DSA 0/1 背包问题

0/1 背包问题

0/1 背包问题是指您有一个有重量限制的背包，并且您身处一个装满宝藏的房间，每个宝藏都有其价值和重量。

要解决 0/1 背包问题，您必须找出要装哪些宝藏才能使总价值最大化，同时保持低于背包的重量限制。

太棒了！您找到了能带来最大价值的物品😀

1

2

3

背包

$ {{ totalValue }}

{{ totalWeight }}/{{limit}} 公斤

{{ item.name }}

$ {{ item.value }}

{{ item.weight }} 公斤

您能手动解决上面的 0/1 背包问题吗？继续阅读以了解解决 0/1 背包问题的不同实现方式。

解决 0/1 背包问题有助于企业在预算内决定资助哪些项目，从而在不超支的情况下实现利润最大化。它还用于物流中，以优化货物装载到卡车和飞机上，确保在不超过重量限制的情况下包含最有价值或优先级最高的物品。

暴力破解法

使用暴力破解法意味着检查所有可能性，寻找最佳结果。这通常是解决问题最直接的方法，但也需要最多的计算。

使用暴力破解法解决 0/1 背包问题意味着：

1. 计算背包中每种可能物品组合的价值。
2. 丢弃超过背包重量限制的组合。
3. 选择总价值最高的物品组合。

这种解决 0/1 背包问题的暴力破解法可以这样实现：

def knapsack_brute_force(capacity, n):
    print(f"knapsack_brute_force({capacity},{n})")
    if n == 0 or capacity == 0:
        return 0

    elif weights[n-1] > capacity:
        return knapsack_brute_force(capacity, n-1)

    else:
        include_item = values[n-1] + knapsack_brute_force(capacity-weights[n-1], n-1)
        exclude_item = knapsack_brute_force(capacity, n-1)
        return max(include_item, exclude_item)

values = [300, 200, 400, 500]
weights = [2, 1, 5, 3]
capacity = 10
n = len(values)

print("\nMaximum value in Knapsack =", knapsack_brute_force(capacity, n))

运行上述代码意味着 knapsack_brute_force 函数会被多次递归调用。您可以从所有打印输出中看到这一点。

每次调用函数时，它都会包含当前项 n-1 或不包含。

第 2 行：此打印语句向我们显示了函数每次被调用的情况。

第 3-4 行：如果物品已用完 (n==0) 或容量已用完 (capacity==0)，则不再进行递归调用，因为此时不能再向背包中添加物品。

第 6-7 行：如果当前物品比容量重 (weights[n-1] > capacity)，则放弃当前物品并转到下一个物品。

第 10-12 行：如果当前物品可以添加到背包中，则查看哪种情况能带来最高价值：添加当前物品，或不添加当前物品。

运行代码示例会创建一个递归树，如下所示，每个灰色框表示一次函数调用。

从上面的递归树中可以看出，例如，如果拿走皇冠、杯子和地球仪，则显微镜（2公斤）就没有空间了，这会给我们带来 200+400+500=1100 的总价值。

我们还可以看到，只拿显微镜会给我们带来 300 的总价值（右下角的灰色框）。

正如您在上面的递归树中以及通过运行示例代码所看到的，函数有时会以相同的参数被调用，例如 knapsack_brute_force(2,0) 就被调用了两次。我们通过使用记忆化来避免这种情况。

记忆化方法（自上而下）

记忆化技术将之前的函数调用结果存储在一个数组中，这样就可以从该数组中获取之前的结果，而无需再次计算。

在此处阅读更多关于记忆化的信息。

记忆化是一种“自上而下”的方法，因为它通过分解为越来越小的子问题来开始解决问题。

在上面的暴力破解示例中，相同的函数调用只发生了几次，所以使用记忆化的效果不是很大。但在其他有更多物品可供选择的示例中，记忆化技术将更有帮助。

在用记忆化改进了暴力破解实现之后，代码现在看起来像这样：

