动态规划中的背包变体

Question

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

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

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

Answer 1

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

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

在你修改的问题中，如果你选择 take i- you can't take 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）