c++ - 为什么整数背包的容量为1？

Question

整数背包问题的动态规划解决方案，对于容量为 C 的背包，对于 n 个元素，其中第 i 个元素的大小为 Si，值为 Vi，则为:

M(C)=max(M(C-1), M(C-Si)+Vi)，其中 i 从 1 到 n

这里M是一个数组。 M(C)表示容量为C的背包的最大值。

M(C-1) 在这个关系中有何用处？我的意思是解决方案应该是这样的:

M(C)=max(M(C-Si)+Vi)，其中 i 从 1 到 n

我认为 M(C-1) 涵盖的所有情况都在 M(C) 中涵盖。

如果我错了，请给我一个示例情况。

Answer 1

我认为您必须将公式设置得有点困惑 - 具体来说，您将袋子的容量与 n-1 件元素的子问题混淆了。让我们重新定义一下。

• 让P表示问题，如 n 列表所示项目。
• 此外，让 Pk表示由索引 1...k 处的项目组成的子问题从最初的问题来看，其中1 <= k <= n 。因此Pn相当于 P .
• 对于索引 i 处的每个项目，让Vi表示该项目的值，Si表示该项目的大小。
• 让C是袋子的容量，C >= 0
• 让M(Pk, C)表示 Pk 描述的问题的最佳解决方案带袋容量C 。 M(Pk, C)返回解决方案中包含的元素列表(因此也返回最优解决方案的值和袋子中的剩余容量)。

对于每个项目，我们可以将其包含在最优解中，也可以不将其包含在最优解中。显然，最佳解决方案是这两个选项中更可取的一个。唯一需要考虑的特殊情况是相关元素是否无法放入包中。在这种情况下，我们必须排除它。

我们可以依靠递归来覆盖我们的每一项，因此不需要迭代。因此，总的来说:

M(Pk,C) = if(Sk > C) M(P(k-1), C) else max(M(P(k-1),C), Vk + M(P (k-1),C-Sk))