江川区住房和城乡建设局网站,项目网站,用xp做网站是否先搭建iis,营销必备十大软件文章目录一、背包能否装满#xff1f;416. 分割等和子集1049. 最后一块石头的重量 II二、装满背包有几种方法#xff1f;494. 目标和518.零钱兑换II377. 组合总和 Ⅳ70. 爬楼梯三、背包装满的最大价值474.一和零四、装满背包最小物品数322. 零钱兑换279.完全平方数一、背包能…
文章目录一、背包能否装满416. 分割等和子集1049. 最后一块石头的重量 II二、装满背包有几种方法494. 目标和518.零钱兑换II377. 组合总和 Ⅳ70. 爬楼梯三、背包装满的最大价值474.一和零四、装满背包最小物品数322. 零钱兑换279.完全平方数一、背包能否装满
416. 分割等和子集 class Solution {
public:// 01背包逆序遍历// 组合问题先背包后容量bool canPartition(vectorint nums) {int m nums.size();int sum accumulate(nums.begin(), nums.end(), 0);if(sum 1) return false;int n sum / 2;vectorint dp(n 1, 0); // dp[j]容量为j的背包最多装入重量为dp[j]的物品for(int i 0; i m; i){for(int j n; j nums[i]; j--){dp[j] max(dp[j], dp[j - nums[i]] nums[i]);}}return dp[n] n;}
};dp背包问题——416. 分割等和子集
1049. 最后一块石头的重量 II class Solution {
public:// 01背包逆序遍历// 组合问题先物品、后容量int lastStoneWeightII(vectorint stones) {int m stones.size();int sum accumulate(stones.begin(), stones.end(), 0);int n sum / 2;vectorint dp(n 1, 0); // dp[j]容量为j的背包最多装dp[j]的石头for(int i 0; i m; i){for(int j n; j stones[i]; j--){dp[j] max(dp[j], dp[j - stones[i]] stones[i]);}}return sum - 2 * dp[n];}
};dp背包问题——1049. 最后一块石头的重量 II
二、装满背包有几种方法
494. 目标和 class Solution {
public:// 01背包逆序遍历// 组合问题先物品后容量int findTargetSumWays(vectorint nums, int target) {int sum accumulate(nums.begin(), nums.end(), 0);if((sum target) 1) return 0;int m nums.size();int n (sum target) / 2;if(n 0) return 0;vectorint dp(n 1, 0); // dp[j]装满容量为j的背包有dp[j]种方法dp[0] 1; // 装满容量为0的背包只有1种方法for(int i 0; i m; i){for(int j n; j nums[i]; j--){// 多了一个物品可选择后装满背包的方法数就是 没有当前物品可选时的方法数 选了当前物品的方法数dp[j] dp[j] dp[j - nums[i]];}}return dp[n];}
};dp背包解决组合问题——494. 目标和
518.零钱兑换II class Solution {
public:// 完全背包顺序遍历// 组合问题先物品、后容量int change(int amount, vectorint coins) {int m coins.size();int n amount;vectorint dp(n 1, 0); // dp[j]装满容量为j的背包有dp[j]种方式dp[0] 1;for(int i 0; i m; i){for(int j coins[i]; j n; j){// 多了一个物品可选后装满背包的方法数就是 没有当前物品可选时的方法数 选了当前物品的方法数dp[j] dp[j] dp[j - coins[i]];}}return dp[n];}
};dp完全背包问题解组合问题——零钱兑换
377. 组合总和 Ⅳ class Solution {
public:// 完全背包顺序遍历// 排列问题先容量后物品int combinationSum4(vectorint nums, int target) {int m nums.size();int n target;vectorint dp(n 1, 0); // dp[j]装满容量为j的背包物品的组合数为dp[j]dp[0] 1;for(int j 1; j n; j){for(int i 0; i m; i){if(j nums[i] dp[j] INT_MAX - dp[j - nums[i]]) dp[j] dp[j - nums[i]];}}return dp[n];}
};70. 爬楼梯 class Solution {
public:// 完全背包顺序遍历// 排列问题先容量后物品int climbStairs(int n) {int m 2;int nums[2] {1,2};vectorint dp(n 1, 0); // dp[j]装满容量为j的背包有dp[j]种方法dp[0] 1;for(int j 1; j n; j){for(int i 0; i m; i){if(j nums[i]) dp[j] dp[j] dp[j - nums[i]];}}return dp[n];}
};排列问题先容量后物品
如果物品为{12}假如此时容量为2容量为1的背包只能装物品1用当前容量遍历多个物品可以选择在装了物品1的基础上接着装也可以选择不在其基础上装直接装入物品2。当容量为3时也可以选择在装有物品2的基础上再装入物品1这样就出现了{21}
组合问题先物品后容量
如果物品为{123}假如此时容量为5 只有物品1用各个容量遍历此时无论是什么容量的背包都只能放入物品1 此时我们手拿着物品2对于每一个容量要么直接使用现在就装满的背包要么找一个剩余容量为2的背包放入当前物品2 接着我们手拿着物品3对于每一个容量要么直接使用现在就装满的背包要么找一个剩余容量为3的背包放入当前物品3
class Solution {
public:int climbStairs(int n) {vectorint dp(n 1, 0);dp[0] 1;dp[1] 1;for(int i 2; i n; i){dp[i] dp[i - 2] dp[i - 1]; // 要么爬1个台阶要么2个台阶}return dp[n];}
};三、背包装满的最大价值
474.一和零 class Solution {
public:// 01背包逆序遍历// 组合问题先物品、后容量int findMaxForm(vectorstring strs, int m, int n) {vectorvectorint dp(m 1, vectorint(n 1, 0)); // dp[i][j]装满容量为ij背包的最大价值for(string s : strs){int w0 0;int w1 0;for(char c : s){if(c 0) w0;else w1;}// 每次循环计算出的dp[m][n]表示只有前几个物品可选时所获得的最大价值for(int i m; i w0; i--){for(int j n; j w1; j--){dp[i][j] max(dp[i][j], dp[i - w0][j - w1] 1); // 1表示价值}}}return dp[m][n];}
};四、装满背包最小物品数
322. 零钱兑换 class Solution {
public:// 问装满背包需要最少的物品数int coinChange(vectorint coins, int amount) {// 完全背包顺序遍历// 组合问题先物品、后容量装满就行不在意装入的顺序int m coins.size();int n amount;// 凑成面值n最多需要n个硬币初始化为n 1即可vectorint dp(n 1, n 1); // dp[j]装满容量为j的背包至少需要dp[j]个物品dp[0] 0;for(int i 0; i m; i){for(int j coins[i]; j n; j){// 装满容量为j的背包要么直接用前面的物品装满要么找一个剩余容量为coins[i]的背包放入coins[i]dp[j] min(dp[j], dp[j - coins[i]] 1); }}return dp[n] n 1 ? -1 : dp[n];}
};279.完全平方数 class Solution {
public:// 物品为[1,4,9,...]// 容量为n问装满背包至少需要几个物品int numSquares(int n) {// 完全背包顺序遍历// 组合问题先物品、后容量vectorint dp(n 1, n);dp[0] 0;for(int i 1; i n / i; i){for(int j i * i; j n; j){dp[j] min(dp[j], dp[j - i * i] 1);}}return dp[n];}
};
