01背包

问题简述

给定最多能容纳 V 体积的背包，和 n 个物品，每个物品有重量(w)和体积(v)两个属性；
求背包能放的最大重量；
每个物品的重量(w)和体积(v)保存在数组 vw 中；

示例1：
    输入：10,2,[[1,3],[10,4]]
    返回：4
示例2：
    输入：10,2,[[1,3],[9,8]]
    返回：11

01背包_牛客题霸_牛客网

总结

• 熟练掌握思路 1 的优化路径（解新题）；

• 牢记 01 背包的一维转移方程：

  • 优化目标是最大重量：dp[i] = max(dp[i], dp[i - v[i]] + w[i])

  • 优化目标是最小空间：dp[i] = min(dp[i], dp[i - w[i]] + v[i])

思路1：暴力递归+记忆化搜索 -> 动态规划

Python：写法1）暴力递归+记忆化搜索

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算01背包问题的结果
# @param V int整型 背包的体积
# @param n int整型 物品的个数
# @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
# @return int整型
#
class Solution:
    def knapsack(self , V: int, n: int, vw: List[List[int]]) -> int:
        # write code here
        import sys
        sys.setrecursionlimit(1010)  # 解除递归深度限制
        
        # 记忆空间
        dp = dict()
        
        # 剩余空间为 rest 的情况下，前 i 个物品能装载的最大值
        def dfs(i, rest):
            if (i, rest) in dp:
                return dp[(i, rest)]
            
            # 递归基
            if i == 0:
                return 0
            
            # 不拿第 i 个物品
            r1 = dfs(i - 1, rest)
            # 拿第 i 个物品，前提是空间足够
            r2 = 0
            if rest >= vw[i - 1][0]:  # 注意第 i 个物品第下标是 i-1，这里最容易犯错
                r2 = dfs(i - 1, rest - vw[i - 1][0]) + vw[i - 1][1]
            
            # 记忆
            dp[(i, rest)] = max(r1, r2)
            return dp[(i, rest)]
        
        return dfs(n, V)  # 因为下标从 0 开始，所以第 n 个物品的下标为 n-1

Python：写法2）使用标准库提供的缓存（爆栈）

• 不知道什么原因无法通过最长的用例，好像 lru_cache 和 setrecursionlimit 不能同时生效；

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算01背包问题的结果
# @param V int整型 背包的体积
# @param n int整型 物品的个数
# @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
# @return int整型
#
class Solution:
    def knapsack(self , V: int, n: int, vw: List[List[int]]) -> int:
        # write code here
        from functools import lru_cache
        import sys
        sys.setrecursionlimit(1010)  # 解除递归深度限制
        
        # 剩余空间为 rest 的情况下，前 i 个物品能装载的最大值
        @lru_cache(maxsize=None)
        def dfs(i, rest):
            if i == -1:  # 因为下标从 0 开始，所以递归基设为 -1
                return 0
            
            # 不拿第 i 个物品
            r1 = dfs(i - 1, rest)
            # 拿第 i 个物品，前提是空间足够
            r2 = 0 if rest < vw[i][0] else dfs(i - 1, rest - vw[i][0]) + vw[i][1]

            return max(r1, r2)
        
        return dfs(n - 1, V)  # 因为下标从 0 开始，所以第 n 个物品的下标为 n-1

Python：写法3）将暴力递归转成动态规划

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算01背包问题的结果
# @param V int整型 背包的体积
# @param n int整型 物品的个数
# @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
# @return int整型
#
class Solution:
    def knapsack(self , V: int, n: int, vw: List[List[int]]) -> int:
        # write code here
        
        dp = [[0] * (V + 1) for _ in range(n + 1)]
        # 对应递归基：剩余容量为 V 时前 0 个物品的最大重量
        dp[0][V] = 0
        
        for i in range(1, n + 1):
            for rest in range(V + 1):  # 这里正序逆序遍历都可以
                # 与 dfs 的过程一一对应
                r1 = dp[i - 1][rest]
                r2 = 0
                if rest >= vw[i - 1][0]:
                    r2 = dp[i - 1][rest - vw[i - 1][0]] + vw[i - 1][1]
                dp[i][rest] = max(r1, r2)
        
        return dp[n][V]

