我需要制作解决装箱问题的程序,但我已经制作了首次拟合和贪婪算法,但我的讲师说在某些情况下它不会找到问题的最小解决方案。所以我决定尝试暴力破解,但我不知道它应该如何检查所有可能的解决方案。所以是的..有人可以向我解释一下或者给出伪代码什么的。我将非常感激。
注意装箱 http://en.wikipedia.org/wiki/Bin_packing_problem是一个 NP 难问题,基本上意味着即使对于相对较小的输入,也需要很长时间才能对其进行暴力破解,所以暴力破解 NP 难题几乎从来都不是一个好主意。上面的链接显示了一些替代方案(或近似值)。但我会继续...
递归 http://www.cse.wustl.edu/~kjg/cse131/Notes/Recursion/recursion.html使暴力破解变得容易。一旦你明白了基本的递归算法 https://stackoverflow.com/a/9724748/1711796, 继续阅读...
基本思想:(对于 3 件物品,2 个箱子,假设一切都合适,如果它不只是跳过该分支)
Put the first item in the first bin.
Put the second item in the first bin.
Put the third item in the first bin.
Woo-hoo! We have a solution!
Remove the third item from the first bin and put it into the second bin.
Woo-hoo! We have a solution!
Remove the third item from the second bin.
Remove the second item from the first bin and put it into the second bin.
Put the third item in the first bin.
Woo-hoo! We have a solution!
Remove the third item from the first bin and put it into the second bin.
Woo-hoo! We have a solution!
Remove the third item from the second bin.
Remove the second item from the second bin.
Remove the first item from the first bin and put it into the second bin.
Put the second item in the first bin.
Put the third item in the first bin.
Woo-hoo! We have a solution!
Remove the third item from the first bin and put it into the second bin.
Woo-hoo! We have a solution!
Remove the third item from the second bin.
Remove the second item from the first bin and put it into the second bin.
Put the third item in the first bin.
Woo-hoo! We have a solution!
Remove the third item from the first bin and put it into the second bin.
Woo-hoo! We have a solution!
Remove the third item from the second bin.
Remove the second item from the second bin.
Remove the first item from the second bin.
(看看已经有多少步了?这只是 3 件物品和 2 个垃圾箱)
伪代码:
recurse(int itemID)
if pastLastItem(itemID)
if betterThanBestSolution
bestSolution = currentAssignment
return
for each bin i:
putIntoBin(itemID, i)
recurse(itemID+1)
removeFromBin(itemID, i)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)