Solving a variation of 0/1 Knapsack (multiple source for items, each item can be selected from one of the sources)

Question

So for a practice question, we are supposed to design a Dynamic Programming algorithm which is a variation of 0/1 knapsack problem... Basically each item comes from 4 different source, and that item can be taken from only one of the sources..

Namely,

S1={(d_k, b_k) | 1 ≤ k ≤ n},
S2={(d_k, b_k) | n + 1 ≤ k ≤ 2n},
S3={(d_k, b_k) | 2n + 1 ≤ k ≤ 3n},
S4 = {(d_k, b_k) | 3n + 1 ≤ k ≤ 4n}

for n = 10, if you select i = 16 to put, that means you won't select 6, 26 or 36...

Can you help me to solve this problem and devise the recurrence equation?

Answer 1

We have 4n elements.

Notation:

• V[k] - value of element k (1 <= k <= 4n)
• W[k] - weight of element k (1 <= k <= 4n)
• B - The bound
• f(k,B) - The value of the optimal solution when the bound is B and you have 4k elements.

For the kth element we have five possible choices:

1. Not inserting the kth element to the knapsack. Under that constraint, the value of the optimal solution is f(k-1,B). Why? because we have k-1 more elements and the bound is still B.
2. Taking the kth element from S1. Under that constraint, the value of the optimal solution is V[k] + f(k-1, B - W[k]). Why? We've earned V[k] for the kth element and waisted W[k]. So for the rest of the elements we're going to earn f(k-1, B - W[k]).
3. Taking the kth element from S2. Use the same logic as before to see that the value of the optimal solution under that constraint is V[k+n] + f(k-1, B - W[k+n]).
4. Taking the nth element from S3. optimum: V[k+2n] + f(k-1, B - W[k+2n]).
5. Taking the nth element from S4. optimum: V[k+3n] + f(k-1, B - W[k+3n]).

Your objective is to maximize f. Hence the recurrence equation is:

f(k, B) =
   max { 
        f(k-1,B),                      //you don't take item n
        V[k]    + f(k-1, B - W[k]),    //you take item k from S1
        V[k+n]  + f(k-1, B - W[k+n]),  //you take item k from S2
        V[k+2n] + f(k-1, B - W[k+2n]), //you take item k from S3
        V[k+3n] + f(k-1, B - W[k+3n])  //you take item k from S2
   }

What left is to find the initial conditions.

Answer 2

Standard 0/1 knapsack problem: For each item, either you don't take it, or you do.

Your problem: For each item, either you don't take it, or you take it from source 1, or ..., or you take it from source 4.

Now look at the usual dynamic programming algorithm and recurrence relation for the 0/1 knapsack problem. Look at where each bit of the RHS in the recurrence relation comes from; it corresponds to the first statement above. Adapt to use the second statement above instead.

(If I'm being a little cryptic, it's because this is homework and you're meant to be learning :-).)