Я работаю с этим вариантом динамического программирования для решения проблемы с рюкзаком:
KnapsackItem = Struct.new(:name, :cost, :value)
KnapsackProblem = Struct.new(:items, :max_cost)
def dynamic_programming_knapsack(problem)
num_items = problem.items.size
items = problem.items
max_cost = problem.max_cost
cost_matrix = zeros(num_items, max_cost+1)
num_items.times do |i|
(max_cost + 1).times do |j|
if(items[i].cost > j)
cost_matrix[i][j] = cost_matrix[i-1][j]
else
cost_matrix[i][j] = [cost_matrix[i-1][j], items[i].value + cost_matrix[i-1][j-items[i].cost]].max
end
end
end
cost_matrix
end
def get_used_items(problem, cost_matrix)
i = cost_matrix.size - 1
currentCost = cost_matrix[0].size - 1
marked = Array.new(cost_matrix.size, 0)
while(i >= 0 && currentCost >= 0)
if(i == 0 && cost_matrix[i][currentCost] > 0 ) || (cost_matrix[i][currentCost] != cost_matrix[i-1][currentCost])
marked[i] = 1
currentCost -= problem.items[i].cost
end
i -= 1
end
marked
end
Это отлично работает для структуры выше, где вы просто указываете имя, стоимость и ценность. Элементы могут быть созданы следующим образом:
items = [
KnapsackItem.new('david lee', 8000, 30) ,
KnapsackItem.new('kevin love', 12000, 50),
KnapsackItem.new('kemba walker', 7300, 10),
KnapsackItem.new('jrue holiday', 12300, 30),
KnapsackItem.new('stephen curry', 10300, 80),
KnapsackItem.new('lebron james', 5300, 90),
KnapsackItem.new('kevin durant', 2300, 30),
KnapsackItem.new('russell westbrook', 9300, 30),
KnapsackItem.new('kevin martin', 8300, 15),
KnapsackItem.new('steve nash', 4300, 15),
KnapsackItem.new('kyle lowry', 6300, 20),
KnapsackItem.new('monta ellis', 8300, 30),
KnapsackItem.new('dirk nowitzki', 7300, 25),
KnapsackItem.new('david lee', 9500, 35),
KnapsackItem.new('klay thompson', 6800, 28)
]
problem = KnapsackProblem.new(items, 65000)
Теперь проблема заключается в том, что мне нужно добавить позицию для каждого из этих игроков, и я должен позволить алгоритму ранца знать, что ему все еще нужно максимизировать ценность для всех игроков, за исключением того, что существует новое ограничение и это ограничение - каждый игрок имеет позицию, и каждая позиция может быть выбрана только определенное количество раз. Некоторые позиции могут быть выбраны дважды, другие - один раз. Элементами в идеале станут следующие:
KnapsackItem = Struct.new(:name, :cost, :position, :value)
Позиции будут иметь такое ограничение, как:
PositionLimits = Struct.new(:position, :max)
Ограничения будут создаваться, возможно, следующим образом:
limits = [Struct.new('PG', 2), Struct.new('C', 1), Struct.new('SF', 2), Struct.new('PF', 2), Struct.new('Util', 2)]
Что делает это немного сложнее, так это каждый игрок может находиться в позиции Util. Если мы хотим отключить позицию Util, мы просто установим значение 2 в 0.
Наш массив исходных элементов будет выглядеть примерно так:
items = [
KnapsackItem.new('david lee', 'PF', 8000, 30) ,
KnapsackItem.new('kevin love', 'C', 12000, 50),
KnapsackItem.new('kemba walker', 'PG', 7300, 10),
... etc ...
]
Как можно добавить ограничения по положению к алгоритму ранца, чтобы сохранить максимальное значение для предоставленного пула игроков?
