2

我正在尝试解决这个练习：我们有 n 个项目，其中每个项目都有一个给定的非负重量 w1,w2,...,wn 和值 v1,v2,...,vn，以及一个最大重量容量的背包W.我必须找到一个最大值的子集S，受两个限制：1）集合的总重量不应超过W；2) 我不能获取具有连续索引的对象。

例如，当 n = 10 时，可能的解是 {1, 4, 6, 9}, {2, 4, 10} o {1, 10}。

我怎样才能建立一个正确的重复？

4

1 回答 1

5

回想一下，用于 DP 解决方案的背包递归公式是：

D(i,w) = max { D(i-1,w) , D(i-1,w-weight[i]) + value[i] }

在你修改的问题中，如果你选择了i- 你不能采取i-1，导致修改：

D(i,w) = max { D(i-1,w) , D(i-2,w-weight[i]) + value[i] }
                              ^
                          note here 
                       i-2 instead of i-1

与经典背包类似，它也是一种详尽的搜索——因此出于同样的原因提供了最佳解决方案。
给出的想法是你已经决定选择i——你不能选择i-1，所以找到最多使用该项目的最佳解决方案i-2。（如果您决定排除，则与原始内容没有任何变化i）

于 2013-01-10T10:50:39.230 回答