java - 给定第一个元素的权重限制，获得对的第二个元素的最大总和

Question

我正在查看示例面试问题并弹出。

该问题要求一个程序接受两个数字，L(限制)和 C(要输入的案例数)。然后输入C个整数对，其中整数对由(weight, value)组成。

现在，程序应该给出权重加起来小于或等于限制的最大可能值。

例如，如果有人输入:

(10,4),(5,2),(1,1),(4,9),(5,7)

程序应该输出 17。第一对表示权重限制为 10，并且将输入 4 个测试用例。接下来的四对是测试用例，最理想的组合由最后三个用例组成，因为它们的权重加起来 <= 10，而值的结果是 17，这是给定限制的最高可能值。

我已经尝试了一段时间来解决这个问题，但我没有找到真正有效的解决方案。到目前为止，我采用的方法是找到所有可能的权重加起来小于或等于限制，然后简单地查看它们的所有总和，然后选择最大的。但我觉得这是一个非常低效的解决方案，使用某种排序可能会更好。如有任何建议，我们将不胜感激。

Answer 1

这是 Knapsack Problem 的一个实例.维基百科页面列出了许多可以有效解决此问题的已知算法。您可能想从这些算法中获得一些灵感。