Leetcode Link: 01背包_牛客题霸_牛客网 (nowcoder.com)
题目讲解： https://www.bilibili.com/video/BV1ET4y1U7T6?p=15&t=203.9
题目
给定数组 w, v, bag.
w[i]表示第 i 个货物的重量，v[i]表示第 i 个货物的价值，bag 表示背包的容量
返回背包能够装下的最大价值
从暴力递归到动态规划
暴力递归
本问题属于从左到右的考虑模型
因此，子问题实际上是考虑从 idx 位置到末尾的物品随意选择时，返回最大的价值
因此在当前位置，只有两种情况，要当前货物还是不要当前货物
class Solution:
def knapsack(self , w, v, bag):
return self.process(w, v, 0, bag)
# 考虑到了idx位置的货物
# [idx .. len(w)-1]货物随便选，返回最大价值
# 对于当前位置idx, 只有"要"和"不要"当前货物这两种情况
def process(self, w, v, idx, rest):
### base case 注意区分无效选择和返回值
if idx == len(w):
return 0 # 没货了，那我放不进去了，价值就是0（这里不是-1，不是无效）
if rest < 0:
return -1 # 背包容量为负数，表示前面的选择是无效选择
### 两种情况
# 不要当前的货
p1 = self.process(w, v, idx+1, rest)
# 要当前的货，需要考虑这个选择是不是有效
# 如果选择了当前的货物导致后面选择无效，则p2就是一个无效的值，不应该拿来操作或者和p1进行比较
# 或者换句话，我要先保证我能放下这个货物我才装
p2 = -1
nnext = self.process(w, v, idx+1, rest-w[idx]) # 我先看看有没有效
if nnext != -1:
p2 = nnext + v[idx]
return max(p1, p2)记忆化搜索
动态规划 （未压缩）
class Solution:
# 行为 idx: 0~len(w)
# 列为 rest: 负数~bag
def knapsack(self , w, v, bag):
dp = [[0 for _ in range(bag+1)] for _ in range(len(w)+1)]
# 根据base case填写初始值，最后一行全是0
# 负数的情况就通过判断来考虑了
for i in range(bag+1):
dp[len(w)][i] = 0
for i in range(len(w)-1, -1, -1): # 依赖下一行，所以倒着来
for j in range(bag+1):
# 根据暴力递归抄一下改改就行!
if j-w[i] >= 0:
dp[i][j] = max(dp[i+1][j], v[i]+dp[i+1][j-w[i]])
else:
dp[i][j] = dp[i+1][j] 动态规划 （状态压缩）
可以看到，依赖关系是上一行依赖下面一行，而列又不是瞎依赖的，所以可以使用滚动数组的方式进行状态压缩，只是用一行，反着更新列。因为当前列依赖当前列和前面的列。
class Solution:
# 行为 idx: 0~len(w)
# 列为 rest: 负数~bag
def knapsack(self , w, v, bag):
dp = [0 for _ in range(bag+1)]
# 根据base case填写初始值
# 我们需要先写倒数第一行，就是0，可以省略。
for i in range(len(w)-1, -1, -1): # 依赖下一行，所以倒着来
for j in range(bag, -1, -1):
# 列要倒着来
if j-w[i] >= 0:
dp[j] = max(dp[j], v[i]+dp[j-w[i]])
else: # else 之后的可以省略
dp[j] = dp[j]