背包：如何将物品类型添加到现有解决方案中

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

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

 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)

现在，我面临的问题是，我需要为每个玩家添加一个位置，我必须让背包算法知道，它仍然需要在所有玩家中最大化价值，除了有一个新的限制，该限制是每个玩家都有一个位置，每个位置只能被选择一定的次数。有些职位可以选择两次，有些职位可以选择一次。理想情况下，物品应为：

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位置，只需将2设置为0。

我们最初的items数组如下所示：

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

该问题类似于约束车辆路径问题。你可以尝试一种启发式算法，比如Clarke的saving算法

Answer 2

据我所知，您指定的附加约束如下：

应有一组元素，在溶液中最多只能选择k（k=1或2）个元素。此类装置应为多套。

我想到了两种方法，但都不够有效。

方法1：

>

将元素分成位置组。因此，如果有5个位置，则每个元素都应分配给5个组中的一个。

通过从每个组中选择1（或2）个元素并检查总价值和成本，迭代（或重复）所有组合。有很多方法可以让你了解一些组合。例如，在一个组中，如果有两个元素，其中一个以较小的成本提供更多的价值，那么另一个可以从所有解决方案中拒绝。

方法2：

Mixed Integer Linear Programming Approach.

将问题表述如下：

Maximize summation (ViXi) {i = 1 to N} 
where Vi is value and 
Xi is a 1/0 variable denoting presence/absence of an element from the solution.

Subject to constraints:
summation (ciXi) <= C_MAX {total cost}
And for each group:
summation (Xj) <= 1 (or 2 depending on position)
All Xi = 0 or 1.

然后你必须找到一个解算器来解上面的MILP。

Answer 3

ruby中有一些高效的库可以满足您的任务，很明显，您正在寻找一些基于约束的优化，ruby中有一些库是开源的，可以免费使用，只需将它们包含在您的项目中即可。你所需要做的就是从你的约束中生成线性规划模型目标函数，库的优化器会生成满足你所有约束的解，或者说如果给定的约束中没有任何结论，就不存在解。

ruby中提供的一些这样的库包括

• RGLPK
• OPL
• LP求解

OPL遵循类似于IBM CPLEX的LP语法，后者是广泛使用的优化软件，因此您可以获得关于如何使用它对LP建模的良好参考，而且这是在RGLPK之上构建的。