思路2：一维 dp（内存优化）

• 因为每次更新第 i 行数据时，只与 i-1 行有关，所以可以使用一维数组优化；

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算01背包问题的结果
# @param V int整型 背包的体积
# @param n int整型 物品的个数
# @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
# @return int整型
#
class Solution:
    def knapsack(self , V: int, n: int, vw: List[List[int]]) -> int:
        # write code here
        
        dp = [0] * (V + 1)
        dp[0] = 0  # 可以省略
        
        for i in range(1, n + 1):
            for rest in range(V, vw[i - 1][0] - 1, -1):
                # 不拿第 i 个物品
                r1 = dp[rest]
                # 拿第 i 个物品
                r2 = dp[rest - vw[i - 1][0]] + vw[i - 1][1]
                # 取较大的
                dp[rest] = max(r1, r2)
        
        return dp[V]

为什么一维 dp 中要逆序遍历体积？

二维状态的转移方程：dp[i][j]=max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]); 一维状态的转移方程：dp[j]=max(dp[j], dp[j-v[i]] + w[i]);

可以看到二维中更新第 i 层数据用的都是 i - 1 层的数据，因为第 i - 1 层的数据已经固定，所以正序逆序遍历都无所谓；而如果在一维状态中正序遍历，那么 dp[j-v[i]] 会在 dp[j] 前被更新，导致 dp[j] 得到错误的答案；

关于01背包和完全背包的优化的体积顺序问题_听-起风了的博客-CSDN博客

思路3：另一种尝试

• 思路 1 是最直观的尝试方法；但存在一个问题，就是当 V 非常大时，可能会超时；

• 此时可以尝试另一个递推思路，定义 dp[i][w] 表示前 i 个物品达到重量为 w 时需要的最小空间；

• 最后的答案为满足 dp[n][w] <= V 时最大的 w；

• 事实上，对比后可以发现两者的转移方程非常相似：

  • 最大重量：dp[i] = max(dp[i], dp[i - v[i]] + w[i])

  • 最小空间：dp[i] = min(dp[i], dp[i - w[i]] + v[i])

Python：写法1）二维 dp

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算01背包问题的结果
# @param V int整型 背包的体积
# @param n int整型 物品的个数
# @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
# @return int整型
#
class Solution:
    def knapsack(self , V: int, n: int, vw: List[List[int]]) -> int:
        # write code here
        
        # 重量上限，即所有物品的重量和
        W = sum(it[1] for it in vw)
        
        # 初始化为无穷大
        #   也可以初始化为 -1，表示不能达到的重量，但是没有直接初始化为无穷大方便；
        dp = [[float('inf')] * (W + 1) for _ in range(n + 1)]
        dp[0][0] = 0  # 重量为 0 所需的最小空间也是 0
            
        for i in range(1, n + 1):
            for w in range(W + 1):
                r1 = dp[i - 1][w]
                r2 = float('inf')
                if w - vw[i - 1][1] >= 0:
                    r2 = dp[i - 1][w - vw[i - 1][1]] + vw[i - 1][0]
                dp[i][w] = min(r1, r2)
            
        for w in range(W, -1, -1):
            if dp[n][w] <= V:
                return w
            
        return 0

Python：写法2）一维 dp

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算01背包问题的结果
# @param V int整型 背包的体积
# @param n int整型 物品的个数
# @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
# @return int整型
#
class Solution:
    def knapsack(self , V: int, n: int, vw: List[List[int]]) -> int:
        # write code here
        
        # 最大重量
        W = sum(it[1] for it in vw)
        
        # 初始化为无穷大
        dp = [float('inf')] * (W + 1)
        dp[0] = 0  # 重量为 0 所需的最小空间也是 0
            
        for i in range(1, n + 1):
            for w in range(W, vw[i - 1][1] - 1, -1):
                dp[w] = min(dp[w], dp[w - vw[i - 1][1]] + vw[i - 1][0])
        
        # 逆序遍历 S，当找到需要的最小体积相遇等于 V 时，此时的 w 就是最大重量
        for w in range(W, -1, -1):
            if dp[w] <= V:
                return w
            
        return 0

