我正在编写具有多个约束的背包 0-1 的变体。除了重量约束之外,我还有数量约束,但在本例中,我想解决背包问题,因为我的背包中需要恰好有 n 件物品,且重量小于或等于 W。目前正在为简单的 0-1 案例实现动态编程 ruby 解决方案,基于 Rosetta Code 中的代码http://rosettacode.org/wiki/Knapsack_problem/0-1#Ruby http://rosettacode.org/wiki/Knapsack_problem/0-1#Ruby.
实施固定数量限制的最佳方式是什么?
您可以向表中添加第三个维度:项目数。所包含的每个项目都会增加重量维度中的重量和计数维度中的计数。
def dynamic_programming_knapsack(problem)
num_items = problem.items.size
items = problem.items
max_cost = problem.max_cost
count = problem.count
cost_matrix = zeros(num_items, max_cost+1, count+1)
num_items.times do |i|
(max_cost + 1).times do |j|
(count + 1).times do |k|
if (items[i].cost > j) or (1 > k)
cost_matrix[i][j][k] = cost_matrix[i-1][j][k]
else
cost_matrix[i][j][k] = [
cost_matrix[i-1][j][k],
items[i].value + cost_matrix[i-1][j-items[i].cost][k-1]
].max
end
end
end
end
cost_matrix
end
要找到解决方案(选择哪些项目),您需要查看网格cost_matrix[num_items-1][j][k]
,对于所有值j
and k
,并找到具有最大值的单元格。
一旦找到获胜的单元格,您需要向后追踪到开始处(i = j = k = 0
)。在您检查的每个单元格上,您需要确定项目是否i
是否习惯到达这里。
def get_used_items(problem, cost_matrix)
itemIndex = problem.items.size - 1
currentCost = -1
currentCount = -1
marked = Array.new(cost_matrix.size, 0)
# Locate the cell with the maximum value
bestValue = -1
(problem.max_cost + 1).times do |j|
(problem.count + 1).times do |k|
value = cost_matrix[itemIndex][j][k]
if (bestValue == -1) or (value > bestValue)
currentCost = j
currentCount = k
bestValue = value
end
end
end
# Trace path back to the start
while(itemIndex >= 0 && currentCost >= 0 && currentCount >= 0)
if (itemIndex == 0 && cost_matrix[itemIndex][currentCost][currentCount] > 0) or
(cost_matrix[itemIndex][currentCost][currentCount] != cost_matrix[itemIndex-1][currentCost][currentCount])
marked[itemIndex] = 1
currentCost -= problem.items[itemIndex].cost
currentCount -= 1
end
itemIndex -= 1
end
marked
end
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)