Minimization of the Unbounded Knapsack with Dynamic Programming

Question

I am curious if it is possible to modify (or use) a DP algorithm of the Unbounded Knapsack Problem to minimize the total value of items in the knapsack while making the total weight at least some minimum constraint C.

A bottom-up DP algorithm for the maximization version of UKP:

let w = set of weights (0-indexed)

and v = set of values (0-indexed)

    DP[i][j] = max{ DP[i-1][j], DP[i][j - w[i-1]] + v[i-1] }

for i = 0,...,N and j = 0,...,C

given DP[0][j] = 0 and DP[i][0] = 0

where N = amount of items

and C = maximum weight

DP[N][C] = the maximum value of items for a knapsack capacity of C

Can we make a minimization UKP ? If not, can anyone offer another solution or technique to solve a problem like this?

Thanks, Dan

note that it should be DP[i-1][j - w[i-1]], not DP[i][j - w[i-1]] in the algorithm above. I tried making the edit but it didn't go through the review. — bernie

David Eisenstat David Eisenstat · Accepted Answer · 2014-08-17T23:14:47

You'll have the new recurrence

DP[i][j] (       j <= 0) = 0
DP[i][j] (i = 0, j >  0) = infinity
DP[i][j] (i > 0, j >  0) = min{ DP[i-1][j], DP[i-1][j - w[i-1]] + v[i-1] },

which gives, for each i and j, the minimum value of items 0..i-1 to make weight at least j. infinity should be some sufficiently large value such that any legitimate value is smaller than infinity.

Notice that DP[i][j] = 0 for all j <= 0 is specified. Sometimes the indexing j - w[i-1] will produce a negative value for the second index. These negative indices j in matrix DP should give the value 0 for the algorithm to work.

Additionally, by definition of DP[i][j], one might expect non-zero values for DP[i][0], since j=0 corresponds to a minimum weight of 0, but DP[i][0] = 0 for all i is necessary for the DP algorithm.

Minimization of the Unbounded Knapsack with Dynamic Programming

1 Answers