Need help with knapsack style problem please. Thanks

[robm612]

Ok guys so i am trying to create 2 versions of a program which sorts items into boxes. The first version i have to create puts the item weights (integer between 1 and 20) into the first "box" they will fit into. So given the input 11,17,3,5,4 the list the program would out put would be 19,17,4. This version i have working fine.

The next version has to put the integers into the boxes in which they will fit best. The code is exactly the same as my first version except i have changed the function which calculates which list item to add the weight to. Basically i have changed the function however is still gives the same output as the first version, i know its somewhere in the function im going wrong, just hoping a fresh pair of eyes could give it the once over and help me out, thanks a million.

def findcontainer(conweights, itemweight):
        count = 0
        gcount = 0
        greatest = itemweight
        while count < len(conweights):
                if conweights[count] + itemweight >= greatest and conweights[count] + itemweight <= 20:
                        greatest = conweights[count] + itemweight
                        gcount = count
                        return gcount
                count = count + 1
        return -1

containerweights = []
itemweightlist = []
serial = []
itemweight = input("Please enter the first item weight. Enter zero to end.")
while itemweight != 0:
    if findcontainer(containerweights, itemweight) != -1:
        containerweights[findcontainer(containerweights, itemweight)] = containerweights[findcontainer(containerweights, itemweight)] + itemweight
    elif findcontainer(containerweights, itemweight) == -1:
        containerweights = containerweights + [0]
        containerweights[findcontainer(containerweights, itemweight)] = containerweights[findcontainer(containerweights, itemweight)] + itemweight 
    itemweightlist = itemweightlist + [itemweight]
    itemweight = input("Please enter the next item weight. Enter zero to end.")

count = 0
while count < len(itemweightlist):
    print "Item", (count + 1),",", "Weight", itemweightlist[count],":", "Container"
    count = count + 1
print "Container Weights:", containerweights

thanks again

[TrustyTony]

I can not see that you changed the function, you are putting value to first fitting slot from beginning, not say find combinations closest to container size. To inputs look ugly, you can use while itemweight: and read the values to list from input inside the while. Put some print statements around the program to see what happens or maybe better to start over and add bit by bit the lines with testing. Probably you should write down your logic and write tests to proove that your program works before you start.

[robm612]

I can not see that you changed the function, you are putting value to first fitting slot from beginning, not say find combinations closest to container size.

The only way i could think of was that the largest value below 20 would be the closest to the containers limit.

This is the function before i changed it

def findcontainer(conweights, itemweight):
        count = 0
        while count < len(conweights):
            if conweights[count] + itemweight <= 20:
                return count
            count = count + 1
        return -1

What kind of code would i use to find combinations closest to the limit?

Thanks

[robm612]

I can not see that you changed the function, you are putting value to first fitting slot from beginning, not say find combinations closest to container size. To inputs look ugly, you can use while itemweight: and read the values to list from input inside the while. Put some print statements around the program to see what happens or maybe better to start over and add bit by bit the lines with testing. Probably you should write down your logic and write tests to proove that your program works before you start.

I know that there is probably better more efficient ways to do this but my task document specifies that i create a function which returns a value, which tells the program where to put the integer and -1 if it doesn't fit anywhere.
It then says that i should only need to change the function to get the program to fit the items more efficiently.

Wouldnt

while itemweight:

give me a list index out of range error?

Btw im a beginner, didnt mention in my first post

[TrustyTony]

You could find at least for value i in values, if there is 20-value and for each container with values, if value 20-total_of_container. There is advanced ways, but the problem is tough one (so called np-hard problem). Generally you could use itertools.combinations and test the sums.

EDIT: What is the initial value you gave to itemweight?

value, values = -1, []
while value:
    try:
        value = int(raw_input("Please enter the first item weight. Enter zero to end."))
        if 0<value<21:
            values.append(value)
        else:
            if value:
                raise ValueError("Incorrect value %s, re-enter" % value)
    except ValueError as e:
        print e
        value = -1

print "values", values

[robm612]

You could find at least for value i in values, if there is 20-value and for each container with values, if value 20-total_of_container. There is advanced ways, but the problem is tough one (so called np-hard problem). Generally you could use itertools.combinations and test the sums.

Wouldnt that mean that if none of the containers values go up to 20 it wouldnt return a value

EDIT: The first time it is assigned a value is when it takes in an input from the user

[TrustyTony]

You must then minimize the difference. The other alternative is trying to equalize the total of all containers. It depends how you define 'fits best'. Minimizing the waste space is generally used definition though.

[robm612]

What it defines as fits best is as follows, given the user input 12,15,5,10,8,9 then 0 to end.

1st version should give - 17,15,18,9
2nd version should give - 20,20,19

[TrustyTony]

For this test case is enough then that you put 12,15 to container one and two and when read 5 see that two is missing 5 and put it ther and same for 12 and 8 etc. However consider that result should work if we enter one more input say 10 and it should not put 9 to number three.