algorithm - 最大化支出并将成本保持在 X 以下

Question

假设我有 100 个节点，每个节点包含(支出，成本)

是否有一种算法可以在成本不超过 Y 金额的情况下找到产生最多支出的 X 个节点？

我不确定是否有简单的排序算法或以某种方式从中生成加权树。还是暴力破解是唯一的方法？

示例:
我们希望在不超过 20 成本的情况下从 3 个节点获得最佳支出

节点[] = (10, 8), (7, 8), (6, 7), (5, 3), (11, 14)

最佳结果:(10, 8), (7, 8), (5, 3)
支出 = 22
成本 = 19

Answer 1

这是一个名为 0/1 knapsack problem 的著名问题，并且有很多方法可以用来解决它。最简单且最有效的解决方案之一是动态规划算法，它一次只考虑一个元素。记住这个术语，我认为您应该能够在 Stack Overflow 上或更广泛的互联网上找到一些很棒的资源。