Solution of 0/1 Knapsack variation (several sources for elements, each element can be selected from one of the sources)

Question

So, for a practical question, we need to develop a dynamic programming algorithm that is a variation of the 0/1 backpack problem ... Basically, each element comes from 4 different sources, and this element 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 for input, this means that you will not select 6, 26 or 36 ...

Can you help me solve this problem and develop a relapse equation?

Answer 1

We have 4n elements.

Designations:

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

For the k-th element, we have five possible options:

• Do not insert the kth item into the backpack. Under this restriction, the value of the optimal solution is f(k-1,B) . What for? because we still have k-1 elements, and the grade is still B.
• Taking the kth element from S1. Under this restriction, the value of the optimal solution is V[k] + f(k-1, B - W[k]) . What for? We earned V [k] for the kth element and set W [k]. So, for the rest of the elements, we are going to earn f (k-1, B - W [k]).
• Taking the k-th element from S2. Use the same logic as before to see that the value of the optimal solution under this constraint is V[k+n] + f(k-1, B - W[k+n]) .
• Taking the nth element from S3. optimal: V[k+2n] + f(k-1, B - W[k+2n]) .
• Taking the nth element from S4. optimal: V[k+3n] + f(k-1, B - W[k+3n]) .

Your goal is to maximize f. Therefore, the recurrence equation:

 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 } 

It remains to find the initial conditions.

Answer 2

The standard problem with a backpack is 0/1: for each element you either don’t take it or you do it.

Your problem: for each element, either you do not take it, or you take it from source 1, or ... or you take it from source 4.

Now let's look at the usual dynamic programming algorithm and the recurrence relation for the 0/1 backpack problem. See where each RHS bit comes from in a recursive manner; this corresponds to the first statement above. Adapt to use the second operator instead.

(If I'm a little mysterious, this is because this is homework, and you should study: -).