algorithm - 装箱，决策与优化

Question

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

Answer 1

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

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

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

• 1 --> 假
• 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) 中)。

一旦您知道打包 X 对象所需的 bins N 数量，就在一侧的项目和 N 之间运行二分匹配算法代码 > 垃圾箱在另一边。假设正确解决了决策问题，则必须存在这种二分匹配，and can be found in polynomial time .