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

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

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

如何在背包算法中增加位置限制，以仍然保留所提供球员池的最大值？

最佳答案

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

ruby 中可用的一些此类库是

RGLPK

OPL

LP Solve

OPL遵循类似于IBM CPLEX的LP语法，后者是被广泛使用的优化软件，因此您可以在如何使用LP建模LP上获得很好的引用，而且它是基于RGLPK的。

关于ruby - 背包: how to add item type to existing solution，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19958184/

lp

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