动态规划-01背包

兜兜转转了半天，发现还是Carl写的好。

看过动态规划-基础的读者，大概都清楚。

动态规划是将大问题，分解成子问题。并将子问题的解储存下来，避免重复计算。

而背包问题，就是动态规划延申出来的一个大类。

而01背包，就隶属于背包问题。

那什么又是01背包呢？

01背包

有n件物品，与一次最多能背w重量的背包。第i件物品，重量为weight[i]，得到的价值为value[i]。

每件物品只能用一次，求解，将那些物品装入背包内，物品的价值总和最大。 

这是一个标准的背包问题，很多一看到这个，就直接想起用动态规划，而忽略了暴力解法。

这是因为没有 自下而上 思考的结果。

如下代码，一般动态规划问题，都是能通过回溯解决，因为每个物品都有两种可能(状态)，

被放入背包，或者不放入背包。

// 全局变量用于记录最大价值int maxValue = 0;// 物品的重量和价值数组vector weights = {1, 3, 4, 5, 6};vector values = {1, 3, 4, 5, 6};// 背包容量int capacity = 10;// 回溯函数void backtrack(int index, int currentWeight, int currentValue) { // 如果已经遍历完所有物品 if (index == weights.size()) { // 更新最大价值 if (currentValue > maxValue) { maxValue = currentValue; } return; } // 不选择当前物品 - 01背包中的0 backtrack(index + 1, currentWeight, currentValue); // 选择当前物品 - 01背包中的1 if (currentWeight + weights[index] <= capacity) { backtrack(index + 1, currentWeight + weights[index], currentValue + values[index]); }}

如上的回溯算法，每个问题都有两个解法，通过暴力解决，但通常这种解法，是O(2^n)的时间复杂度，随着数量的增加。

呈指数级上升。

而动态规划仅仅需要O(N*M)就可以解决。

第一步：下标含义

dp[i][j]表示将前i件物品装进限重为j的背包可以获得的最大价值, 0<=i<=N, 0<=j<=W

第二步：推导公式

那么我们可以将dp[0][0...W]初始化为0，表示将前0个物品(即没有物品)，装入书包的最大价值为0。那么当i>0时，dp[i][j]有两种情况：

1. 不装入第i件物品，即dp[i−1][j]；
2. 装入第i件物品（前提是能装下），即dp[i-1][j-weight[i]]+value[i]。

第三步：书写代码

dp[weight.size()][bagweight + 1];// weight数组的大小 就是物品个数for(int i = 1; i < weight.size(); i++) { // 遍历物品 for(int j = 0; j <= bagweight; j++) { // 遍历背包容量 if (j < weight[i]) dp[i][j] = dp[i - 1][j]; else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); }}

压缩

递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

看到 dp[i][j] 与 dp[i-1][...] 的

大家都可以发现，dp都由上一行推导出来的(也就是把dp[i - 1]那一层拷贝到dp[i]上)，所以可以压缩代码。

把二维数组，压缩为一维滚动数组。

这也就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。

需要注意的是，为了防止上一层循环的dp[0,...,j-1]被覆盖，循环的时候 j 只能逆向枚举

如下：

for(int i = 0; i =weight[i]; j--){ dp[j] = max( dp[j], dp[j-weight[i]]+value[i] ); }}

大纲 

1、分割等和子集

 2、最后一块石头的重量 II

 3、目标和

 4、一和零

题目

1、分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]输出：true解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]输出：false解释：数组不能分割成两个元素和相等的子集。

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

