5

所以对于一个练习题，我们应该设计一个动态规划算法，它是 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...

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

4

2 回答 2

8

我们有 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
   }

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

于 2011-03-20T22:00:31.170 回答
3

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

你的问题：对于每个项目，要么你不接受它，要么你从源 1 中获取它，或者......，或者你从源 4 中获取它。

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

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

于 2011-03-20T21:43:35.497 回答