def knapsack_memoization(capacity, n):
    print(f"knapsack_memoization({n}, {capacity})")
    if memo[n][capacity] is not None:
        print(f"Using memo for ({n}, {capacity})")
        return memo[n][capacity]
    
    if n == 0 or capacity == 0:
        result = 0
    elif weights[n-1] > capacity:
        result = knapsack_memoization(capacity, n-1)
    else:
        include_item = values[n-1] + knapsack_memoization(capacity-weights[n-1], n-1)
        exclude_item = knapsack_memoization(capacity, n-1)
        result = max(include_item, exclude_item)

    memo[n][capacity] = result
    return result

values = [300, 200, 400, 500]
weights = [2, 1, 5, 3]
capacity = 10
n = len(values)

memo = [[None]*(capacity + 1) for _ in range(n + 1)]

print("\nMaximum value in Knapsack =", knapsack_memoization(capacity, n))

上面代码中高亮显示的部分展示了用于改进之前暴力破解实现的记忆化技术。

第 24 行：创建一个数组 memo 来存储之前的结果。

第 3-5 行：在函数开始时，在进行任何计算或递归调用之前，检查结果是否已找到并存储在 memo 数组中。

第 16 行：存储结果以备后用。

列表法（自下而上）

解决 0/1 背包问题的另一种技术是使用一种称为列表法的方法。这种方法也称为迭代法，是动态规划中使用的一种技术。

列表法以自下而上的方式解决问题，首先用最基本的子问题的结果填充表格。然后使用之前的结果填充下一个表格值。

使用下面的动画来查看表格是如何逐格填充的，使用之前计算的值，直到得出最终结果。

列表法通过一次考虑一件物品，并逐步增加背包容量来工作。通过这种方式，通过首先解决最基本的子问题来构建解决方案。

在每一行，都会考虑将一件物品添加到背包中，并增加容量。

def knapsack_tabulation():
    n = len(values)
    tab = [[0]*(capacity + 1) for y in range(n + 1)]

    for i in range(1, n+1):
        for w in range(1, capacity+1):
            if weights[i-1] <= w:
                include_item = values[i-1] + tab[i-1][w-weights[i-1]]
                exclude_item = tab[i-1][w]
                tab[i][w] = max(include_item, exclude_item)
            else:
                tab[i][w] = tab[i-1][w]
    
    for row in tab:
    	  print(row)
    return tab[n][capacity]

values = [300, 200, 400, 500]
weights = [2, 1, 5, 3]
capacity = 10
print("\nMaximum value in Knapsack =", knapsack_tabulation())

第 7-10 行：如果物品重量小于容量，则表示可以添加该物品。检查添加它是否会获得比上一行（表示不添加该物品）计算出的结果更高的总价值。使用这两个值中的最高值 (max)。换句话说：选择带走或不带走当前物品。

第 8 行：这一行可能最难理解。要找到与添加当前物品相对应的价值，我们必须使用 values 数组中当前物品的价值。但除此之外，我们必须用当前物品的重量减少容量，以查看剩余容量是否能给我们带来任何额外价值。这类似于检查除了当前物品之外是否可以添加其他物品，并添加这些物品的价值。

第 12 行：如果当前物品比容量重（太重），则只需填入上一行的值，这表示不添加当前物品。

手动演练

以下是关于表格中一些值如何计算的解释列表。您可以在阅读时点击上面动画中相应的表格单元格以获得更好的理解。

显微镜，容量 1 公斤：对于计算出的第一个值，检查在重量限制为 1 公斤的情况下，显微镜是否可以放入袋中。显微镜重 2 公斤，太重了，所以值 0 直接从上面单元格中复制，表示背包中没有物品。只考虑一个重量限制为 1 公斤的袋子中的显微镜，意味着我们不能带任何物品，必须空手而归，总价值为 0 美元。

显微镜，容量 2 公斤：对于计算出的第二个值，我们能够将显微镜放入重量限制为 2 公斤的袋子中，所以我们可以带上它，袋子中的总价值是 300 美元（显微镜的价值）。对于更高的背包容量，只考虑显微镜，意味着我们可以带上它，所以该行中的所有其他值都是 300 美元。

地球仪，容量 1 公斤：考虑一个重 1 公斤的地球仪和一个容量为 1 公斤的背包，这意味着我们可以带走地球仪，因此价值为 200 美元。代码会找出带走地球仪（价值 200 美元）与之前计算出的 1 公斤容量下的价值（0 美元，来自上方单元格）中的最大值。在这种情况下，很明显我们应该带走地球仪，因为它是唯一重量如此低的物品，但在其他情况下，之前在相同容量下计算出的价值可能更高。

