递归思路：
- 确定递归结束条件
- bag < 0时，非法，标记为无效解
- index 越界，结束递归
- 递归分支
- 不要当前货物，index往下走
- 要当前货物，标记为无效解的需要进行置0，有效解则 v[index] + index往下走
DP思路：
-
根据暴力递归写DP
-
构建dp二位数组new int [N+1][bag+1]，为什么要+1，因为递归中有越界判断
-
确定依赖关系
- index依赖于下一层的index （important）
- 最后一层的dp[index]全部为0，因为递归中 len(w) == index return 0
-
构建dp
- 从倒数第二层index开始，rest从0~bag 或 bag~0都可以，没有依赖关系
-
最后return dp[0][bag]，就是从0开始遍历货物，bag为空的情况
def max_value(w, v, bag):
"""
params w: 货物的重量
params v: 货物的价值
params bag: 背包容量
return : 不超重的情况下，返回背包的最大价值
"""
if not w or not v or len(w) == 0 or len(v) == 0: # 边界条件
return 0
# 当前考虑到了index货物，index后的所有货物可以自由选择
# 做的选择不能超过背包容量
# 返回最大价值
def process(startIndex, w, v, bag):
# if bag <= 0: # 如果背包 < 0，则是无效解
# return 0
if startIndex == len(w): # 如果开始索引越界，就没了
return 0
p1 = process(startIndex+1, w, v, bag) # 不要当前的货
# 要当前的货
if bag - w[startIndex] < 0: # 如果bag容量小于0，为无效解，value为0
p2 = 0
else:
p2 = v[startIndex] + process(startIndex+1, w, v, bag-w[startIndex])
return max(p1, p2)
return process(0, w, v, bag)
def dp_value(w, v, bag):
if not w or not v or len(w) == 0 or len(v) == 0: # 边界条件
return 0
N = len(w)
dp = [[0 for j in range(bag+1)] for i in range(N+1)] # 构建动态规划表
# 确定依赖，startIndex依赖于下一层的startIndex，
for startIndex in range(N-1, -1, -1):
for rest in range(bag, -1, -1):
# 没拿的情况
p1 = dp[startIndex+1][rest]
# 如果拿了超重，无效解计0，有效解正常计算
p2 = 0 if rest - w[startIndex] < 0 else v[startIndex] + dp[startIndex+1][rest-w[startIndex]]
dp[startIndex][rest] = max(p1, p2)
return dp[0][bag]
w = [3,2,4,7,3,1,7]
v = [5,6,3,19,12,4,2]
bag = 15
print(max_value(w, v, bag))
print(dp_value(w, v, bag))