Python knapsack problem

[Kurioz]

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

 

[Matimus]

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

You will need to check whether each item can fit before adding it.

Currently you are doing:

while there is room in the sac:
add the next most valuable item

You should be doing:

while there is room in the sac:
if the next most valuable item fits
add it

But... once you fix that you will run into another issue.

You are using ints to compare. Casting floating point values to ints
will always
round down.

vA = 0.5
vB = 2.3333...
vC = 2.0

But..
2

Matt

 

[Terry Reedy]

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!

There are several comments I could make, but your immediate problem is
this: before putting something in the knapsack, you must check whether
it will exceed the limit. Since this is a class assignment, I will stop
there.

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