地球仪，容量 2 公斤：在容量为 2 公斤时，代码发现地球仪可以装下，这给了我们 200 美元的价值，但显微镜就装不下了。而如果装下显微镜（容量为 2 公斤）则会给我们带来 300 美元的价值，这更高，所以选择显微镜（来自上方单元格的价值）是最大化此表格单元格背包价值的选择。

地球仪，容量 3 公斤：考虑容量为 3 公斤的地球仪，意味着我们可以带走地球仪，但剩余的 2 公斤容量也可以带走显微镜。在这个单元格中，同时带走地球仪和显微镜会给我们带来更高的价值 200+300=500，而不是只带走显微镜（如上一行计算所示），所以这两个物品都被带走了，单元格值为 500。

哪些物品能给我们带来最高价值？

在填充完表格并找到背包可以拥有的最大值后，我们不清楚需要携带哪些物品才能获得该价值。

为了找到包含的物品，我们使用已创建的表格，并从右下角具有最高值的单元格开始，在我们的例子中是值为 1200 的单元格。

这是使用逐步方法找到包含的物品的图示：

这是找到所含物品的方法

1. 右下角的值是 1200，上面的单元格是 900。值不同，这意味着包含皇冠。
2. 我们要去的下一个单元格在上面一行，我们向左移动与皇冠重量相同的次数，即向左移动 3 个位置到值为 700 的单元格。
3. 我们现在所在的单元格的值是 700，上面单元格的值是 500。值不同，这意味着当前行的物品包含在内：杯子。
4. 杯子重 5 公斤，所以我们去的下一个单元格在上面一行，向左 5 个位置，到值为 300 的单元格，在考虑地球仪的那一行。
5. 由于上方单元格的值与当前值为 300 的单元格相同，这意味着地球仪不包含在内，我们要去的下一个单元格是正上方的显微镜所在的 300 值的单元格。
6. 由于上面的单元格与当前值为 300 的单元格不同，这意味着显微镜已包含在内。
7. 我们要去的下一个单元格在上面一行，向左两个位置，因为显微镜重 2 公斤。
8. 我们到达了左上角的单元格。由于值为 0，表示我们已完成。

当包含这些物品时，我们的 0/1 背包问题具有最大价值：皇冠、杯子和显微镜。

相同的步骤添加到下面的代码中，以找到构成 0/1 背包问题解决方案的物品。

def knapsack_tabulation():
    n = len(values)
    tab = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                include_item = values[i-1] + tab[i-1][w - weights[i-1]]
                exclude_item = tab[i-1][w]
                tab[i][w] = max(include_item, exclude_item)
            else:
                tab[i][w] = tab[i-1][w]

    for row in tab:
        print(row)

    items_included = []
    w = capacity
    for i in range(n, 0, -1):
        if tab[i][w] != tab[i-1][w]:
            items_included.append(i-1)
            w -= weights[i-1]

    print("\nItems included:", items_included)

    return tab[n][capacity]

values = [300, 200, 400, 500]
weights = [2, 1, 5, 3]
capacity = 10
print("\nMaximum value in Knapsack =", knapsack_tabulation())

时间复杂度

解决 0/1 背包问题有三种方法，它们的运行方式和时间复杂度不同。

暴力破解法：这是三种方法中最慢的一种。可能性以递归方式检查，时间复杂度为 \(O(2^n)\)，其中 \(n\) 是我们可以装入的潜在物品数量。这意味着每增加一个需要考虑的物品，计算量就会翻倍。

记忆化方法：通过记忆之前的结果来节省计算，从而获得更好的时间复杂度 \(O(n \cdot C)\)，其中 \(n\) 是物品数量，\(C\) 是背包容量。此方法以与暴力破解法相同的递归方式运行。

列表法：时间复杂度与记忆化方法相同，为 \(O(n \cdot C)\)，其中 \(n\) 是物品数量，\(C\) 是背包容量，但内存使用和运行方式更具可预测性，这通常使得列表法最受青睐。