关于优化和决策版本的装箱

Question

我正在准备一次考试，我们得到了一组练习题。这是我正在努力解决的一个问题，我希望有人能帮助我了解一下解决这个问题的正确方法：

​

下面是我对这个问题的初步探讨：

决策版本:为了找到使用决策版本的最优解，我会尝试使用各种K，直到得到一个“是”的答案。假设优化的解决方案是7，我会尝试：

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

所以现在我们知道最优解是7个桶，我们通过从最大到最小的大小排序来解决决策版本，然后填充最大到最小的垃圾箱，然后在垃圾箱上循环，直到它们不再是集合中的元素。

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

我以前从来没有见过这样的问题，所以我不知道合适的格式应该是怎样的。

任何帮助都将不胜感激！

Answer 1

有一种解决基于决策问题的优化问题的更好的方法，请注意，在输入的大小上，您的解是指数的(伪多项式，但仍然是指数的)，因为如果您有一个在决策问题上运行在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来实现。