数量固定的背包0

本文介绍了数量固定的背包0-1的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在写有多个约束的背包0-1的变体。除了权重约束外，我还具有数量约束，但是在这种情况下，我想解决背包问题，因为我的背包中必须正好有n个物品，重量小于或等于W。目前，我正在根据 rosettacode/wiki/Knapsack_problem/0-1#Ruby 。

I'm writing a variation of knapsack 0-1 with multiple constraints. In addition to a weight constraint I also have a quantity constraint, but in this case I want to solve the knapsack problem given that I'm required to have exactly n items in my knapsack, with a weight less than or equal to W. I'm currently implementing a dynamic programming ruby solution for the simple 0-1 case based off of the code at Rosetta Code at rosettacode/wiki/Knapsack_problem/0-1#Ruby.

实现固定数量的最佳方法是什么

What's the best way to implement the fixed quantity constraint?

推荐答案

您可以在表格中添加第三个维度：项目数。

You could add a third dimension to the table: Number of items. Each item included adds both weight in the weight-dimension, and count in the count-dimension.

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 和 k ，并找到具有最大值的单元格。

To find the solution (which items to pick), you need to look at the grid cost_matrix[num_items-1][j][k], for all values of j and k, and find the cell with maximum value.

找到获胜单元格后，您需要向后追溯开始（ i = j = k = 0 ）。在您检查的每个单元格上，都需要确定是否使用项目 i 到达此处。

Once you find the winning cell, you need to trace backwards towards the start (i = j = k = 0). On each cell you examine, you need to determine if item i was used to get here or not.

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