1

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

有没有人知道关于背包容量根据您选择的项目（即，域是项目的权力集）而不是项目数量而变化的变体的任何信息（名称、文献、算法......）？

4

1 回答 1

0

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

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

sum p_i x_i <= C

在古典背包和

sum p_i x_i <= C (sum x_i)

在塌陷的背包里。

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

现在，如果您对幂集的每个元素都有一个任意容量值C_J，那么您的容量不是向量 的可预测函数，因此从必须检查的列表中x删除子集的唯一方法是其值 ( ) 是否为低于您已经发现可行的子集之一的值（您没有任何来自容量的信息）。Jsum_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): 目前找到的最佳子集的值
  • if M >= M_{k-1}, stop：我们找到了最优的
  • 别的k := k-1

要搜索基数的最佳子集k，您可以使用 的顺序a_i：

  • 从基数为的子集开始{0, ..., k}并递归检查子集，{0} U J'J'k-1{1, ..., n}
  • 然后检查表单的所有子集，其{1} U J'基数J'为k-1等{2, ..., n}。

找到可行子集后，立即更新 bound M。

这又是因为k不包含的基数子集a_0, ..., a_i由 限制a_{i+1} + ... + a_{i+k+1}，一旦它低于当前限制，您就可以停止M。

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

于 2013-10-10T19:49:16.980 回答