如何找到不超过某个值的最大项目总和？

Question

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

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

Answer 1

这是背包问题的一个例子。它是NP 困难的，因此对于 45 个项目，您必须使用一些启发式算法（例如爬山）来找到可接受的估计。为了找到最佳解决方案，你别无选择，只能尝试所有可能性（这是不可行的）。了解您的发行版可能会改变这一点。如果许多物品本身超出了限制，则可能会被丢弃。或者，如果限制非常接近所有数字的总和，您可能只需要最多大约 5 个项目的组合即可不包含在内；45选5还是可行的。