当前位置：首页 > news >正文

代码随想录算法训练营第三十六天|完全背包理论基础、518. 零钱兑换 II、377. 组合总和 Ⅳ、70. 爬楼梯。

news 2026/3/26 18:56:40

理论基础

完全背包(二维)

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
52. 携带研究材料（第七期模拟笔试）

#include<bits/stdc++.h>usingnamespacestd;intmain(){intn,v;cin>>n>>v;vector<int>wi(n);vector<int>vi(n);for(inti=0;i<n;i++){cin>>wi[i]>>vi[i];}//在装上前i个物品里，在总重量为j要求下的最大价值vector<vector<int>>dp(n,vector<int>(v+1,0));for(intj=wi[0];j<=v;j++){dp[0][j]=dp[0][j-wi[0]]+vi[0];}for(inti=1;i<n;i++){for(intj=0;j<=v;j++){if(j<wi[i])dp[i][j]=dp[i-1][j];elsedp[i][j]=max(dp[i][j-wi[i]]+vi[i],dp[i-1][j]);}}cout<<dp[n-1][v];return0;}

完全背包(一维)

对于纯完全背包问题，其for循环的先后循环是可以颠倒的！
但如果题目稍稍有点变化，就会体现在遍历顺序上。（如求组合数和排列数）

#include<iostream>#include<vector>usingnamespacestd;intmain(){intN,bagWeight;cin>>N>>bagWeight;vector<int>weight(N,0);vector<int>value(N,0);for(inti=0;i<N;i++){intw;intv;cin>>w>>v;weight[i]=w;value[i]=v;}vector<int>dp(bagWeight+1,0);for(intj=0;j<=bagWeight;j++){// 遍历背包容量for(inti=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;return0;}

练习

518. 零钱兑换 II

518. 零钱兑换 II - 力扣（LeetCode）

classSolution{public:intchange(intamount,vector<int>&coins){//装满i的组合数vector<longlong>dp(amount+1,0);dp[0]=1;for(inti=0;i<coins.size();i++){for(intj=coins[i];j<=amount;j++){if(dp[j]<INT_MAX-dp[j-coins[i]]){//防止相加数据超过int,题目保证了最终结果 dp[amount] 是一个合法的 32 位整数。dp[j]+=dp[j-coins[i]];}}}returndp[amount];}};

377. 组合总和 Ⅳ(排列数)

377. 组合总和 Ⅳ - 力扣（LeetCode）

注意是排列，不是只组合

classSolution{public:intcombinationSum4(vector<int>&nums,inttarget){//dp[i]: 凑成目标正整数为i的排列个数为dp[i]vector<int>dp(target+1,0);dp[0]=1;//求组合数// for(int i=0;i<nums.size();i++) {// for(int j=nums[i];j<=target;j++) {// if(dp[j]<=INT_MAX-dp[j-nums[i]]) {// dp[j]+=dp[j-nums[i]];// }// }// }for(inti=0;i<=target;i++){// 遍历背包for(intj=0;j<nums.size();j++){// 遍历物品if(i-nums[j]>=0&&dp[i]<=INT_MAX-dp[i-nums[j]]){dp[i]+=dp[i-nums[j]];}}}returndp[target];}};

70. 爬楼梯（进阶）

57. 爬楼梯（第八期模拟笔试）

#include<bits/stdc++.h>usingnamespacestd;intmain(){intn,m;cin>>n>>m;vector<int>dp(n+1,0);dp[0]=1;for(inti=1;i<=n;i++){//楼梯for(intj=1;j<=m;j++){//步数if(i>=j)dp[i]+=dp[i-j];}}cout<<dp[n];return0;}