Python knapsack problem

[Matimus]

On Feb 13, 8:06 am, "Kurioz" <zpetel... at gmaljo.com> wrote:
> 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..

>>> int(vA)
0
>>> int(vB)
2
>>> int(vC)
2

Matt