背包问题：寻找Top-K较低利润的解决方案

Question

在经典的0-1背包问题中，我使用以下（动态规划）算法来构造“dp表”：

def knapsack(weights, values, capacity):
    n = len(weights)
    weights = np.concatenate(([0], weights))  # Prepend a zero
    values = np.concatenate(([0], values))    # Prepend a zero
    
    table = np.zeros((n+1, capacity+1), dtype=np.int64)  # The first row/column are zeros
    for i in range(n+1):
        for w in range(capacity+1):
            if i == 0 or w == 0:
                table[i, w] = 0
            elif weights[i] <= w:
                table[i, w] = max(
                    table[i-1, w-weights[i]] + values[i],
                    table[i-1, w]
                )
            else:
                table[i, w] = table[i-1, w]
    return table

然后，通过使用以下代码遍历表格，我就能够识别构成最佳解决方案的项目：

def get_items(weights, capacity, table):
    items = []
    i = len(weights)
    j = capacity
    weights = np.concatenate(([0], weights))  # Prepend a zero
    table_copy = table.copy()
    while i > 0 and j > 0:
        if table_copy[i, j] == table_copy[i-1, j]:
            pass  # Item is excluded
        else:
            items.append(i-1)  # Item is included, fix shifted index due to prepending zero
            j = j - weights[i]
        i = i-1
    return items

这对于查找构成单个最佳解决方案（即最高总和值）的项目非常有用。但是，我似乎不知道如何从该表中检索总重量小于或等于最大容量的前 3 或前 5 个解决方案。

例如，以下输入的前 3 个解决方案是：

weights = [1,  2,  3, 2, 2]
values =  [6, 10, 12, 6, 5]
capacity = 5

# with corresponding "dp table"
array([[ 0,  0,  0,  0,  0,  0],
       [ 0,  6,  6,  6,  6,  6],
       [ 0,  6, 10, 16, 16, 16],
       [ 0,  6, 10, 16, 18, 22],
       [ 0,  6, 10, 16, 18, 22]])

总和值	项目（从零开始的索引）
22	1, 2
22	0,1,3
21	0,1,4

请注意，两个第一名都有平局，因此我们会在前 3 行之后截断解决方案（不过，如果可能的话，最好获得所有平局）。有没有一种有效的方法从“dp表”中获取top-k解？

Answer 1

我会建立一个更丰富的 DP 表。对于每个单元格，您仅存储一个项目集的总价值。相反，我会存储该单元格的前 k 个项目集的信息：总值和索引。以下程序的输出：

22 [1, 2]
22 [0, 1, 3]
21 [0, 1, 4]

这就是我存储在

table[-1][-1]

中的信息。更准确地说，这是我存储在那里的 Python 数据：

[(22, [1, 2]), (22, [0, 1, 3]), (21, [0, 1, 4])]

如果您有很多项目，我认为您可以提高效率并仅存储每个项目集的最后一个索引而不是其所有索引。但随后你必须稍后重建项目集，而我没有心情这样做:-)

完整代码：

import numpy as np

def knapsack(weights, values, capacity, k):
    n = len(weights)
    weights = np.concatenate(([0], weights))  # Prepend a zero
    values = np.concatenate(([0], values))    # Prepend a zero
    
    table = np.zeros((n+1, capacity+1), dtype=object)  # The first row/column are zeros
    for i in range(n+1):
        for w in range(capacity+1):
            if i == 0 or w == 0:
                table[i, w] = [(0, [])]
            elif weights[i] <= w:
                table[i, w] = sorted(
                    [
                        (total + values[i], indices + [i-1])
                        for total, indices in table[i-1, w-weights[i]]
                    ] +
                    table[i-1, w],
                    reverse=True
                )[:k]
            else:
                table[i, w] = table[i-1, w]
    return table[-1][-1]

weights = [1,  2,  3, 2, 2]
values =  [6, 10, 12, 6, 5]
capacity = 5
k = 3

top_k = knapsack(weights, values, capacity, k)

for total, indices in top_k:
    print(total, indices)

在线尝试！