01背包
n個物品，v的體積，求最多能裝下的價值
每個物品只能拿一次
https://www.acwing.com/problem/content/2/
1 #include<bits/stdc++.h> 2 using namespace std; 3 int main(){ 4 int N,V,dp[1005] = {0}; 5 scanf("%d%d",&N,&V); 6 for(int i=1,x,y;i<=N;i++){ 7 scanf("%d%d",&x,&y); 8 for(int j=V;j>=x;j--){ 9 dp[j] = max(dp[j],dp[j-x]+y); 10 } 11 } 12 printf("%d\n",dp[V]); 13 return 0; 14 }代碼
完全背包
n個物品，v的體積，求最多能裝下的價值
每個物品可以拿無限次
https://www.acwing.com/problem/content/3/
1 #include<bits/stdc++.h> 2 using namespace std; 3 int main(){ 4 int N,V,dp[1005] = {0}; 5 scanf("%d%d",&N,&V); 6 for(int i=1,x,y;i<=N;i++){ 7 scanf("%d%d",&x,&y); 8 for(int j=x;j<=V;j++){ 9 dp[j] = max(dp[j],dp[j-x]+y); 10 } 11 } 12 printf("%d\n",dp[V]); 13 return 0; 14 }代碼
多重背包
n個物品，v的體積，求最多能裝下的價值
每個物品可以拿ki次
https://www.acwing.com/problem/content/5/
一個優化：（二進制優化）
顯然我們沒有必要跑全ki次，判斷下能用完全背包的就用完全背包好了
不能用完全背包的，考慮一個等價的次數，即，每次取1個，2個，4個，，，ki-2j+1個
j是最大的能使ki-2j+1>0的數
也就是說我們將ki二進制拆分了
時間復雜度為O(n*m*log(∑ki))
另一個優化：（單調佇列優化）
————咕咕咕——————
時間復雜度O(n*m)
https://www.acwing.com/problem/content/6/
/*author:revolIA*/ #include<bits/stdc++.h> #define max(x,y) (x>y?x:y) using namespace std; typedef long long ll; int main(){ ll N,V,dp[20005] = {0}; scanf("%lld%lld",&N,&V); for(ll i=1,x,y,z;i<=N;i++){ scanf("%lld%d%lld",&x,&y,&z); if(x*z>V){ for(int j=x;j<=V;j++){ dp[j] = max(dp[j],dp[j-x]+y); } }else{ for(ll tmp = 1;z-tmp+1 > 0;tmp <<= 1){ ll k = (z-(tmp<<1)+1)<0?z-tmp+1:tmp; for(ll j=V;j>=x*k;j--){ dp[j] = max(dp[j],dp[j-x*k]+y*k); } } } } printf("%lld\n",dp[V]); return 0; }View Code
混合背包
前三個混在一起，加個if判斷即可
https://www.acwing.com/problem/content/submission/7/
/*author:revolIA*/ #include<bits/stdc++.h> #define max(a,b) (a>b?a:b) typedef long long ll; using namespace std; const int maxn = 2e4+7; int dp[maxn]; int main(){ int n,m; scanf("%d%d",&n,&m); while(n--){ int k,value,cnt; scanf("%d%d%d",&k,&value,&cnt); if(cnt == -1){ for(int i=m;i>=k;i--){ dp[i] = max(dp[i],dp[i-k]+value); } }else if(cnt == 0 || k*cnt>=m){ for(int i=k;i<=m;i++){ dp[i] = max(dp[i],dp[i-k]+value); } }else{ for(int i=1;cnt-i+1>0;i<<=1){ int tmp = (cnt-(i<<1)+1)<0?cnt-i+1:i; for(int j=m;j>=tmp*k;j--){ dp[j] = max(dp[j],dp[j-tmp*k]+tmp*value); } } } } printf("%d\n", dp[m]); return 0; }View Code
二維費用的背包問題
物體不止有體積這個限制條件，還有質量這個限制條件
n個物體，v的背包容積，m的負重限制，還是01背包只能拿一個
https://www.acwing.com/problem/content/submission/8/
/*author:revolIA*/ #include<bits/stdc++.h> #define max(a,b) (a>b?a:b) typedef long long ll; using namespace std; const int maxn = 1e3+7; int dp[maxn][maxn]; int main(){ int n,v,m; scanf("%d%d%d",&n,&v,&m); while(n--){ int volum,weight,value; scanf("%d%d%d",&volum,&weight,&value); for(int i=v;i>=volum;i--){ for(int j=m;j>=weight;j--){ dp[i][j] = max(dp[i][j],dp[i-volum][j-weight]+value); } } } printf("%d\n",dp[v][m]); return 0; }View Code
分組背包問題
每組只能拿一個，這樣調整下for的順序就好了
https://www.acwing.com/problem/content/submission/9/
/*author:revolIA*/ #include<bits/stdc++.h> #define max(a,b) (a>b?a:b) typedef long long ll; using namespace std; const int maxn = 1e3+7; int dp[maxn]; int weight[maxn],value[maxn]; int main(){ int n,m; scanf("%d%d",&n,&m); while(n--){ int cnt; scanf("%d",&cnt); for(int i=1;i<=cnt;i++){ scanf("%d%d",&weight[i],&value[i]); } for(int i=m;i>=0;i--){ for(int j=1;j<=cnt;j++)if(i>=weight[j]){ dp[i] = max(dp[i],dp[i-weight[j]]+value[j]); } } } printf("%d\n",dp[m]); return 0; }View Code
有依賴的背包問題
要想拿當前物體，必須拿它的父親
用dfs先處理處子節點，然后拿出當前節點（因為必須拿當前才能拿子節點）
做一個背包，然后把當前節點更新進去
https://www.acwing.com/problem/content/submission/10/
/*author:revolIA*/ #include<bits/stdc++.h> #define max(x,y) (x>y?x:y) using namespace std; typedef long long ll; const int maxn = 107; int n,m,root; int head[maxn],to[maxn],Next[maxn],tot = 1; int dp[maxn][maxn],val[maxn],wei[maxn]; void Add(int u,int v){ to[tot] = v; Next[tot] = head[u]; head[u] = tot++; } void dfs(int u){ for(int i=head[u];i;i=Next[i]){ int son = to[i]; dfs(son); for(int j=m-wei[u];j>=wei[son];j--){ for(int k=wei[son];k<=j;k++){ dp[u][j] = max(dp[u][j],dp[u][j-k]+dp[son][k]); } } } for(int i=m;i>=wei[u];i--)dp[u][i] = dp[u][i-wei[u]]+val[u]; for(int i=0;i<wei[u];i++)dp[u][i] = 0; } int main(){ scanf("%d%d",&n,&m); for(int i=1,x;i<=n;i++){ scanf("%d%d%d",&wei[i],&val[i],&x); if(~x)Add(x,i); else root = i; } dfs(root); printf("%d\n",dp[root][m]); return 0; }View Code
背包問題求方案數
加一個陣列，更新即可
https://www.acwing.com/problem/content/submission/11/
/*author:revolIA*/ #include<bits/stdc++.h> #define max(x,y) (x>y?x:y) using namespace std; typedef long long ll; const int maxn = 1e5+7,mod = 1e9+7; int n,m; int dp[maxn],ans[maxn]; int main(){ scanf("%d%d",&n,&m); fill(ans,ans+n,1); for(int i=1,x,y;i<=n;i++){ scanf("%d%d",&x,&y); for(int j=m;j>=x;j--){ if(dp[j]<dp[j-x]+y){ ans[j] = ans[j-x]; }else if(dp[j] == dp[j-x]+y){ ans[j] += ans[j-x]; ans[j] %= mod; } dp[j] = max(dp[j],dp[j-x]+y); } } printf("%d\n",ans[m]); return 0; }View Code
背包問題求具體方案
求字典序最小的方案
倒著來一遍背包，然后正著掃描一遍
https://www.acwing.com/problem/content/submission/12/
/*author:revolIA*/ #include<bits/stdc++.h> #define max(x,y) (x>y?x:y) using namespace std; typedef long long ll; const int maxn = 1e3+7,mod = 1e9+7; int n,m; int dp[maxn][maxn]; int x[maxn],y[maxn]; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d%d",&x[i],&y[i]); } for(int i=n;i>=1;i--){ for(int j=0;j<x[i];j++) dp[i][j] = dp[i+1][j]; for(int j=x[i];j<=m;j++) dp[i][j] = max(dp[i+1][j],(dp[i+1][j-x[i]]+y[i])); } for(int i=1;i<=n;i++){ if(m>=x[i] && dp[i][m] == dp[i+1][m-x[i]]+y[i]){ printf("%d ",i); m -= x[i]; } } return 0; }View Code
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/100182.html
標籤：C++
上一篇：C++生成亂數
下一篇：C++分治策略實作快速排序