背包问题-01背包问题

01背包问题

问题抽象：有N个物体，每一个重量为c[i]，各自的价值为w[i]，背包最大容量为V,求背包能放下的物品总和的最大价值

DP思想解决问题

每一个物体都有被放入和不被放入的可能，当前被选择的物体是否被放入所产生的最大价值和后续的物体无关(无后效性)，只和前面已经放入的物体的总价值
有关(重叠子问题)，前面的最优，加上当前的物体一定最优(最优子结构)

转移方程

f[i][v]表示将第i种物体放入容量为v的背包能达到的最大价值
f[i][v]=max{f[i-1][v], f[i-1][v-c[i]]+w[i]} 表示当前物体不被选(只将第i-1个物体放入背包)以及将第i-1个物体放入v-c[i]的背包，加上当前的物体

时间复杂度是O(VN),空间复杂度为O(VN)，实现代码为：

N,V=20,100
c=[...]
w=[...]
f=[[0 for _ in range(V+1)] for _ in range(N+1)] # 第0行表示没有石头装进去
for i in range(1, N+1):
    for v in range(V+1):
        f[i][v]=max(f[i-1][v], f[i-1][v-c[i]]+w[i]) if v-c[i]>0 else f[i-1][v] 

空间复杂度可以进一步的压缩，求解f的第i行数值的时候只是使用到了上一行的状态，因此可以使用两个
N维数组来储存状态，last_state以及cur_state,压缩状态的代码如下：

N,V=20,100
c=[...]
w=[...]
last_state=[0 for _ in range(V+1)] # 第0行的时候没有石头装进去，对于任意容量的背包都是0价值的
cur_state=last_state # 初始时二者一致
for i in range(1, N+1):
    last_state=cur_state # 状态变换
    for v in range(V+1):
        cur_state[v]=max(last_state[v], last_state[v-c[i]]+w[i]) # 仅仅使用到上一行的状态

进一步压缩空间复杂度，只使用一个V+1维数组进行迭代计算,由于每次计算cur_state[v]依赖的是，last_state[v], last_state[v-c[i]]
(相当于是依赖相对位置更靠前面的数值)：

N,V=20,100
c=[...]
w=[...]
f=[0 for _ in range(V+1)] # 第0行的时候没有石头装进去，对于任意容量的背包都是0价值的
for i in range(1, N+1):
    for v in range(V,-1,-1): # 从V往0倒序遍历，可以使得f[v-c[i]]不会出错
        f[v]=max(f[v], f[v-c[i]]+w[i]) if v-c[i]>=0 else f[v]# 仅仅使用到之前的状态
        # 袋子容量小于当前物品的重量，一定放不下当前物品，最大的价值取决于上一个物品的被放置(或者不放置)的最大值
# 进一步优化循环
for i in range(1, N+1):
    for v in range(V,c[i]-1,-1): # 从V往0倒序遍历，可以使得f[v-c[i]]不会出错
        f[v]=max(f[v], f[v-c[i]]+w[i]) # 仅仅使用到之前的状态
        # 袋子容量小于当前物品的重量，一定放不下当前物品，最大的价值取决于上一个物品的被放置(或者不放置)的最大值
        # 遍历的袋子容量一定大于等于当前物品的重量

未优化和终极优化的完整代码：

stoneValue = [1, 3, 2, 4]
stoneCost = [2, 2, 2, 3]
stoneValue = [0] + stoneValue  # 虚拟的第0块石头价值为0
stoneCost = [0] + stoneCost  # 虚拟的第0石头的重量为0
pack = 8
N = len(stoneCost)
dp = [[0 for _ in range(pack + 1)] for _ in range(N)] # 0号石头对于任何背包都是没有价值的
for i in range(1, N):
    for v in range(pack + 1):
        dp[i][v] = max(dp[i - 1][v], dp[i - 1][v - stoneCost[i]] + stoneValue[i]) if v - stoneCost[i] >= 0 else \
        dp[i - 1][v]

print(dp[-1][-1])
dp=[0 for _ in range(pack+1)]
for i in range(1, N):
    for v in range(pack, stoneCost[i]-1,-1):
        dp[v]=max(dp[v], dp[v-stoneCost[i]]+stoneValue[i])
print(dp[-1])

01背包问题的初始化

要求背包恰好装满

初始化的时候dp[0][0]或者一位数组dp[0]初始化为0，其他的为float('inf')*-1，只有重量为0的石头在
容量为0的背包中，才能创造价值为0，其他情况为不合格。

# 要求背包恰好装满
stoneValue = [1, 3, 2, 4]
stoneCost = [2, 2, 1, 2]
pack = 7
stoneValue = [0] + stoneValue  # 虚拟的第0块石头价值为0
stoneCost = [0] + stoneCost  # 虚拟的第0石头的重量为0
N=len(stoneValue)
dp = [[-float('inf') for _ in range(pack + 1)] for _ in range(N)]
dp[0][0] = 0  # 除了重量为0背包容量为0之外，其余的均为不合法情况
for i in range(1, N):
    for v in range(pack + 1):
        dp[i][v] = max(dp[i - 1][v], dp[i - 1][v - stoneCost[i]] + stoneValue[i]) if v - stoneCost[i] >= 0 else \
            dp[i - 1][v]
print(dp[-1][-1])
# 优化版本
dp=[-float('inf') for _  in range(pack+1)]
dp[0]=0
for i in range(1, N):
    for v in range(pack,stoneCost[i]-1,-1):
        dp[v]=max(dp[v], dp[v-stoneCost[i]]+stoneValue[i])
print(dp[-1])

# 没有要求背包恰好装满的情况就是之前的普通情况,将所有的初始值记为0