折叠背包问题是普通背包问题的推广,其中背包容量是所含元素数量的非增函数。
有谁知道背包容量根据您选择的项目(即域是项目的幂集)而不是项目数量而变化的变体(名称、文献、算法...)?
最佳答案
对于“容量”的一般值,我相信您需要对集合元素进行某种枚举。如果我理解正确,它或多或少对应于一个任意 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
.
关于algorithm - 折叠背包,容量变化是根据选择的元素而不是数量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19267969/