Solving knapsack problem using a greedy python algorithm

Question

I'm trying to solve the knapsack problem using Python, implementing a greedy algorithm. The result I'm getting back makes no sense to me.

Knapsack:

The first line gives the number of items, in this case 20. The last line gives the capacity of the knapsack, in this case 524. The remaining lines give the index, value and weight of each item.

20
    1    91    29
    2    60    65
    3    61    71
    4     9    60
    5    79    45
    6    46    71
    7    19    22
    8    57    97
    9     8     6
   10    84    91
   11    20    57
   12    72    60
   13    32    49
   14    31    89
   15    28     2
   16    81    30
   17    55    90
   18    43    25
   19   100    82
   20    27    19
524

Python code:

import os 

def constructive():     
    knapsack = []
    Weight = 0
    while(Weight <= cap):
        best = max(values)
        i = values.index(best)
        knapsack.append(i)
        Weight = Weight + weights[i]
        del values[i]
        del weights[i]
    return knapsack, Weight


def read_kfile(fname):
    with open(fname, 'rU') as kfile:
        lines = kfile.readlines()     # reads the whole file
    n = int(lines[0])
    c = int(lines[n+1])
    vs = []
    ws = []
    lines = lines[1:n+1]   # Removes the first and last line
    for l in lines:
        numbers = l.split()   # Converts the string into a list
        vs.append(int(numbers[1]))  # Appends value, need to convert to int
        ws.append(int(numbers[2]))  # Appends weigth, need to convert to int
    return n, c, vs, ws

dir_path = os.path.dirname(os.path.realpath(__file__))  # Get the directory where the file is located
os.chdir(dir_path)  # Change the working directory so we can read the file

knapfile = 'knap20.txt'
nitems, cap, values, weights = read_kfile(knapfile)
val1,val2 =constructive()
print ('knapsack',val1)
print('weight', val2)
print('cap', cap)

Result:

knapsack [18, 0, 8, 13, 3, 8, 1, 0, 3]
weight 570
cap 524

MooingRawr · Accepted Answer · 2018-10-05 20:45:58Z

3

Welcome. the reason why your program is giving a weights over the cap limit is because on the final item you are putting in the knapsack, you aren't checking if it can fit in it. To do this just add an if statement, Also you should check if the list of values is empty. Do note that I have append (i+1) since your text file's index is starting at 1 but Python starts it's list index at 0:

def constructive():
    knapsack = []
    Weight = 0

    while(Weight <= cap and values):
        best = max(values)
        i = values.index(best)
        if weights[i] <= cap-Weight:
            knapsack.append(i+1)
            Weight = Weight + weights[i]
        del values[i]
        del weights[i]

    return knapsack, Weight

answered Oct 5, 2018 at 20:45

MooingRawr

4,9973 gold badges30 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

FChris · Accepted Answer · 2018-10-05 20:49:35Z

The problem is -- in the last step -- the best item you find will exceed the maximum weight. But since you already entered the loop you add it anyway. In the next iteration you recognize that you are over the cap and stop.

I am not sure how you want to proceed once the next best is too heavy. In case you simple want to stop and not add anything more you can simply modify your constructive to look as follows:

def constructive():

    knapsack = []
    Weight = 0

    while(True):
        best = max(values)
        i = values.index(best)

        if Weight + weights[i] > cap:
            break

        knapsack.append(i)
        Weight = Weight + weights[i]

        del values[i]
        del weights[i]

    return knapsack, Weight

Collectives™ on Stack Overflow

Solving knapsack problem using a greedy python algorithm

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related