3

There are types of items (N types), each have weight wi and cost ci. There are an infinite number of each. The problem is to make a knapsack with EXACT (W) weight and minimum total cost of items. I know I should use dynamic in this case, but it's not a usual knapsack problem and I can't find the relation. I also found some similar questions, but I haven`t understood theese solutions. Here are the links 1, 2. How to use DP to solve it?

Community
  • 1
  • 1
John Smith
  • 41
  • 1
  • 1
  • 4

2 Answers2

4

let f[i] means, to get weight i, the minimum cost. g[i] means whether it is possible to combine exactly weight i;

f[0]=0;g[0]=true;
for (int i=0;i<N;i++)
    for (int j=0;j<W;j++)
        if (g[j]) {
            g[j+w[i]]=true;
            if (f[j+w[i]]==0||f[j+w[i]]>f[j]+c[i])
                f[j+w[i]]=f[j]+c[i];
        }

if (g[W]) return f[W];
else return 0;//impossible
songlj
  • 927
  • 1
  • 6
  • 10
  • Does this algorithm really take the unbounded nature into account? (That there's an infinite number of each type available). I can't quite see how it does? – estan Oct 01 '15 at 17:46
2

Assuming you want to find the minimum cost it can take you to accomplish a weight of W and that c_i > 0 and w_i > 0 then we can define min_cost(i, W) as the minimum cost that can be achieved using only items from i to N whose weight is W

  • The base case happens when we only have one item, thus when i=N. In that case the solution is:

    min_cost(N, 0) = 0 because if we do not use item N then we already have a weight equal to 0

    min_cost(N, W) = c_i * W / w_i if W is a multiple of w_i i.e W mod w_i = 0

    min_cost(N, W) = Infinity otherwise since we cannot achieve a weight of exactly W with only the last item.

  • The recurrent relation can now be stated as:

    min_cost(i, W) = min(c_i * k + min_cost(i+1, W - k * w_i)) for k=0 until W - k*w_i < 0

The recurrent relation states that we will use item i as many times as possible while we have not made a weight bigger than W.

You can then implement this methodology with a recursive algorithm using memoization and storing as you see fit the actual solutions (the ks in the recurrence).

Edit Upon a suggestion a speedup can be achieved if we notice that there are two cases that influence min_cost(i, W). Such cases are first when do not need to use the ith item at all i.e. min_cost(i+1, W) and when we are going to use the ith item at least once, which is the same as min_cost(i, W - w_i) since we might use item i more than one time. This changes our recurrence to the following:

min_cost(i, 0) = 0         // We already reached our goal
min_cost(i, W) = Infinity  // if (W < 0 or i > N) then we can't get to W

min_cost(i, W) = min(min_cost(i+1, W), min_cost(i, W - w_i) + c_i)
Gustavo Torres
  • 464
  • 6
  • 22
  • 1
    Here's a speedup: if for a given i you calculate weights in increasing order, then to calculate `min_cost(i, W)` you only ever need to try adding either 0 instances of item i to the optimal solution for items i+1 .. N, or 1 instance of item i to the optimal solution *for items i .. N* (which you've already calculated because it has lower weight): `min_cost(i, W) = min(min_cost(i+1, W), min_cost(i, W-w_i) + c_i)`. In the worst case where all weights are 1, this kills a factor of W. – j_random_hacker Mar 18 '13 at 16:10
  • I added that speedup as an edit to the answer. Good speedup and way simpler, thanks! – Gustavo Torres Mar 18 '13 at 18:09
  • 1
    You're welcome! P.S. If you write e.g. "@j_random_hacker" somewhere in a comment, it will notify that person. I only noticed your comment because I came back out of vanity :-P – j_random_hacker Mar 19 '13 at 13:13
  • @GustavoTorres, Any chance you have a look at this - https://math.stackexchange.com/questions/2415617? Thank You. – Royi Sep 03 '17 at 21:07