ruby - 背包 : how to add item type to existing solution

Question

我一直在使用动态规划的这种变体来解决背包问题:

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

这对于上面的结构非常有效，您只需提供名称、成本和值(value)。项目可以像下面这样创建:

 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)

现在，我遇到的问题是我需要为这些玩家中的每一个添加一个位置，并且我必须让背包算法知道它仍然需要最大化所有玩家的值(value)，除非有一个新的限制而那个限制就是每个玩家都有一个位置，每个位置只能选择一定的次数。有些位置可以选择两次，有些位置可以选择一次。理想情况下，项目会变成这样:

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 ...
        ]

如何将位置限制添加到背包算法中，以便仍然保留提供的玩家池的最大值？

Answer 1

ruby 中有一些高效的库可以满足您的任务，很明显您正在寻找一些 constrain based optimization ，ruby 中有一些库是开源的，因此可以免费使用，只需将它们包含在您的项目中即可。您需要做的就是生成 Linear programming在您的约束之外建模目标函数，库的优化器将生成满足您所有约束的解决方案，或者如果无法从给定的约束得出任何结论，则表示不存在解决方案。

ruby 中可用的一些此类库是

• RGLPK
• OPL
• LP Solve

OPL 遵循类似于 IBM CPLEX 的 LP 语法，这是一种广泛使用的优化软件，因此您可以很好地引用如何使用它对 LP 建模，而且它是建立在 RGLPK 之上的。