0/1 Knapsack with integer values and irrational weights?

Question

The standard 0/1 knapsack problem lends itself to a simple DP solution: with n distinct objects with irrational values, integer weights, and a max weight of W, make an n x W array m and let m[i, j] be the maximum value achievable with items 1 to i and a weight of at most j.

I'm trying to solve the problem where the weights are irrational but the values are rational. I'm told that there is an O(nV) solution, where V is the sum of all of the values. I want to say something like this: let m be an n x V array, and let m[i, j] be the minimum possible weight to achieve a value of at least j with items 1 to i. This would yield something like the following:

def knapsack(weights, values, max_weight):
    max_v = sum(values)
    m = [[0 for _ in range(max_v)] for _ in weights]

    for i in range(len(weights)):
        for j in range(max_v):
            if j < values[i]:
                m[i][j] = m[i - 1][j]
            else:
                m[i][j] = min(m[i - 1][j], weights[i] + m[i - 1][j - values[i]])

    for val, col in reversed(enumerate(zip(*m))):
        wt = min(col)
        if wt <= max_weight:
           return col

    return 0

But this doesn't work: cells like m[0, 100] get initialized with meaningless junk that propagates downward. I'm not sure how to solve this, and I can't find any info. It looks like this question would provide an algorithm to fill each cell, but it would be too expensive to call for every single one.

is this a typo,"where the weights are irrational but the weights are rational", also could you give a small example ? — advocateofnone, Jan 14 '15 at 10:57
Yes, my mistake. I also accidentally deleted some code from my broken solution. — Patrick Collins, Jan 14 '15 at 10:59
@PM2Ring No, not at the moment, I don't think I used anything numpy specific? It's late, though, and I may have made a mistake. — Patrick Collins, Jan 14 '15 at 11:03
Also, `m = [[0] * max_v] * len(weights)` probably doesn't do what you want it to do. Eg, `m=[[0]*5]*3;m[1][1]=7;print(m)` prints `[[0, 7, 0, 0, 0], [0, 7, 0, 0, 0], [0, 7, 0, 0, 0]]`. See http://stackoverflow.com/q/240178/4014959 for details. — PM 2Ring, Jan 14 '15 at 11:05
General case DP -- maybe you've seen this? http://rosettacode.org/wiki/Knapsack_problem/Unbounded/Python_dynamic_programming — Paul, Jan 14 '15 at 11:06
@Paul None of those seem to handle non-integer weights, as far as I can tell. — Patrick Collins, Jan 14 '15 at 11:12

David Eisenstat · Accepted Answer · 2015-01-14T13:01:48.430

Let's change the meaning of m to the minimum weight for exactly the given value. We then want an initialization like

m = [[(float('inf') if j else 0) for j in range(max_v + 1)] for _ in range(len(weights) + 1)]

where I'm using positive infinity as a marker of infeasibility (I also fixed two off-by-one errors in the table size). Then the loop can look something like this (untested).

for i in range(len(weights)):
    for j in range(max_v + 1):
        if j >= values[i]:
            m[i + 1][j] = min(m[i][j], m[i][j - values[i]] + weights[i])
        else:
            m[i + 1][j] = m[i][j]

Then we have to adjust the output extraction to reflect the new definition of m.

0/1 Knapsack with integer values and irrational weights?

1 Answers1