python - 如何找到不超过某个值的最大项目数？

Question

如何找到不超过某个值的最大项目数？例如，我有 45 个这样的值:1.0986122886681098、1.6094379124341003、3.970291913552122、3.1354942159291497、2.5649493574615367。我需要找到不超过 30.7623 的最大可能组合。

我无法使用蛮力查找所有组合，因为组合的数量会很大。所以我需要使用一些贪心算法。

Answer 1

这是 Knapsack problem 的一个实例.是NP-hard ，因此对于 45 个项目，您必须使用一些启发式算法(例如 Hill Climbing)来找到可接受的估计值。要找到最佳解决方案，您别无选择，只能尝试所有可能性(这是不可行的)。了解您的发行版可能会改变这一点。如果许多项目本身会超过限制，则可以将其丢弃。或者，如果限制非常接近所有数字的总和，您可能只需要最多约 5 个项目的组合即可不包括在内； 45选5还是可行的。