代码验证

• 因为上面一些代码不能通过 OJ，所以离线写了一个对数器验证正确性（假设能通过 OJ 的 Solution1 是正确的）；

Python

from typing import *


class Solution1:
    def knapsack(self, V: int, n: int, vw: List[List[int]]) -> int:
        # write code here

        dp = [[0] * (V + 1) for _ in range(n + 1)]
        # 对应递归基：剩余容量为 V 时前 0 个物品的最大重量
        dp[0][V] = 0

        for i in range(1, n + 1):
            for rest in range(V + 1):  # 这里正序逆序遍历都可以
                # 与 dfs 的过程一一对应
                r1 = dp[i - 1][rest]
                r2 = 0
                if rest >= vw[i - 1][0]:
                    r2 = dp[i - 1][rest - vw[i - 1][0]] + vw[i - 1][1]
                dp[i][rest] = max(r1, r2)

        return dp[n][V]


class Solution2:
    def knapsack(self, V: int, n: int, vw: List[List[int]]) -> int:
        # write code here

        dp = [0] * (V + 1)
        dp[0] = 0  # 可以省略

        for i in range(1, n + 1):
            for rest in range(V, vw[i - 1][0] - 1, -1):
                # 不拿第 i 个物品
                r1 = dp[rest]
                # 拿第 i 个物品
                r2 = dp[rest - vw[i - 1][0]] + vw[i - 1][1]
                # 取较大的
                dp[rest] = max(r1, r2)

        return dp[V]


class Solution3:
    def knapsack(self, V: int, n: int, vw: List[List[int]]) -> int:
        # write code here

        # 最大重量
        W = sum(it[1] for it in vw)

        # 初始化为无穷大
        dp = [[float('inf')] * (W + 1) for _ in range(n + 1)]
        dp[0][0] = 0  # 重量为 0 所需的最小空间也是 0

        for i in range(1, n + 1):
            for w in range(W + 1):
                r1 = dp[i - 1][w]
                r2 = float('inf')
                if w - vw[i - 1][1] >= 0:
                    r2 = dp[i - 1][w - vw[i - 1][1]] + vw[i - 1][0]
                dp[i][w] = min(r1, r2)

        for w in range(W, -1, -1):
            if dp[n][w] <= V:
                return w

        return 0


class Solution4:
    def knapsack(self, V: int, n: int, vw: List[List[int]]) -> int:
        # write code here

        # 最大重量
        W = sum(it[1] for it in vw)

        # 初始化为无穷大
        dp = [float('inf')] * (W + 1)
        dp[0] = 0  # 重量为 0 所需的最小空间也是 0

        for i in range(1, n + 1):
            for w in range(W, vw[i - 1][1] - 1, -1):
                dp[w] = min(dp[w], dp[w - vw[i - 1][1]] + vw[i - 1][0])

        # 逆序遍历 S，当找到需要的最小体积相遇等于 V 时，此时的 w 就是最大重量
        for w in range(W, -1, -1):
            if dp[w] <= V:
                return w

        return 0


def random_input():
    import random
    MAX = 1000

    V = random.randint(1, MAX)
    n = random.randint(1, 100)  # 因为 方法 3, 4 比较慢，所以控制一下 n 的范围

    vw = []
    for _ in range(n):
        v, w = random.randint(1, MAX), random.randint(1, MAX)
        vw.append([v, w])

    return V, n, vw


def _test():
    """"""
    for _ in range(10):
        V, n, vw = random_input()
        r1 = Solution1().knapsack(V, n, vw)
        r2 = Solution2().knapsack(V, n, vw)
        r3 = Solution3().knapsack(V, n, vw)
        r4 = Solution4().knapsack(V, n, vw)

        assert r1 == r2 == r3 == r4


if __name__ == '__main__':
    """"""
    _test()