我正在查看示例面试问题并弹出。
该问题要求一个程序接受两个数字，L(限制)和 C(要输入的案例数)。然后输入C个整数对，其中整数对由(weight, value)组成。
现在，程序应该给出权重加起来小于或等于限制的最大可能值。
例如，如果有人输入:
(10,4), (5,2), (1,1), (4,9), (5,7)
程序应该输出 17。第一对表示权重限制为 10，并且将输入 4 个测试用例。接下来的四对是测试用例，最理想的组合由最后三个用例组成，因为它们的权重加起来 <= 10，而值的结果是 17，这是给定限制的最高可能值。
我已经尝试了一段时间来解决这个问题，但我没有找到真正有效的解决方案。到目前为止，我采用的方法是找到所有可能的权重加起来小于或等于限制，然后简单地查看它们的所有总和，然后选择最大的。但我觉得这是一个非常低效的解决方案，使用某种排序可能会更好。如有任何建议，我们将不胜感激。
最佳答案
这是 Knapsack Problem 的一个实例.维基百科页面列出了许多可以有效解决此问题的已知算法。您可能想从这些算法中获得一些灵感。
关于java - 给定第一个元素的权重限制，获得对的第二个元素的最大总和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30421734/