如何实现适用的举措算法0-1背包？

Question

我现在正在研究背包问题（kp），并找到 wikipedia 有点不清楚，如何在 $ o ^ *（2 ^ {n / 2}）$ ？我可以理解子集合问题（SSP）的算法，它是0-1 kp的特定实例，但对于概括的问题，步骤可能存在问题：

  for each subset of A do
      find the subset of B of greatest value such that the combined weight is less than W

.

如我所理解的是，这是搜索（例如，在B的所有子集的组合权重上搜索（做二进制搜索），这是每个搜索的对数时间。但是在知道哪些子集中的重量小于w后，如何找到最大的价值之一？如果在具有权重 $ o ^ *（2 ^ {n / 2}）$ ，但类似于 $ o ^ *（2 ^ n）$ 。

即使它首先开始发现最大值（易于为表格的易于易于收缩）而没有收缩，在此之后，权重的验证可能会向虚假变为错误，因此对于其他子集需要更多的测试数字似乎与表尺寸再次线性相关。

现在，我只能假设总值和组合权重是强烈的正相关，使得在找到最大允许权重的子集之后，只需要恒定的时间来搜索这个子集以获得最大的最大值之一。但我对这种解释不满意。所以有人对这个问题有更好的想法吗？

ps：我已经阅读了霍洛伊茨，ellis和sahni，sartaj的原始纸张，但我发现定义的问题有一个决策问题而不是常见的优化问题。也许有人可以在这个方向上提供想法。

Answer 1

首先，请在 $ b $ 中的每个子集的权重。

按重量排序，并将权重和子集放在并行阵列中，使 $ w [i]= prefile $ 和 $ s [i]=子集$ 。

然后使另一个并行阵列使得 $ best [i] $ 是索引 $ j $ 其中最大的值，使得<跨度类=“math-container”> $ j <= i $ 。您可以使用单个扫描从 $ i= 0 $ 向上，记住到目前为止看到的最大值。

现在，要搜索 $ b $ ，您可以在 $ w $ 中进行二进制搜索最大允许权重，并在 $ best $

中获得最佳索引中的最佳集合