最大化支出并将成本保持在 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 上或更广泛的互联网上找到一些很棒的资源。

Answer 2

您可以使用Integer Programming来解决问题。这是 Python 中使用 PuLP 库的完整解决方案：

import pulp

# Input parameters
nodes = [(10, 8), (7, 8), (6, 7), (5, 3), (11, 14)]

# Cost limit
max_cost = 20

# Create an LP problem object with maximization objective
problem = pulp.LpProblem("Knapsack", pulp.LpMaximize)

# Define decision variables
choices = pulp.LpVariable.dicts("choice", range(len(nodes)), lowBound = 0, upBound = 1, cat = pulp.LpInteger)

# Define optimization function (sum of payoffs)
problem += sum([nodes[i][0] * choices[i] for i in range(len(nodes))])

# Add cost constraint (sum of costs below max_cost)
problem += sum([nodes[i][1] * choices[i] for i in range(len(nodes))]) <= max_cost, "CostConstraint"

# Solve the problem
problem.solve()

# Print the solution
solution = [int(choices[i].value()) for i in range(len(nodes))] 
print(solution)

代码打印：

[1, 1, 0, 1, 0]

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

Maximize Payout & Keep Cost Below X

algorithm

knapsack-problem

minimize

maximize