0/1 具有整数值和非理性重量的背包？

Question

标准的 0/1 背包问题适用于一个简单的 DP 解决方案：使用 n 个具有非理性值、整数权重和最大重量 W 的不同对象，制作一个 n x W 数组 m 并设 m[i, j] 为项目 1 到 i 可达到的最大值，权重至多为 j。

我正在尝试解决权重不合理但值合理的问题。有人告诉我有一个 O(nV) 解决方案，其中 V 是所有值的总和。我想这样说：设 m 为 n x V 数组，设 m[i, j] 为项目 1 至少达到 j 值的最小可能权重至 i。这将产生如下内容：

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 会提供一种算法来填充每个单元格，但是调用每个单元格的成本太高了。

Answer 1

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

这样的初始化

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

我使用正无穷大作为不可行的标记（我还修复了 table 大小中的两个差一错误）。然后循环看起来像这样（未经测试）。

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 的新定义。

0/1 具有整数值和非理性重量的背包？

0/1 Knapsack with integer values and irrational weights?

python

algorithm

knapsack-problem