动态规划-01背包问题

01背包问题

题目

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

基本思路

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：

f[i][v] = max{ f[i-1][v], f[i-1][v-c[i]] + w[i] }

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

image.png image.png image.png

# coding: utf-8
bag_v = 8 # 背包大小
# 4个商品，第一列0用于填充
w = [0, 2, 3, 4, 5] # 商品的体积
v = [0, 3, 4, 5, 6] # 商品的价值

# 创建空矩阵
dp = [[0 for i in range(bag_v+1)] for i in range(4+1)]

for i in range(1, 4+1):
    for j in range(1, bag_v+1):
        if j < w[i]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

print(dp)
            

此种方法维护的是一张二维表
时间和空间复杂度均为O(N*V)
其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。

先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。
状态转移式f[v]=max{f[v],f[v-c[i]]}

# coding: utf-8
bag_v = 8 # 背包大小
# 4个商品，第一列0用于填充
n = 4
w = [0, 2, 3, 4, 5] # 商品的体积
v = [0, 3, 4, 5, 6] # 商品的价值

# 二维矩阵方法

# 创建空矩阵
#dp = [[0 for i in range(bag_v+1)] for i in range(n+1)]

# for i in range(1, n+1):
#     for j in range(1, bag_v+1):
#         if j < w[i]:
#             dp[i][j] = dp[i-1][j]
#         else:
#             dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
# print(dp)

# 一维数组方法
f = [0 for i in range(bag_v + 1)]
for i in range(1, n+1):
    for j in range(bag_v, 0, -1):
        if j >= w[i]:
            f[j] = max(f[j], f[j-w[i]] + v[i])

print(f)

            

参考资料

1. 01背包问题 图解+详细解析 （转载）
2. 动态规划解决背包问题（0-1、完全）