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

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 个箱子，我们通过按大小从最大到最小对项目进行排序来解决决策版本，然后从最大到最小填充箱子，然后循环遍历箱子直到它们集合中不再有元素。

如果我们有一个最优解并且我们想解决决策版本，我会获取最优解返回的 bin 数，然后在决策版本上运行它以查看它是否返回 yes。

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

任何帮助将不胜感激!

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 即可轻松实现。