我一直在使用这个变式的动态规划算法来解决背包问题:
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）位置。如果我们想禁用“万能”位置，只需将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 ...
]
如何在背包算法中添加位置限制以便仍然保留提供的球员池的最大价值？