algorithm - 折叠背包，容量变化是根据选择的元素而不是数量

Question

折叠背包问题是普通背包问题的推广，其中背包容量是所含元素数量的非增函数。

有谁知道背包容量根据您选择的项目(即域是项目的幂集)而不是项目数量而变化的变体(名称、文献、算法...)？

Answer 1

对于“容量”的一般值，我相信您需要对集合元素进行某种枚举。如果我理解正确，它或多或少对应于一个任意 bool 值，表示一个子集是否可行(其元素的权重之和低于其容量)。

背包问题中的“容量”是出现在约束右侧的东西，即

sum p_i x_i <= C

在经典背包中

sum p_i x_i <= C (sum x_i)

在折叠的背包里。

因为这些是线性约束，它们以某种可预测的方式表现，避免查看所有可能的组合(幂集的元素)来解决问题。

现在，如果您有一个任意容量值C_J对于幂集的每个元素，您的容量不是向量的可预测函数 x , 所以你删除子集的唯一方法 J从列表中必须检查的是它的值 ( sum_J a_i x_i ) 是否低于您已经发现可行的子集之一的值(您没有任何来自容量的信息).

这特别意味着没有办法用整数程序对此进行建模，因为每个 C_J 都需要至少一个约束。 (只计算每个可行子集的成本会更有效)。

我会使用枚举算法并尝试尽可能地减少搜索树。

让我们按非增值的顺序来排序a_0 >= a_1 >= ... >= a_n .

我们可以通过降低基数来查看所有可能的子集。这是因为对于一些基数 k ，您知道基数最多为 k 的最佳可能子集的值为 M_k = sum_{i=0}^k a_i ，因此您将能够在检查所有子集之前停止搜索(我想不出另一种切割搜索树的方法)。

算法将是:

以 M := 0 开头和 k=n .

重复:

• 找到具有基数的最佳子集 k如果它的值 A优于M
• M := max (A, M) : 迄今为止找到的最佳子集的值
• 如果M >= M_{k-1} , 停止:我们找到了最优
• 其他 k := k-1

搜索基数的最佳子集k , 你可以使用 a_i 的顺序:

• 开始于 {0, ..., k}并递归检查子集 {0} U J'与 J'基数的子集 k-1的 {1, ..., n} ,
• 然后检查 {1} U J' 形式的所有子集与 J'基数的子集 k-1的 {2, ..., n}等

一旦找到可行子集，就更新边界 M .

这又是因为基数的子集 k不包含 a_0, ..., a_i以 a_{i+1} + ... + a_{i+k+1} 为界, 你可以在低于当前界限时立即停止 M .

注意:我假设没有关于容量的假设 C_J .知道容量是否在集合论意义上增加当然很有趣，即如果 I包含在 J 中暗示C_I <= C_J .