网站服务器在那里找,公司十大部门,wordpress 民宿模板,行业网平台前言#xff1a;
今天同样是01背包问题#xff0c;今天详细学习了背包问题在各种场景下的应用。今天一道也没做出来#xff0c;有点废。好难啊#xff01;就是思路不太清晰#xff0c;不知道如何去做#xff0c;看了题解后感觉原来如此#xff0c;但是想不出来。今天做…前言
今天同样是01背包问题今天详细学习了背包问题在各种场景下的应用。今天一道也没做出来有点废。好难啊就是思路不太清晰不知道如何去做看了题解后感觉原来如此但是想不出来。今天做的时候有几道题思路基本差不多但是想着想着就懵了直接把自己绕进去了。
第一题 简介
本题与昨天的最后一题有点相像基本思路一致。只不过昨天那题是求两子集相等的时候本题可以看作求两子集的相差最小
同样动态规划五部曲
1.确定dp数组的含义 dp[j] 表示容量这里说容量更形象其实就是重量为j的背包最多可以背最大重量为dp[j]。
2.确定递归公式 dp[j] max(dp[j],dp[j-stones[i]]stones[i]);
3.确定如何初始化
因为提示中给出1 stones.length 301 stones[i] 100所以最大重量就是30 * 100。
而我们要求的target其实只是最大重量的一半所以dp数组开到1500大小就可以了。
当然也可以把石头遍历一遍计算出石头总重量 然后除2得到dp数组的大小。
接下来就是如何初始化dp[j]呢因为重量都不会是负数所以dp[j]都初始化为0就可以了这样在递归公式dp[j] max(dp[j], dp[j - stones[i]] stones[i]);中dp[j]才不会初始值所覆盖。
4.确定如何遍历数组
5.打印数组
代码实现 int lastStoneWeightII(vectorint stones) {vectorint dp(1501,0);int sum 0;for(int i0;istones.size();i){sum stones[i];}int target sum /2;for(int i0;istones.size();i){for(int j target;jstones[i];j--){dp[j] max(dp[j],dp[j-stones[i]]stones[i]);}}return sum - dp[target]-dp[target];}
第二题 简介 动态规划五部曲
1.确定dp数组的含义 //dp[j]表示在 等于j 时 有几种方法
2.确定递归公式
只要搞到nums[i]凑成dp[j]就有dp[j - nums[i]] 种方法。例如dp[j]j 为5
已经有一个1nums[i] 的话有 dp[4]种方法 凑成 容量为5的背包。已经有一个2nums[i] 的话有 dp[3]种方法 凑成 容量为5的背包。已经有一个3nums[i] 的话有 dp[2]中方法 凑成 容量为5的背包已经有一个4nums[i] 的话有 dp[1]中方法 凑成 容量为5的背包已经有一个5 nums[i]的话有 dp[0]中方法 凑成 容量为5的背包
那么凑整dp[5]有多少方法呢也就是把 所有的 dp[j - nums[i]] 累加起来。
所以递归公式为 3.确定如何初始化 dp[0] 1 因为不放任何数也是一种办法。dp[j]其他下标对应的数值应该初始化为0。
4.确定如何遍历数组 由上方公式我们可以看出只要我们知道能装满bagsize正数和的 容量有几种方法就可以了。 其中有两种特殊情况 5.打印数组
代码实现 int findTargetSumWays(vectorint nums, int target) {int sum 0;for (int i 0; i nums.size(); i) sum nums[i];if (abs(target) sum) return 0; // 此时没有方案if ((target sum) % 2 1) return 0; // 此时没有方案/*left:正数和right负数和left right sumleft - right targetsumtarget 2 bagsize(正数和)*/int bagSize (target sum) / 2; vectorint dp(bagSize 1, 0);dp[0] 1;for (int i 0; i nums.size(); i) {for (int j bagSize; j nums[i]; j--) {dp[j] dp[j - nums[i]];}}return dp[bagSize];}
第三题 简介
本题是01背包两个维度的一个应用以前的题都是一个重量就可以确定但是本题需要m和n同时确定。其实只要确定本题是两个维度之后就与其他题没有区别了。
同样动态规划五部曲
1.确定dp数组的含义 dp[i][j] 表示最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
2.确定递归公式
onenum 和 zeronum 为字符串中的 01 的个数。 3.确定如何初始化 4.确定如何遍历数组
注本题从两个维度进行确定 5.打印数组
代码实现 //dp[i][j]最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。 int findMaxForm(vectorstring strs, int m, int n) {vectorvectorint dp(m 1, vectorint (n 1, 0)); // 默认初始化0for (string str : strs) { // 遍历物品int oneNum 0, zeroNum 0;for (char c : str) {if (c 0) zeroNum;else oneNum;}for (int i m; i zeroNum; i--) { // 遍历背包容量且从后向前遍历for (int j n; j oneNum; j--) {dp[i][j] max(dp[i][j], dp[i - zeroNum][j - oneNum] 1);}}}return dp[m][n];}
总结
总体来说今天收获还是很大的见识了很多题型学习了01背包问题在各种场景如何进行运用。
虽然没有自己做出来但是收获颇丰继续加油
