目錄

• 218. 01背包問(wèn)題【經(jīng)典模型】
• 220. 最長(zhǎng)公共子序列問(wèn)題【經(jīng)典模型】
• 219. 完全背包問(wèn)題【經(jīng)典模型】
• 221. 01背包問(wèn)題之 2【經(jīng)典模型】
• 222. 多重部分和問(wèn)題【中 有意思】
• 223. 最長(zhǎng)上升子序列問(wèn)題【經(jīng)典模型】

218. 01背包問(wèn)題【經(jīng)典模型】

https://www.papamelon.com/problem/218
狀態(tài)表示: f[i][j] 表示從前i個(gè)物品中選 總體積不超過(guò)j的最大價(jià)值

#include<bits/stdc++.h> using namespace std; const int N=1010; int f[110][N],n,m,w[N],v[N]; int main(void) {cin>>n>>m;for(int i=1;i<=n;i++) cin>>v[i]>>w[i];for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){f[i][j]=f[i-1][j];if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);}}cout<<f[n][m];return 0; }

其實(shí)可以邊讀入邊計(jì)算。

#include<bits/stdc++.h> using namespace std; const int N=1010; int f[110][N],n,m,w[N],v[N]; int main(void) {cin>>n>>m;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];for(int j=0;j<=m;j++){f[i][j]=f[i-1][j];if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);}}cout<<f[n][m];return 0; }

優(yōu)化空間至一維。

#include<bits/stdc++.h> using namespace std; const int N=1010; int f[N],n,m,w[N],v[N]; int main(void) {cin>>n>>m;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];for(int j=m;j>=v[i];j--){f[j]=max(f[j],f[j-v[i]]+w[i]);}}cout<<f[m];return 0; }

220. 最長(zhǎng)公共子序列問(wèn)題【經(jīng)典模型】

https://www.papamelon.com/problem/220
狀態(tài)表示: f[i][j] 表示a的前i個(gè)字符 和 b的前j個(gè)字符的最長(zhǎng)公共子序列個(gè)數(shù)

• a的第i個(gè)不選,b的第j個(gè)也不選f[i-1][j-1]
• a的第i個(gè)選,b的第j個(gè)不選f[i][j-1]
• a的第i個(gè)不選,b的第j個(gè)選f[i-1][j]
• a的第i個(gè)選,b的第j個(gè)也選。這時(shí)候就要判斷a[i]是否等于b[j] 如果相等則f[i-1][j-1]+1

#include<bits/stdc++.h> using namespace std; const int N=1e3+10; int f[N][N],n,m; char a[N],b[N]; int main(void) {cin>>n>>m>>a+1>>b+1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){f[i][j]=max({f[i-1][j-1],f[i][j-1],f[i-1][j]});if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);}}cout<<f[n][m]<<endl;return 0; }

其實(shí)都不選的狀態(tài)可以不用寫(xiě)，因?yàn)槠渌膸追N狀態(tài)就已經(jīng)包含了。

#include<bits/stdc++.h> using namespace std; const int N=1e3+10; int f[N][N],n,m; char a[N],b[N]; int main(void) {cin>>n>>m>>a+1>>b+1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){f[i][j]=max(f[i][j-1],f[i-1][j]);if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);}}cout<<f[n][m]<<endl;return 0; }

219. 完全背包問(wèn)題【經(jīng)典模型】

https://www.papamelon.com/problem/219

#include<bits/stdc++.h> using namespace std; const int N=10100; int f[110][N],n,m,w[N],v[N]; int main(void) {cin>>n>>m;for(int i=1;i<=n;i++) cin>>v[i]>>w[i];for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){f[i][j]=f[i-1][j];if(j>=v[i]) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);}}cout<<f[n][m];return 0; } #include<bits/stdc++.h> using namespace std; const int N=10100; int f[N],n,m,w[N],v[N]; int main(void) {cin>>n>>m;for(int i=1;i<=n;i++) cin>>v[i]>>w[i];for(int i=1;i<=n;i++){for(int j=v[i];j<=m;j++){f[j]=max(f[j],f[j-v[i]]+w[i]);}}cout<<f[m];return 0; }

221. 01背包問(wèn)題之 2【經(jīng)典模型】

https://www.papamelon.com/problem/221
通過(guò)分析，你會(huì)發(fā)現(xiàn)我們的體積是太大了，但是有一個(gè)就是我們的價(jià)值和很小的。
故f[i][j] 表示再前i中選總價(jià)值為j 的最小體積 其本質(zhì)基于貪心的思維，對(duì)于同樣價(jià)值的物品我們肯定是希望浪費(fèi)的體積越小越好。
最后我們?cè)诎纯們r(jià)值從大到小枚舉，第一個(gè)體積小于我們背包總體積的就是答案。

#include<bits/stdc++.h> using namespace std; const int N=1e4+10; int f[110][N],n,m,w[N],v[N]; int main(void) {cin>>n>>m;for(int i=1;i<=n;i++) cin>>v[i]>>w[i];memset(f,0x3f,sizeof f);for(int i=0;i<=n;i++) f[i][0]=0;for(int i=1;i<=n;i++){for(int j=0;j<N;j++){f[i][j]=f[i-1][j];if(j>=w[i]) f[i][j]=min(f[i][j],f[i-1][j-w[i]]+v[i]);}}for(int i=N-1;i>=0;i--){if(f[n][i]<=m){cout<<i;break;}}return 0; }

222. 多重部分和問(wèn)題【中 有意思】

https://www.papamelon.com/problem/222
f[i][j] 表示前i個(gè)數(shù),總和為j。第i類(lèi)剩余的個(gè)數(shù)

#include<bits/stdc++.h> using namespace std; const int N=110; const int M=1e5+10; int f[N][M],a[N],cnt[N],n,m; //f[i][j] 表示前i個(gè)數(shù),總和為j。第i類(lèi)剩余的個(gè)數(shù) int main(void) {cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>cnt[i];memset(f,-1,sizeof f);for(int i=1;i<=n;i++) f[i][0]=cnt[i];for(int i=1;i<=n;i++) {for(int j=0;j<=m;j++){if(f[i-1][j]>=0) f[i][j]=cnt[i];//不拿if(j>=a[i]&&f[i][j-a[i]]>0) f[i][j]=max(f[i][j],f[i][j-a[i]]-1);//拿}}if(f[n][m]>=0) puts("Yes");else puts("No");return 0; }

223. 最長(zhǎng)上升子序列問(wèn)題【經(jīng)典模型】

https://www.papamelon.com/problem/223
f[i] 表示以i結(jié)尾的最長(zhǎng)上升子序列

#include<bits/stdc++.h> using namespace std; const int N=1010; int f[N],n,a[N]; int main(void) {cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++){f[i]=1;for(int j=1;j<i;j++)if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);}int ans=0;for(int i=1;i<=n;i++) ans=max(ans,f[i]);cout<<ans;return 0; }

總結(jié)

以上是生活随笔為你收集整理的第 2 章：初出茅庐【初级篇 - 2.3 动态规划】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。