DSA 0/1 背包问题

0/1 背包问题

0/1 背包问题是指，你有一个背包，它有一个重量限制，你身处一个满是宝藏的房间里，每个宝藏都有价值和重量。

为了解决 0/1 背包问题，你必须找出哪些宝藏要装进背包，以最大限度地提高总价值，同时保持在背包的重量限制内。

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

1

2

3

背包

$ {{ totalValue }}

{{ totalWeight }}/{{limit}} kg

{{ item.name }}

$ {{ item.value }}

{{ item.weight }} kg

你能手动解决上面的 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) 被调用了 2 次。我们可以通过使用记忆化 来避免这种情况。

记忆化方法（自顶向下）

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

在此处阅读更多关于记忆化的内容 此处。

记忆化是一种“自顶向下”的方法，因为它从解决问题开始，并逐步向下解决越来越小的子问题。

在上面的蛮力示例中，相同的函数调用只发生了几次，因此使用记忆化带来的影响并不大。但在其他具有更多要选择的物品的示例中，记忆化技术会更有帮助。

在通过使用记忆化改进蛮力实现之后，代码现在看起来像这样

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 kg：对于第一个计算的值，检查显微镜是否可以在重量限制为 1 kg 的情况下放入包中。显微镜的重量为 2 kg，太重了，因此从上面对应的没有物品的背包的单元格复制值 0。只考虑一个重量限制为 1 kg 的包中的显微镜，这意味着我们不能带任何物品，我们必须空手而归，总价值为 0 美元。

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

地球仪，容量 1 kg：考虑一个重量为 1 kg 且背包容量为 1 kg 的地球仪，这意味着我们可以携带地球仪，因此价值为 200 美元。代码找到携带地球仪（给我们 200 美元）和先前计算的 1 kg 容量的值（从上面的单元格中获得的 0 美元）之间的最大值。在这种情况下，很明显我们应该携带地球仪，因为它是唯一重量这么低的物品，但在其他情况下，先前在相同容量下计算的值可能更高。

地球仪，容量 2 kg：在 2 kg 容量下，代码发现地球仪可以放入，这给我们 200 美元的价值，但显微镜无法放入。将显微镜添加到 2 kg 容量中，得到 300 美元的价值，这更高，所以选择显微镜（上面的单元格的值）来最大化此表格单元格的背包价值。

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

哪些物品能给我们最大的价值？

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

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

下面是使用分步方法找到包含物品的图表

这就是找到包含物品的方式

1. 右下角的值是 1200，上面的单元格是 900。这两个值不同，这意味着王冠已包含。
2. 我们转到的下一个单元格位于上面的行，并向左移动与王冠重量相同的次数，即向左移动 3 个位置到值为 700 的单元格。
3. 我们所在的单元格现在值为 700，上面的单元格值为 500。这两个值不同，这意味着当前行的物品已包含：杯子。
4. 杯子的重量为 5 kg，因此我们转到的下一个单元格位于上面的行，向左移动 5 个位置，到值为 300 的单元格，位于考虑地球仪的行。
5. 上面的单元格具有相同的值 300，这意味着地球仪未包含，我们转到的下一个单元格是上面的单元格，值为 300，位于考虑显微镜的行。
6. 由于上面的单元格与当前值为 300 的单元格不同，这意味着显微镜已包含。
7. 我们转到的下一个单元格位于上面的行，向左移动 2 个位置，因为显微镜为 2 kg。
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\) 是背包容量，但内存使用和运行方式更可预测，这通常使得表格法成为最有利的方法。