4

我需要制作解决装箱问题的程序，但我已经制作了第一个拟合和贪婪算法，但我的讲师说在某些情况下它不会找到问题的最小解决方案。所以我决定尝试暴力破解，但我不知道它应该如何检查所有可能的解决方案。所以是的..有人可以向我解释或提供伪代码或其他东西。我会很感激。

4

3 回答 3

2

蛮力只是尝试每一种组合。

在此处输入图像描述

要编写蛮力代码，请考虑以下技巧：假设我们要访问 8 个皇后的所有组合，而不对 8 个嵌套循环进行硬编码。想想以下由 8 个零组成的八进制数。

00000000

然后编写一个循环，在八进制数字系统中增加它：

00000001
00000002
00000003
...
00000007 // 7 + 1 = 10
00000010
00000011
00000012
...
77777776
77777777

这会尝试所有组合，而无需对 8 个内部循环进行硬编码。将 8 替换为 n 并且相同的代码仍然有效。

于 2013-04-18T13:48:31.410 回答
2

请注意，装箱是一个 NP-hard 问题，基本上意味着即使对于相对较小的输入，对其进行蛮力运行也需要很长时间，因此NP-hard 问题的蛮力几乎不是一个好主意。上面的链接显示了一些替代方案（或近似值）。但我会继续...

递归使蛮力变得容易。一旦您了解了基本的递归算法，请继续阅读...

基本思想：（对于 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)
于 2013-04-18T14:05:48.313 回答
1

显然，您可以做得比蛮力更好。首先，您计算最小箱数。如果您有大小为 100 的垃圾箱，并且物品的总大小为 1,234，那么它们将不适合 12 个垃圾箱，但可能适合 13 个垃圾箱。

使用 13 个 bin，您将有 66 个 (1,300 - 1,234) 的未使用空间。由于 5 x 13 = 65，因此必须至少有一个大小为 6 的 bin 未使用。因此，如果您有任何尺寸为 6 或以下的物品，则可以将其排除在计算之外，因为最终您仍然可以适应它（当然您需要检查您拥有的实际数字，但无论如何，小物品可以从搜索中删除）。

如果两个项目正好填满一个箱子，那么您不需要考虑任何不适合放在一起的解决方案。

从那时起，您使用动态编程，除了您总是使用最大的未使用项目作为新箱中的第一个项目，您总是按降序将项目装满一个箱，您总是添加更多的项目直到没有合适的东西，您从不考虑组合其中所有项目都较小或与其他组合中的大小相同。最后，当您找到与所需的最小箱数一样好的组合时，您找到了最佳解决方案。

于 2014-03-31T22:41:12.817 回答