algorithm - 装箱，决策与优化

Question

对于一个作业，我得到了装箱问题，并要求我展示如何从优化版本中解决问题的决策版本，反之亦然。我知道要解决决策版本，您只需将优化版本中使用的 bin 数量与指定的最大 bin 数量进行比较，但我如何使用决策版本来解决优化版本？

Answer 1

您可以通过观察如果Nbins 足够，那么K > Nbins 也足够，可以使用决策版本来解决优化版本。

从单个 bin 开始，然后在其上运行决策版本。如果答案是true，你就完成了；否则，请继续将垃圾箱数量增加一倍，直到您达到true. 假设您true在尝试时得到了答案N = 2 ^ k。M = 2^(k-1)然后，您可以在和之间运行二进制搜索N，以找到优化问题的确切解决方案（两者N都k来自上一步）。

考虑这个例子：假设最优解是 14。然后您可以尝试以下决策问题序列来找到答案：

• 1 -->false
• 2 --> false(加倍 1)
• 4 --> false(加倍 2)
• 8 --> false(加倍 4)
• 16 --> true（加倍 8；我们有一个true，所以继续进行二分搜索）
• 12 --> false（8 到 16 之间的中点）
• 14 --> true(12 和 16 之间的中点)
• 13 --> false(12 和 14 之间的中点)

一般来说，可以在对数时间内找到答案（即在 Log ₂ (Answer) 中）。

一旦您知道N打包对象所需的箱数，X就在一侧的项目和另一侧的箱之间运行二分匹配算法N。假设正确解决了决策问题，这样的二分匹配一定存在，并且可以在多项式时间内找到。