解决 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 或 36 ...

你能帮我解决这个问题并设计递推方程吗？

Answer 1

我们有 4n 个元素。

表示法：

• V[k] - 元素 k 的值 (1 <= k <= 4n)
• W[k] - 元素的权重element 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
   }

剩下的就是求初始条件。

Answer 2

标准 0/1 背包问题：对于每件物品，要么不拿，要么拿。

您的问题：对于每件物品，要么不拿，要么拿从源 1 获取它，或者...，或者从源 4 获取它。

现在看看 0/1 背包问题的常用动态规划算法和递推关系。查看递归关系中RHS的每一位来自哪里；它对应于上面的第一条语句。改为使用上面的第二个语句。

（如果我有点神秘，那是因为这是作业，你应该学习:-)。）