背包问题0-1，固定数量

Question

我正在编写一个带有多个约束条件的背包0-1变体。除了重量约束外，我还有一个数量约束，但在这种情况下，我想解决背包问题，假设我需要在我的背包中恰好有n个物品，并且重量小于或等于W。我目前正在基于Rosetta Code网站上的代码实现针对简单0-1情况的动态规划ruby解决方案。http://rosettacode.org/wiki/Knapsack_problem/0-1#Ruby。

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

- Steven Tang

Answer 1

您可以将表格添加第三个维度：物品数量。每个包括的物品都会在重量维度中增加重量，在数量维度中增加计数。

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

一旦您找到获胜的单元格，您需要向后跟踪到起点（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

- Markus Jarderot

---

谢谢，这很有帮助。但是现在我遇到了一个问题，就是如何遍历cost_matrix以返回已使用项目的列表。您知道如何修改二维情况吗？ - Steven Tang

这个解决方案是否确实限制了恰好 k 个项目？也就是说，它仅解决了最多 k 个项目的约束。 - bernie