python - 0/1 变量很少的背包 : which algorithm?

Question

我必须实现具有约束的 0/1 背包问题的解决方案。在大多数情况下，我的问题的变量很少(~ 10-20，最多 50)。

我记得大学时有很多算法在很多情况下比蛮力表现得更好(例如，我在考虑分支定界算法)。

由于我的问题相对较小，我想知道使用复杂的解决方案而不是蛮力在效率方面是否有明显的优势。

如果有帮助，我正在用 Python 编程。

Answer 1

如果权重之和足够小，您可以使用使用动态规划的伪多项式算法。您只需计算，对于每个 X 和 Y，您是否可以通过前 Y 项获得权重 X。运行时间为 O(NS)，其中 N 是项目数，S 是权重之和。

另一种可能性是使用中间相遇的方法。将项目分成两半，并且:对于前半部分，采用所有可能的项目组合(每半部分有 2^(N/2) 种可能的组合)并将其权重存储在某个集合中。对于下半场，采取所有可能的项目组合，并检查上半场是否有重量合适的组合。这应该在 O(2^(N/2)) 时间内运行。