我需要编写解决装箱问题的程序，但我已经编写了优先拟合和贪心算法，但我的讲师说在某些情况下它找不到问题的最小解。所以我决定尝试暴力破解，但我不知道它应该如何检查所有可能的解决方案。所以是的......有人可以向我解释或提供伪代码或其他东西。我将不胜感激。
最佳答案
请注意 bin-packing是一个 NP-hard 问题，基本上意味着它会花费过长的时间对其进行蛮力计算，即使对于相对较小的输入也是如此，因此对 NP-hard 问题进行蛮力计算几乎从来都不是一个好主意。上面的链接显示了一些替代方案(或近似值)。但我会继续...
Recursion使蛮力变得容易。一旦你明白a basic recursive algorithm , 继续阅读...
基本思路:(对于 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)
关于java - 装箱暴力破解法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16083977/