algorithm - 动态规划中的背包变体

Question

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

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

如何构建正确的循环？

Answer 1

回想一下，用于 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，则与原始版本没有任何变化)