【Python】动态规划之背包问题

递归思路：

• 确定递归结束条件
  • 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))