Python knapsack problem

Kurioz zpeteljac at gmaljo.com
Fri Feb 13 11:06:55 EST 2009


Hi,

I got the assignment to solve the knapsack problem in Python. I have to find 
the solution to put items in a sack (I have only one item A, B and C) which 
maxWeight can't be larger than 6 kilograms.  Solution of this problem should 
be A and C but the only solution I'm getting is B and C which aren't true 
because weight of the B and C is 7 kilograms which is heavier than the 
maxWeight.

If anyone could point me what am I doing wrong I'd be very grateful! Thanks 
in advance!

Code:

#1st array element is weight of an item, and 2nd array element is value
A=[2.0,1.0]
B=[3.0,7.0]
C=[4.0,8.0]
#Checking the values per one kilo
vA=A[1]/A[0]
vB=B[1]/B[0]
vC=C[1]/C[0]
maxWeight=0
print vA,vB,vC
#Checking the values
while maxWeight<6:
    if int(vA)>int(vB) and int(vA)>int(vC):
        maxWeight=maxWeight+A[0]
        vA=0
        print maxWeight

    elif int(vB)>int(vA) and int(vB)>int(vC):
        maxWeight=maxWeight+B[0]
        print maxWeight

    else:
        vC=0
        maxWeight=maxWeight+C[0]
        print maxWeight 




More information about the Python-list mailing list