動態規劃三種基本背包問題模板
1.01背包
題目鏈接
有 N 件物品和一個容量是 V 的背包，每件物品只能使用一次，
第 i 件物品的體積是 vi，價值是 wi，
求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大，
輸出最大價值，
輸入格式
第一行兩個整數，N，V，用空格隔開，分別表示物品數量和背包容積，
接下來有 N 行，每行兩個整數 vi,wi，用空格隔開，分別表示第 i 件物品的體積和價值，
輸出格式
輸出一個整數，表示最大價值，
資料范圍
0<N,V≤1000
0<vi,wi≤1000
輸入樣例
4 5
1 2
2 4
3 4
4 5
輸出樣例：
8
代碼模板(二維)
#include<iostream>
#include<algorithm>
using namespace std;
int N,V;
int dp[1002][1002];
int v[1002],w[1002];
int main()
{
cin>>N>>V;
for(int i=1;i<=N;i++)
cin>>v[i]>>w[i];
for(int i=1;i<=N;i++)
{
for(int j=1;j<=V;j++)
{
dp[i][j]=dp[i-1][j];
if(j>=v[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
}
}
cout<<dp[N][V];
return 0;
}
代碼模板(一維)
#include<iostream>
#include<algorithm>
using namespace std;
int N,V;
int dp[1002];
int v[1002],w[1002];
int main()
{
cin>>N>>V;
for(int i=1;i<=N;i++)
cin>>v[i]>>w[i];
for(int i=1;i<=N;i++)
for(int j=V;j>=v[i];j--)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
cout<<dp[V];
return 0;
}
2.完全背包
題目鏈接
有 N 種物品和一個容量是 V 的背包，每種物品都有無限件可用，
第 ii 種物品的體積是 vi，價值是 wi，
求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大，
輸出最大價值，
輸入格式
第一行兩個整數，N，V，用空格隔開，分別表示物品種數和背包容積，
接下來有 NN 行，每行兩個整數 vi,wi，用空格隔開，分別表示第 i 種物品的體積和價值，
輸出格式
輸出一個整數，表示最大價值，
資料范圍
0<N,V≤1000
0<vi,wi≤1000
輸入樣例
4 5
1 2
2 4
3 4
4 5
輸出樣例：
10
代碼模板
#include<iostream>
#include<algorithm>
using namespace std;
int N,V;
int dp[1002];
int v[1002],w[1002];
int main()
{
cin>>N>>V;
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<=V;j++)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
cout<<dp[V];
return 0;
}
3.多重背包
題目鏈接
有 N 種物品和一個容量是 V 的背包，
第 i 種物品最多有 si 件，每件體積是 vi，價值是 wi，
求解將哪些物品裝入背包，可使物品體積總和不超過背包容量，且價值總和最大，
輸出最大價值，
輸入格式
第一行兩個整數，N，V，用空格隔開，分別表示物品種數和背包容積，
接下來有 N 行，每行三個整數 vi,wi,si，用空格隔開，分別表示第 i 種物品的體積、價值和數量，
輸出格式
輸出一個整數，表示最大價值，
資料范圍
0<N,V≤100
0<vi,wi,si≤100
輸入樣例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
輸出樣例：
10
代碼模板
#include<iostream>
#include<algorithm>
using namespace std;
int N,V;
int dp[1002];
int v[1002],w[1002],s[1002];
int main()
{
cin>>N>>V;
for(int i=1;i<=N;i++)
cin>>v[i]>>w[i]>>s[i];
for(int i=1;i<=N;i++)
for(int j=V;j>=v[i];j--)
for(int k=1;k<=s[i]&&k*v[i]<=j;k++)
dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);
cout<<dp[V];
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/455421.html
標籤：其他
上一篇：量子計算基礎——量子測量
下一篇：Java基礎——IO流—位元組流