完全背包问题与01背包比较类似不过是物体可以被无限重复的选择1.52. 携带研究材料第七期模拟笔试52. 携带研究材料第七期模拟笔试小明是一位科学家他需要参加一场重要的国际科学大会以展示自己的最新研究成果。他需要带一些研究材料但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等它们各自占据不同的重量并且具有不同的价值。小明的行李箱所能承担的总重量是有限的问小明应该如何抉择才能携带最大价值的研究材料每种研究材料可以选择无数次并且可以重复选择。#include iostream #include vector using namespace std; int main() { int n, bagWeight; int w, v; cin n bagWeight; vectorint weight(n); vectorint value(n); for (int i 0; i n; i) { cin weight[i] value[i]; } vectorvectorint dp(n, vectorint(bagWeight 1, 0)); // 初始化 for (int j weight[0]; j bagWeight; j) dp[0][j] dp[0][j - weight[0]] value[0]; for (int i 1; i n; 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][j - weight[i]] value[i]); } } cout dp[n - 1][bagWeight] endl; return 0; }这里是二维dp数组的做法dp[i][j] 表示从下标为[0-i]的物品每个物品可以取无限次放进容量为j的背包价值总和最大是多少。不放物品i背包容量为j里面不放物品i的最大价值是dp[i - 1][j]。放物品i背包空出物品i的容量后背包容量为j - weight[i]dp[i][j - weight[i]] 为背包容量为j - weight[i]且不放物品i的最大价值那么dp[i][j - weight[i]] value[i] 物品i的价值就是背包放物品i得到的最大价值递推公式dp[i][j] max(dp[i - 1][j], dp[i][j - weight[i]] value[i]);注意完全背包二维dp数组 和 01背包二维dp数组 递推公式的区别01背包中是dp[i - 1][j - weight[i]] value[i])因为01背包中的物体只有一个只可以放进去一次所以物体的范围应该是0到i-1完全背包中的物体可以被无限次选择所以选择的范围是0到i如何初始化dp[0][j]即存放编号0的物品的时候各个容量的背包所能存放的最大价值。那么很明显当j weight[0]的时候dp[0][j] 应该是 0因为背包容量比编号0的物品重量还小。当j weight[0]时dp[0][j] 如果能放下weight[0]的话就一直装每一种物品有无限个。遍历顺序中可以外层遍历物体也可以遍历背包容量#include iostream #include vector using namespace std; int main() { int N, bagWeight; cin N bagWeight; vectorint weight(N, 0); vectorint value(N, 0); for (int i 0; i N; i) { int w; int v; cin w v; weight[i] w; value[i] v; } vectorint dp(bagWeight 1, 0); for(int j 0; j bagWeight; j) { // 遍历背包容量 for(int i 0; i weight.size(); i) { // 遍历物品 if (j - weight[i] 0) dp[j] max(dp[j], dp[j - weight[i]] value[i]); } } cout dp[bagWeight] endl; return 0; }这里解法是使用滚动数组一维的dp做法dp[i]表示容量为i的背包能够装的最大价值与01背包的遍历不同01背包需要先便利物体再反向遍历容量这里完全背包不需要这样遍历按照物体或者容量遍历都是可以的。2.518.零钱兑换II力扣题目链接(opens new window)给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。class Solution { public: int change(int amount, vectorint coins) { vectoruint64_t dp(amount1,0); dp[0]1; for(int i0;icoins.size();i){ for(int j0;jamount;j){ if(jcoins[i]){ dp[j]dp[j-coins[i]]; } } } return dp[amount]; } };这里也是一种完全背包不过计算的是组成的金额组合数并且这里不考虑顺序所以需要遍历的是物体与容量都可以。dp[i]表示金额为i能够组成的组合数所以这里不是求最大值而是进行相加不加第i个物体个数加上加第i个物体的个数3.377. 组合总和 Ⅳ力扣题目链接(opens new window)难度中等给定一个由正整数组成且不存在重复数字的数组找出和为给定目标正整数的组合的个数class Solution { public: int combinationSum4(vectorint nums, int target) { vectoruint64_t dp(target 1, 0); dp[0] 1; //与上一题零钱兑换2比较类似不过零钱兑换是组合问题 //这一题是排列问题所以字可以先便利背包再遍历物体 //先便利背包的话这样放入背包就有多种顺序 for (int i 0; i target; i) { // 遍历背包 for (int j 0; j nums.size(); j) { // 遍历物品 if (i - nums[j] 0 ) { dp[i] dp[i - nums[j]]; } } } return dp[target]; } };与上一题一样不过这里需要顺序是排列问题这样的话遍历顺序就要改变因为如果说先便利物体的话物体1只可以出现在物体2的前面不能在后面反过来的话就会有多种情况出现。4.70. 爬楼梯进阶版卡码网57. 爬楼梯(opens new window)假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬至多m (1 m n)个台阶。你有多少种不同的方法可以爬到楼顶呢注意给定 n 是一个正整数。#includeiostream #includevector using namespace std; int main(){ int n,m; cinnm; vectorint dp(n1,0); dp[0]1; for(int i1;in;i){ for(int j1;jm;j){ if(i-j0){ dp[i]dp[i-j]; } } } coutdp[n]; return 0; }同样的这里也是排列的问题先便利n表示台阶个数即背包容量再遍历m表示每次走的台阶数即选择的物体价值一共是1到m个物体可以选每个都可以无限次数的选择。5.322. 零钱兑换力扣题目链接(opens new window)给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回 -1。你可以认为每种硬币的数量是无限的class Solution { public: int coinChange(vectorint coins, int amount) { vectorint dp(amount 1, INT_MAX); dp[0] 0; for (int i 0; i coins.size(); i) { // 遍历物品 for (int j coins[i]; j amount; j) { // 遍历背包 if (dp[j - coins[i]] ! INT_MAX) { // 如果dp[j - coins[i]]是初始值则跳过 dp[j] min(dp[j - coins[i]] 1, dp[j]); } } } if (dp[amount] INT_MAX) return -1; return dp[amount]; } };不考虑排列的完全背包问题dp[i]表示值为i的金额能够组成的种类的最小个数所以这里的递推公式为取不选择该物体与选择该物体之间的最小值选择该物体的值为dp[j - coins[i]] 16.279.完全平方数力扣题目链接(opens new window)给定正整数 n找到若干个完全平方数比如 1, 4, 9, 16, ...使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。给你一个整数 n 返回和为 n 的完全平方数的 最少数量 。完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。class Solution { public: int numSquares(int n) { //完全平方数是物体n是背包 vectorint dp(n 1, INT_MAX); dp[0] 0; for (int i 1; i * i n; i) { // 遍历物品 for (int j i * i; j n; j) { // 遍历背包 dp[j] min(dp[j - i * i] 1, dp[j]); } } return dp[n]; } };跟上一题一样都是找最小值并且都不考虑顺序dp[i]表示值为i的数由若干个完全平方组成组成的个数最少。7.139.单词拆分力扣题目链接(opens new window)给定一个非空字符串 s 和一个包含非空单词的列表 wordDict判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。class Solution { public: bool wordBreak(string s, vectorstring wordDict) { unordered_setstring wordset(wordDict.begin(),wordDict.end()); vectorbool dp(s.size()1,false); dp[0]true; for(int i1;is.size();i){ for(int j0;ji;j){ string strs.substr(j,i-j); if(wordset.find(str)!wordset.end()dp[j]){ dp[i]true; } } } return dp[s.size()]; } };用s表示的是背包容量字典中字符串表示物体用字典中的字符串装满s但是这里有限制这里不仅是需要装满还需要确定排列的顺序所以需要先便利背包在遍历物体。一维dp[i]表示长度为i的字符串使用字典中的字符串是否能被排列成功这里长度为i的字符串是否能排列成功依赖于dp[j]j为当前长度去除分割的字符串长度当dp[j]为true并且j到i之间的字符串也在字典中表示物体可以被装进背包那么dp[i]为true。背包问题总结确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组递推公式存在规律性问能否能装满背包或者最多装多少dp[j] max(dp[j], dp[j - nums[i]] nums[i]); 对应题目如下这里装满背包一般是代表物体的重量与价值是一样的所以选择装第j个物体或者不装第j个物体之间取最大值并且选择装第j个物体的时候需要留出的空间就是当前容量减去当前物体元素的值。动态规划416.分割等和子集动态规划1049.最后一块石头的重量 II问装满背包有几种方法dp[j] dp[j - nums[i]] 对应题目如下装满背包的方法数量一般是选择装第j个物体与不装第j个物体的个数之和动态规划494.目标和动态规划518. 零钱兑换 II动态规划377.组合总和Ⅳ动态规划70. 爬楼梯进阶版完全背包问背包装满最大价值dp[j] max(dp[j], dp[j - weight[i]] value[i]); 对应题目如下问最大价值就取选择与不选择之间的最大值动态规划474.一和零问装满背包所有物品的最小个数dp[j] min(dp[j - coins[i]] 1, dp[j]); 对应题目如下问最小个数取选择与不选择之间的最小值并且选择的时候添加的个数为1.动态规划322.零钱兑换动态规划279.完全平方数遍历顺序也是根据题目的类型来进行选择的01背包在动态规划关于01背包问题你该了解这些中我们讲解二维dp数组01背包先遍历物品还是先遍历背包都是可以的且第二层for循环是从小到大遍历。和动态规划关于01背包问题你该了解这些滚动数组中我们讲解一维dp数组01背包只能先遍历物品再遍历背包容量且第二层for循环是从大到小遍历。一维dp数组的背包在遍历顺序上和二维dp数组实现的01背包其实是有很大差异的大家需要注意完全背包说完01背包再看看完全背包。在动态规划关于完全背包你该了解这些中讲解了纯完全背包的一维dp数组实现先遍历物品还是先遍历背包都是可以的且第二层for循环是从小到大遍历。但是仅仅是纯完全背包的遍历顺序是这样的题目稍有变化两个for循环的先后顺序就不一样了。如果求组合数就是外层for循环遍历物品内层for遍历背包。如果求排列数就是外层for遍历背包内层for循环遍历物品。相关题目如下求组合数动态规划518.零钱兑换II求排列数动态规划377. 组合总和 Ⅳ (opens new window)、动态规划70. 爬楼梯进阶版完全背包如果求最小数那么两层for循环的先后顺序就无所谓了相关题目如下求最小数动态规划322. 零钱兑换、动态规划279.完全平方数
完全背包问题与01背包比较类似不过是物体可以被无限重复的选择1.52. 携带研究材料第七期模拟笔试52. 携带研究材料第七期模拟笔试小明是一位科学家他需要参加一场重要的国际科学大会以展示自己的最新研究成果。他需要带一些研究材料但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等它们各自占据不同的重量并且具有不同的价值。小明的行李箱所能承担的总重量是有限的问小明应该如何抉择才能携带最大价值的研究材料每种研究材料可以选择无数次并且可以重复选择。#include iostream #include vector using namespace std; int main() { int n, bagWeight; int w, v; cin n bagWeight; vectorint weight(n); vectorint value(n); for (int i 0; i n; i) { cin weight[i] value[i]; } vectorvectorint dp(n, vectorint(bagWeight 1, 0)); // 初始化 for (int j weight[0]; j bagWeight; j) dp[0][j] dp[0][j - weight[0]] value[0]; for (int i 1; i n; 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][j - weight[i]] value[i]); } } cout dp[n - 1][bagWeight] endl; return 0; }这里是二维dp数组的做法dp[i][j] 表示从下标为[0-i]的物品每个物品可以取无限次放进容量为j的背包价值总和最大是多少。不放物品i背包容量为j里面不放物品i的最大价值是dp[i - 1][j]。放物品i背包空出物品i的容量后背包容量为j - weight[i]dp[i][j - weight[i]] 为背包容量为j - weight[i]且不放物品i的最大价值那么dp[i][j - weight[i]] value[i] 物品i的价值就是背包放物品i得到的最大价值递推公式dp[i][j] max(dp[i - 1][j], dp[i][j - weight[i]] value[i]);注意完全背包二维dp数组 和 01背包二维dp数组 递推公式的区别01背包中是dp[i - 1][j - weight[i]] value[i])因为01背包中的物体只有一个只可以放进去一次所以物体的范围应该是0到i-1完全背包中的物体可以被无限次选择所以选择的范围是0到i如何初始化dp[0][j]即存放编号0的物品的时候各个容量的背包所能存放的最大价值。那么很明显当j weight[0]的时候dp[0][j] 应该是 0因为背包容量比编号0的物品重量还小。当j weight[0]时dp[0][j] 如果能放下weight[0]的话就一直装每一种物品有无限个。遍历顺序中可以外层遍历物体也可以遍历背包容量#include iostream #include vector using namespace std; int main() { int N, bagWeight; cin N bagWeight; vectorint weight(N, 0); vectorint value(N, 0); for (int i 0; i N; i) { int w; int v; cin w v; weight[i] w; value[i] v; } vectorint dp(bagWeight 1, 0); for(int j 0; j bagWeight; j) { // 遍历背包容量 for(int i 0; i weight.size(); i) { // 遍历物品 if (j - weight[i] 0) dp[j] max(dp[j], dp[j - weight[i]] value[i]); } } cout dp[bagWeight] endl; return 0; }这里解法是使用滚动数组一维的dp做法dp[i]表示容量为i的背包能够装的最大价值与01背包的遍历不同01背包需要先便利物体再反向遍历容量这里完全背包不需要这样遍历按照物体或者容量遍历都是可以的。2.518.零钱兑换II力扣题目链接(opens new window)给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。class Solution { public: int change(int amount, vectorint coins) { vectoruint64_t dp(amount1,0); dp[0]1; for(int i0;icoins.size();i){ for(int j0;jamount;j){ if(jcoins[i]){ dp[j]dp[j-coins[i]]; } } } return dp[amount]; } };这里也是一种完全背包不过计算的是组成的金额组合数并且这里不考虑顺序所以需要遍历的是物体与容量都可以。dp[i]表示金额为i能够组成的组合数所以这里不是求最大值而是进行相加不加第i个物体个数加上加第i个物体的个数3.377. 组合总和 Ⅳ力扣题目链接(opens new window)难度中等给定一个由正整数组成且不存在重复数字的数组找出和为给定目标正整数的组合的个数class Solution { public: int combinationSum4(vectorint nums, int target) { vectoruint64_t dp(target 1, 0); dp[0] 1; //与上一题零钱兑换2比较类似不过零钱兑换是组合问题 //这一题是排列问题所以字可以先便利背包再遍历物体 //先便利背包的话这样放入背包就有多种顺序 for (int i 0; i target; i) { // 遍历背包 for (int j 0; j nums.size(); j) { // 遍历物品 if (i - nums[j] 0 ) { dp[i] dp[i - nums[j]]; } } } return dp[target]; } };与上一题一样不过这里需要顺序是排列问题这样的话遍历顺序就要改变因为如果说先便利物体的话物体1只可以出现在物体2的前面不能在后面反过来的话就会有多种情况出现。4.70. 爬楼梯进阶版卡码网57. 爬楼梯(opens new window)假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬至多m (1 m n)个台阶。你有多少种不同的方法可以爬到楼顶呢注意给定 n 是一个正整数。#includeiostream #includevector using namespace std; int main(){ int n,m; cinnm; vectorint dp(n1,0); dp[0]1; for(int i1;in;i){ for(int j1;jm;j){ if(i-j0){ dp[i]dp[i-j]; } } } coutdp[n]; return 0; }同样的这里也是排列的问题先便利n表示台阶个数即背包容量再遍历m表示每次走的台阶数即选择的物体价值一共是1到m个物体可以选每个都可以无限次数的选择。5.322. 零钱兑换力扣题目链接(opens new window)给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回 -1。你可以认为每种硬币的数量是无限的class Solution { public: int coinChange(vectorint coins, int amount) { vectorint dp(amount 1, INT_MAX); dp[0] 0; for (int i 0; i coins.size(); i) { // 遍历物品 for (int j coins[i]; j amount; j) { // 遍历背包 if (dp[j - coins[i]] ! INT_MAX) { // 如果dp[j - coins[i]]是初始值则跳过 dp[j] min(dp[j - coins[i]] 1, dp[j]); } } } if (dp[amount] INT_MAX) return -1; return dp[amount]; } };不考虑排列的完全背包问题dp[i]表示值为i的金额能够组成的种类的最小个数所以这里的递推公式为取不选择该物体与选择该物体之间的最小值选择该物体的值为dp[j - coins[i]] 16.279.完全平方数力扣题目链接(opens new window)给定正整数 n找到若干个完全平方数比如 1, 4, 9, 16, ...使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。给你一个整数 n 返回和为 n 的完全平方数的 最少数量 。完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。class Solution { public: int numSquares(int n) { //完全平方数是物体n是背包 vectorint dp(n 1, INT_MAX); dp[0] 0; for (int i 1; i * i n; i) { // 遍历物品 for (int j i * i; j n; j) { // 遍历背包 dp[j] min(dp[j - i * i] 1, dp[j]); } } return dp[n]; } };跟上一题一样都是找最小值并且都不考虑顺序dp[i]表示值为i的数由若干个完全平方组成组成的个数最少。7.139.单词拆分力扣题目链接(opens new window)给定一个非空字符串 s 和一个包含非空单词的列表 wordDict判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。class Solution { public: bool wordBreak(string s, vectorstring wordDict) { unordered_setstring wordset(wordDict.begin(),wordDict.end()); vectorbool dp(s.size()1,false); dp[0]true; for(int i1;is.size();i){ for(int j0;ji;j){ string strs.substr(j,i-j); if(wordset.find(str)!wordset.end()dp[j]){ dp[i]true; } } } return dp[s.size()]; } };用s表示的是背包容量字典中字符串表示物体用字典中的字符串装满s但是这里有限制这里不仅是需要装满还需要确定排列的顺序所以需要先便利背包在遍历物体。一维dp[i]表示长度为i的字符串使用字典中的字符串是否能被排列成功这里长度为i的字符串是否能排列成功依赖于dp[j]j为当前长度去除分割的字符串长度当dp[j]为true并且j到i之间的字符串也在字典中表示物体可以被装进背包那么dp[i]为true。背包问题总结确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组递推公式存在规律性问能否能装满背包或者最多装多少dp[j] max(dp[j], dp[j - nums[i]] nums[i]); 对应题目如下这里装满背包一般是代表物体的重量与价值是一样的所以选择装第j个物体或者不装第j个物体之间取最大值并且选择装第j个物体的时候需要留出的空间就是当前容量减去当前物体元素的值。动态规划416.分割等和子集动态规划1049.最后一块石头的重量 II问装满背包有几种方法dp[j] dp[j - nums[i]] 对应题目如下装满背包的方法数量一般是选择装第j个物体与不装第j个物体的个数之和动态规划494.目标和动态规划518. 零钱兑换 II动态规划377.组合总和Ⅳ动态规划70. 爬楼梯进阶版完全背包问背包装满最大价值dp[j] max(dp[j], dp[j - weight[i]] value[i]); 对应题目如下问最大价值就取选择与不选择之间的最大值动态规划474.一和零问装满背包所有物品的最小个数dp[j] min(dp[j - coins[i]] 1, dp[j]); 对应题目如下问最小个数取选择与不选择之间的最小值并且选择的时候添加的个数为1.动态规划322.零钱兑换动态规划279.完全平方数遍历顺序也是根据题目的类型来进行选择的01背包在动态规划关于01背包问题你该了解这些中我们讲解二维dp数组01背包先遍历物品还是先遍历背包都是可以的且第二层for循环是从小到大遍历。和动态规划关于01背包问题你该了解这些滚动数组中我们讲解一维dp数组01背包只能先遍历物品再遍历背包容量且第二层for循环是从大到小遍历。一维dp数组的背包在遍历顺序上和二维dp数组实现的01背包其实是有很大差异的大家需要注意完全背包说完01背包再看看完全背包。在动态规划关于完全背包你该了解这些中讲解了纯完全背包的一维dp数组实现先遍历物品还是先遍历背包都是可以的且第二层for循环是从小到大遍历。但是仅仅是纯完全背包的遍历顺序是这样的题目稍有变化两个for循环的先后顺序就不一样了。如果求组合数就是外层for循环遍历物品内层for遍历背包。如果求排列数就是外层for遍历背包内层for循环遍历物品。相关题目如下求组合数动态规划518.零钱兑换II求排列数动态规划377. 组合总和 Ⅳ (opens new window)、动态规划70. 爬楼梯进阶版完全背包如果求最小数那么两层for循环的先后顺序就无所谓了相关题目如下求最小数动态规划322. 零钱兑换、动态规划279.完全平方数
