我必须实现一个有约束的 0/1 背包问题的解决方案。在大多数情况下，我的问题几乎没有变量（〜 10-20，最多 50）。
我记得在大学里有许多算法在许多情况下比蛮力执行得更好（例如，我在想分支定界算法）。
由于我的问题相对较小，我想知道在使用复杂的解决方案而不是蛮力时在效率方面是否有明显的优势。
如果有帮助，我正在用 Python 编程。
问问题
1282 次
3 回答
1
如果权重之和足够小，您可以使用伪多项式算法，该算法使用动态编程。您只需计算，是否可以通过每个 X 和 Y 的前 Y 个项目获得权重 X。这在 O(NS) 时间内运行，其中 N 是项目数，S 是权重总和。
另一种可能性是使用中间相遇的方法。将项目分成两半，并且：对于前半部分，取所有可能的项目组合（每半部分有 2^(N/2) 个可能的组合）并将其权重存储在某个集合中。后半部分取所有可能的项目组合，检查前半部分是否有合适重量的组合。这应该在 O(2^(N/2)) 时间内运行。
于 2012-06-22T11:47:07.387 回答
0
蛮力的东西对于 10 个变量可以正常工作，但是对于 40 个变量，你会得到大约 1000'000'000'000 个可能的解决方案，这可能需要很长时间才能枚举。我会考虑近似算法，例如多项式时间算法（参见例如http://math.mit.edu/~goemans/18434S06/knapsack-katherine.pdf）或使用诸如分支定界的搜索算法，也许有一个额外的启发式。
于 2012-06-22T11:11:36.573 回答
0
蛮力算法将始终返回最佳解决方案。它们的问题在于，在指数级问题中，它们很快变得不可行。
如果保证最多有 20 个变量，那么您将测试不超过 100 万个解决方案 (2^20= 1M)。因此，蛮力是可行的，没有其他算法会返回更好的解决方案。
启发式方法很棒，但只有在我们无法准确解决问题时才应该使用它们。有一本好书可以帮助你：如何解决它，作者 Michalewicz。
于 2012-06-22T18:45:33.670 回答