第一章：经典动态规划：0-1 背包问题

labuladong 经典动态规划：0-1 背包问题

---

动态规划之背包汇总

第零章：动态规划解题套路框架
第一章：经典动态规划：0-1 背包问题
第零章：经典动态规划：子集背包问题
第零章：经典动态规划：完全背包问题

---

题目地址

有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.

问最多能装入背包的总价值是多大?

样例 样例 1:

输入: m = 10, A = [2, 3, 5, 7], V = [1, 5, 2, 4] 输出: 9 解释: 装入 A[1] 和
A[3] 可以得到最大价值, V[1] + V[3] = 9 样例 2:

输入: m = 10, A = [2, 3, 8], V = [2, 5, 8] 输出: 10 解释: 装入 A[0] 和 A[2]
可以得到最大价值, V[0] + V[2] = 10

1. base case：0 物品和 0 背包容量时，价值为0
2. 明确状态和选择
   • 状态：背包的容量 ，放进去的物品
   • 选择：放/不放 当前物品到背包中
3. dp数组的含义：因为状态有两个，所以dp用二维数组表示。dp[i][j] 表示对前i个物品，背包容量为j时，可以装的最大价值（dp数组可以加一行一列表示0物品或0容量时的状态，更便于进行状态转移）
   • 若书包容量太小，容不下（if j<A[i-1]），则dp[i][j]=dp[i-1][j]
   • 否则，可以放进去
     • 若不放进去，则dp[i][j]=dp[i-1][j]
     • 若放进去，则dp[i][j]=dp[i-1][j-A[i-1]]+V[i-1] （因为首行首列加了0物品0背包，所以数组中第0个物品其实是A[i-1]大小和V[i-1]价值）

class Solution:
    def backPackII(self, m, A, V):
        # write your code here
        dp=[[0 for _ in range(m+1)] for _ in range(len(A)+1)]
        for i in range(1,len(A)+1):
            for j in range(1,m+1):                
                if j<A[i-1]:# 若书包容量为j时，放不进去第i个物品（从0开始，所以A[i-1]表示第i个物品的大小）
                    dp[i][j]=dp[i-1][j]
                else: # 否则，可以放进去
                    notBring=dp[i-1][j] # 选择不放
                    bring=dp[i-1][j-A[i-1]]+V[i-1] # 选择放
                    dp[i][j]=max(notBring,bring) # 取最大值即可
        print(dp)
        return dp[-1][-1]