class Solution { // 最大也就意味着最接近 // 能通过动态规划解决的，都能通过回溯解决 // 每个数字都有两种状态，被选中，或者不被选中 // 只有单纯的数字，那么数字的大小是重量，也是价值。public: bool canPartition(vector& nums) { int cur = 0; for(int i:nums) cur+=i; int sum = cur/2; if(sum*2 != cur) return false; // 意外情况，直接排除 vector dp(sum+1,0); for(int i=0; i=nums[i]; --j){ dp[j] = max(dp[j], dp[j-nums[i]]+nums[i]); } } return sum==dp[sum]?true:false; }};

2、最后一块石头的重量 II

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

• 如果 x == y，那么两块石头都会被完全粉碎；
• 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

示例 1：

输入：stones = [2,7,4,1,8,1]输出：1解释：组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

示例 2：

输入：stones = [31,26,33,21,40]输出：5

提示：

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 100

为啥要分两堆->一直在动态的动态的维护，从第一块进入开始，一直在动态的维护两堆的平衡。

class Solution { // 对呐，只要让两拨石头血拼就行！ // 但是，为啥要让两拨石头血拼？ // 图片上附上解析，希望以后能看懂public: int lastStoneWeightII(vector& stones) { int sum = 0; for(int i : stones) sum+=i; int cur = sum; sum>>=1; // 右移2位，相当于除以2； vector dp(sum+1, 0); for(int i=0; i=stones[i]; --j){ dp[j] = max(dp[j],dp[j-stones[i]]+stones[i]); } } return cur-2*dp[sum]; }};

3、目标和

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 \'+\' 或 \'-\' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 \'+\' ，在 1 之前添加 \'-\' ，然后串联起来得到表达式 \"+2-1\" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3输出：5解释：一共有 5 种方法让最终目标和为 3 。-1 + 1 + 1 + 1 + 1 = 3+1 - 1 + 1 + 1 + 1 = 3+1 + 1 - 1 + 1 + 1 = 3+1 + 1 + 1 - 1 + 1 = 3+1 + 1 + 1 + 1 - 1 = 3

示例 2：

输入：nums = [1], target = 1输出：1

提示：

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

class Solution { // 如果用暴力解法，本题也是能做的 // 但是如果我不暴力呢？ // 了解过答案之后，就发现这道题目，纯纯是一道推理题。 // 用方法就行推理，真tm是一道推理题 // (cur+)+(cur-) = target; // (cur+)-(cur-) = target; // cur = (sum-target)/2; 由此公式推导 // 只要找到cur就OK了 // 当sum为0时，代表总和与target相同，都只有一种情况public: int findTargetSumWays(vector& nums, int target) { int cur = 0; for(int i:nums) cur+=i; int sum = (cur-target)>>1; if(sum*2!=cur-target||sum<0) return 0; // 直接就没有可能了 vector dp(sum+1); dp[0]=1; // 公式推导出来的正整数 for(int i=0; i=nums[i]; --j){ dp[j]=dp[j-nums[i]]+dp[j]; } } return dp[sum]; }}; // ???我的脑袋里，有个大大的问题？这能过？？

4、一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

输入：strs = [\"10\", \"0001\", \"111001\", \"1\", \"0\"], m = 5, n = 3输出：4解释：最多有 5 个 0 和 3 个 1 的最大子集是 {\"10\",\"0001\",\"1\",\"0\"} ，因此答案是 4 。其他满足题意但较小的子集包括 {\"0001\",\"1\"} 和 {\"10\",\"1\",\"0\"} 。{\"111001\"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

输入：strs = [\"10\", \"0\", \"1\"], m = 1, n = 1输出：2解释：最大的子集是 {\"0\", \"1\"} ，所以答案是 2 。

提示：

• 1 <= strs.length <= 600
• 1 <= strs[i].length <= 100
• strs[i] 仅由 \'0\' 和 \'1\' 组成
• 1 <= m, n <= 100

class Solution { // 直接就干到n的三次方了！我的天呐，太牛了public: int findMaxForm(vector& strs, int m, int n) { vector<vector> dp(m+1,vector(n+1,0)); for(string str : strs){ int num0=0,num1=0; for(char c : str){ if(c==\'0\') num0++; else num1++; } for(int i=m; i>=num0; --i){ for(int j=n; j>=num1; --j){  dp[i][j] = max(dp[i][j],dp[i-num0][j-num1]+1); } } } return dp[m][n]; }};

完结（￣︶￣）↗　，自己是收益匪浅啦

博客借鉴：

1、动态规划之背包问题系列

2、动态规划：01背包理论基础