0/1具有整数值和无理权重的背包？

标准0/1背包问题本身借给简单DP溶液：与n与无理值，整数权重和的W一个最大重量不同的对象，使一个n x W阵列m并让m[i, j]与项可达到的最大数值1至i并且最多重量为j。0/1具有整数值和无理权重的背包？

我试图解决的权重是非理性的，但价值观是合理的问题。我被告知有一个O(nV)解决方案，其中V是所有值的总和。我想说的是这样的：让m为n x V数组，并且让m[i, j]为最小可能的权重，以使项目1至i的值至少达到j。这将产生类似以下内容：

def knapsack(weights, values, max_weight): 
    max_v = sum(values) 
    m = [[0 for _ in range(max_v)] for _ in weights] 

    for i in range(len(weights)): 
     for j in range(max_v): 
      if j < values[i]: 
       m[i][j] = m[i - 1][j] 
      else: 
       m[i][j] = min(m[i - 1][j], weights[i] + m[i - 1][j - values[i]]) 

    for val, col in reversed(enumerate(zip(*m))): 
     wt = min(col) 
     if wt <= max_weight: 
      return col 

    return 0

但是，这并不工作：像m[0, 100]细胞得到与向下传播毫无意义的垃圾初始化。我不知道如何解决这个问题，我找不到任何信息。它看起来像this question会提供一种算法来填充每个单元格，但是要调用每个单元格会太昂贵。

来源

2015-01-14 Patrick Collins

这是一个错字，“权重是非理性的，但权重是合理的”，你也可以举一个小例子吗？ – sashas

是的，我的错误。我也意外删除了我的破解解决方案中的一些代码。 –

@ PM2Ring不，目前还没有，我不认为我使用任何特定的numpy？尽管如此，我可能犯了一个错误。 –

让我们将m的含义更改为恰好给定值的最小权重。然后，我们要像

m = [[(float('inf') if j else 0) for j in range(max_v + 1)] for _ in range(len(weights) + 1)]

初始化在那里我使用正无穷大不可行的标志（我也是固定的两断接一个表中的尺寸误差）。然后循环可以看起来像这样（未经测试）。

for i in range(len(weights)): 
    for j in range(max_v + 1): 
     if j >= values[i]: 
      m[i + 1][j] = min(m[i][j], m[i][j - values[i]] + weights[i]) 
     else: 
      m[i + 1][j] = m[i][j]

然后我们必须调整输出提取以反映m的新定义。

来源

2015-01-14 12:51:30

0/1具有整数值和无理权重的背包？

回答

相关问题