On Feb 13, 8:06 am, "Kurioz" <zpetel...@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 -- http://mail.python.org/mailman/listinfo/python-list