时间戳

首页 > 技术文章 > 动态规划之01背包问题

动态规划之01背包问题

ikventure 2021-06-09 22:57 原文

本文理论内容参考自崔添翼的背包九讲系列。
实例可参考上一篇博物馆大盗问题。

一、01背包问题

有N件物品和一个容量为V的背包，第i件物品的体积为\(v_i\)，价值为\(w_i\)。求解将哪些物品放入背包可以达到总价值最大。

二、基本思路

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即\(F[i,j]\)表示前i件物品放入容量为j的背包，可以获得的最大价值。

状态转移方程：

\[F[i,j] = max\{F[i-1,j], F[i-1,j-v_i] + w_i\} \]

"将前i件物品放入容量为j的背包中"这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只和前i-1件物品相关的问题。

  • 如果不放第i 件物品，那么问题就转化为“前i-1件物品放入容量为j的背包中”，价值为\(F[i-1, j]\)；
  • 如果放第i 件物品，那么问题就转化为“前i-1件物品放入剩下的容量为\(j-v_i\)的背包中”，此时能获得的最大价值就是\(F[i-1,j-v_i]\)再加上通过放入第i 件物品获得的价值\(w_i\).

步骤总结：

  1. 使用一个N*V的二维数组记录dp[i][j]，初始化：dp = [[0 for _ in range(V+1)] for _ in range(N)]
  2. 边界：i=0 或j=0 时，dp[i][j] = 0
  3. 外层循环：i件物品，从1到N循环
  4. 内层循环：容量V，从1到V循环
  5. j < vi时，第i件物品放入容量为j的背包，因此dp[i][j] = dp[i-1][j]
  6. j >= vi时，状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-vi] + wi)

python版代码

# 物品属性
v = [0, 2, 3, 4, 5]
w = [0, 3, 4, 5, 6]

N = len(v)
max_V = 10
dp = [[0 for _ in range(max_V+1)] for _ in range(N)]
for i in range(1, N):
    for j in range(1, max_V+1):
        if j < v[i]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])
print(dp[N-1][max_V])
# 按行输出表格
for c in dp:
    print(c)

输出结果：

三、优化空间复杂度

以上方法的时间复杂度和空间均为O(VN),其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到O(V)。
根据以上推导，\(dp[i][j]\)由\(dp[i-1][j]\)和\(dp[i-1][j-v[i]]\)两个子问题递推而来，在考虑将二维数组替换成一维数组时，只需要保证\(dp[i][j]\)在\(dp[i-1][j]\)和\(dp[i-1][j-v[i]]\)更新前更新即可。
一维数组的更新方式：
\(j >= v_i\)时，\(dp[j] = max(dp[j], dp[j-v[i]] + w[i])\)
为了确保dp[j]在dp[j-v[i]]前更新，需要将v的循环顺序改为逆序，即内层循环从v到1循环。

步骤总结

  1. 使用一个长度为V的一维数组记录dp[j]，初始化：dp = [0 for _ in range (V+1)]
  2. 边界：dp[0] = 0
  3. 外层循环：i件物品，从1到V循环
  4. j >= vi时，状态转移方程：dp[j] = max(dp[j], dp[j-v[i]] + w[i])

python版代码

# 物品属性
v = [0, 2, 3, 4, 5]
w = [0, 3, 4, 5, 6]

N = len(v)
max_V = 10
dp = [0 for _ in range(max_V + 1)]
print(dp)
for i in range(1, N):
    j = max_V
    while j >= v[i]:
        dp[j] = max(dp[j], dp[j-v[i]] + w[i])
        j -= 1
    # 按行输出
    print(dp)
print(dp[max_V])

输出结果：

四、初始化的细节问题

求最优解的背包问题中，有两种不太相同的问法，一个是要求“恰好装满背包”，一个并没有要求必须把背包装满。

  • "恰好装满背包"时，初始化F[0]=0，其他值均为-∞
  • 不要求装满背包，只要求价值最大，初始化全部设为0

初始化的F数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可以在什么也不装且价值为0的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为-∞ 了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。

推荐阅读