13

Given the usual n sets of items (each unlimited, say), with weights and values:

w1, v1
w2, v2
...
wn, vn

and a target weight W, I need to choose items such that the total weight is at least W and the total value is minimized.

This looks to me like a variation (or in some sense converse) of the integer/unbounded knapsack problem. Any help in formulating the DP algorithm would be much appreciated!

unutbu
  • 777,569
  • 165
  • 1,697
  • 1,613
ragebiswas
  • 3,688
  • 8
  • 34
  • 39

2 Answers2

32

let TOT = w1 + w2 + ... + wn.

In this answer I will describe a second bag. I'll denote the original as 'bag' and to the additional as 'knapsack'

Fill the bag with all elements, and start excluding elements from it, 'filling' up a new knapsack with size of at most TOT-W, with the highest possible value! You got yourself a regular knapsack problem, with same elements, and bag size of TOT-W.

Proof:
Assume you have best solution with k elements: e_i1,e_i2,...,e_ik, then the bag size is at least of size W, which makes the excluded items knapsack at most at size TOT-W. Also, since the value of the knapsack is minimized for size W, the value of the excluded items is maximized for size TOT-W, because if it was not maximized, there would be a better bag of size at least W, with smaller value.
The other way around [assuming you have maximal excluded bag] is almost identical.

amit
  • 172,148
  • 26
  • 225
  • 324
  • 3
    Came across the same problem, and this solution is so elegant. I'm impressed, really. Nice work. – seth May 23 '12 at 09:39
0

Not too sure, but this might work. Consider the values to be the -ve of the values you have. The DP formulation would try to find max value for that weight which would be the least negative value in this case. Once you have a value, take a -ve of it for the final answer.

shobhit
  • 87
  • 2
  • 8