Максимизируйте выплаты и держите стоимость ниже X

Допустим, у меня есть 100 узлов, каждый из которых состоит из (выплаты, стоимости)

Существует ли алгоритм для поиска узлов X, которые приносят наибольшую выплату без превышения суммы Y?

Я новичок в решении проблем с алгоритмами, и я не уверен, есть ли простой алгоритм сортировки или как-то сделать из него взвешенное дерево (не уверен, как это поможет). Или грубая сила - единственный подход?

Пример:
Мы хотим получить максимальную выплату от 3 узлов, не превышая 20 затрат.

Узлы[] = (10, 8), (7, 8), (6, 7), (5, 3), (11, 14)

Лучший результат: (10, 8), (7, 8), (5, 3)
Выплата = 22
Стоимость = 19


Если вы не знаю ответа, я все равно был бы признателен, если бы вы могли указать мне правильное направление с точки зрения терминологии, например, к какой категории алгоритма он может относиться или что мне следует исследовать. Спасибо!


algorithm knapsack-problem minimize maximize
person Corey    schedule 08.11.2017    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Это известная проблема под названием проблема с рюкзаком 0/1, и существует множество подходов, которые вы можете использовать для ее решения. Самым простым и одним из самых эффективных решений является алгоритм динамического программирования, который рассматривает элементы по одному. Имея в виду этот термин, я думаю, вы сможете найти отличные ресурсы здесь, в Stack Overflow, или в более широком смысле в Интернете.

person templatetypedef    schedule 08.11.2017

arrow_upward
0
arrow_downward

Вы можете использовать целочисленное программирование, чтобы решить эту проблему. Вот полное решение на 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]
person Bolo    schedule 22.04.2018