背包型动态规划

• 详细讲解背包类型问题：背包九讲

1 题型分析

1.1 经典背包问题

• 你有一个背包，背包有最大承重
• 每个物品有重量和价值
• 目标:不撑爆背包的前下
  • 装下最多重量物品？
  • 装下最大总价值的物品？
  • 有多少种方式正好带走满满一背包物品？

1.2 解题要点

• 最后一步
  • 最后一个背包内的物品是哪个？
  • 最后一个物品有没有进背包？(01背包)
• 数组的大小和最大承重Target有关

2 背包问题

2.1 可行性背包

LintCode 92. Backpack

• 常见误区:
  • 错误状态：dp[i]表示前i个物品能拼出的最大重量(不超过Target)
  • 反例:A=[3 9 5 2], Target=10
  • 错误原因:最优策略中，不需要知道前N-1个物品拼出的不超过Target的最 大重量
• 状态:
  • dp[i][w] = 能否用前i个物品拼出重量w (TRUE / FALSE)
• 空间优化:
  • dp[i] 是否可以达到重量i
  • 第一层：遍历可用的item
  • 第二层：从后往前遍历可达重量再加上item为新可达重量

2.2 计数型背包

LintCode 564. Backpack VI

• 每个item不仅只使用一次，可以多次使用

2.3 最值型背包

LintCode 125. Backpack II

• 除了重量，每个物品还有价值，求背包能装下的最大价值的物品
• 设dp[i][w]=用前i个物品拼出重量w时最大总价值(-1表示不能拼出 w)
  • 二维DP i-表示前i个物品，w-表示能拼出的重量w，值代表价值
  • 从最后一个值的角度出发，存在两种状况，放入或者不放入背包
  • 放入背包就是dp[i-1][j-A[i-1]]+V[i-1],不放入背包就是dp[i-1][j]

class Solution:
    """ Time O(mn), Space O(mn) -> O(m)
    @param m: An integer m denotes the size of a backpack
    @param A: Given n items with size A[i]
    @param V: Given n items with value V[i]
    @return: The maximum value
    """
    def backPackII(self, m, A, V):
        # write your code here
        n = len(A)
        dp = [0] * (m + 1) 
        for i in xrange(n):
            for j in xrange(m, -1, -1): # Why Reverse from m to 0?
                if A[i] <= j:
                    dp[j] = max(dp[j], dp[j-A[i]] + V[i])
        return max(dp)

LintCode 440. Backpack III

• II是每个item只能用一次，III是每个item可以用无限次
• 递归公式是关键！1.状态 2.如何递归 3.空间优化

  class Solution:
    """
    @param A: an integer array
    @param V: an integer array
    @param m: An integer
    @return: an array
    """
    def backPackIII(self, A, V, m):
        # write your code here
        n = len(A)
        dp = [0] * (m + 1)
        for i in xrange(n):
            for j in xrange(m+1): # 和II相比只有这里的顺序发生了变化
                if A[i] <= j:
                    dp[j] = max(dp[j], dp[j-A[i]] + V[i])
        return max(dp)