1

我正在准备考试，我们得到了一组练习题。这是我正在努力解决的问题，我希望有人可以帮助阐明解决此问题的正确方法： 在此处输入图像描述

这是我最初解决这个问题的方法：

决策版本：要使用决策版本找到最佳解决方案，我会尝试使用各种 K，直到得到肯定的答案。假设优化的解决方案是 7，我会尝试：

k=1, no
k=2, no
k=3, no
k=4, no
k=5, no
k=6, no
k=7, yes.

所以现在我们知道最佳解决方案是 7 个 bin，我们通过按大小从最大到最小对项目进行排序来解决决策版本，然后将填充最大到最小的 bin 填满，然后循环遍历这些 bin，直到它们不再存在集合中的元素。

如果我们有一个最优解决方案并且我们想要解决决策版本，我将获取最优解决方案返回的箱数，并在决策版本上运行它，看看它是否返回是。

我以前从未真正见过这样的问题，所以我不确定正确的格式应该是怎样的。

任何帮助将不胜感激！

4

1 回答 1

2

有一种更好的方法来解决基于决策问题的优化问题，请注意，您的解决方案在输入的大小上是指数的（伪多项式，但仍然是指数的） ，因为如果您有一个T(n)在决策问题，建议的解决方案在 中运行O(k*T(n))，但由于k实际上是输入大小的指数（您只需要log(k)位来表示它），因此您有一个指数运行时间。

但是，您可以对问题应用二分搜索，并且只需要O(log(k))调用决策问题的算法即可解决优化问题。

现在，如果 P = NP，并且这种算法（用于解决决策问题）存在于多项式时间内O(p(n))，则解决优化问题将在O(p(n) * log(k))- 这是输入大小的多项式。

二进制搜索将是这样的：

k <- 1
while decision_bin_packing(G,k) == false:
    k <- k * 2
perform binary search for the smallest value t in [k/2,k] such that decision_bin_packing(G,t)==true

最后的二分搜索非常标准，只需O(logk)调用decision_bin_packing.

于 2014-12-08T09:04:48.307 回答