解决0/1背包的变化(项目的多个来源,每个项目可以从其中一个来源中选择)

Question

因此,对于练习题,我们应该设计一个动态编程算法,它是0/1背包问题的变体......基本上每个项目来自4个不同的来源,并且该项目只能从其中一个来源获取. .

也就是说,

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}

因为n = 10,如果你选择i = 16放,这意味着你不会选择6, 26 or 36...

你能帮助我解决这个问题并设计复发方程吗？

Answer 1

我们有4n个元素.

符号:

• V[k] - 元素k的值(1 <= k <= 4n)
• W[k] - 元素k的权重(1 <= k <= 4n)
• B - 界限
• f(k,B) - 当边界为B且您有4k个元素时,最优解的值.

对于第k个元素,我们有五种可能的选择:

1. 不将第k个元素插入到背包中.在该约束下,最优解的价值是f(k-1,B).为什么？因为我们有k-1个元素,并且边界仍然是B.
2. 从S1获取第k个元素.在该约束下,最优解的价值是V[k] + f(k-1, B - W[k]).为什么？我们为第k个元素赢得了V [k]并且W [k].所以对于剩下的元素,我们将获得f(k-1,B-W [k]).
3. 从S2获取第k个元素.使用与以前相同的逻辑来查看该约束下的最优解的值V[k+n] + f(k-1, B - W[k+n]).
4. 从S3获取第n个元素.最佳:V[k+2n] + f(k-1, B - W[k+2n]).
5. 从S4获取第n个元素.最佳:V[k+3n] + f(k-1, B - W[k+3n]).

你的目标是最大化f.因此,递推方程是:

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
   }

剩下的就是找到初始条件.