1 01背包问题
当前有N件物品和一个V的背包,第i个物品的体积为C(i),价值为w(i)
每件物品只能选择放或者不放
模版
#include <iostream>
#include <cstring>
using namespace std;
int dp[21][1010];
int w[21],c[21];
int main() {int N,V;cin>>N>>V;for(int i=1;i<=N;i++) {cin>>w[i]>>c[i];}for(int i=1;i<=N;i++) {for(int j=0;j<=V;j++) {if(j>=c[i]) {dp[i][j]=max(dp[i-1][j-c[i]]+w[i],dp[i-1][j]);} else {dp[i][j]=dp[i-1][j];}}}cout<<dp[N][V]<<endl;return 0;
}
2 多重背包问题
N个物品,V的容量,第i个物品的占用空间为C(i),价值为W(i),有n个。
模版:
#include <iostream>
#include <cstring>
using namespace std;
int dp[21][1010];
int w[21],c[21],n[21];
int main() {int N,V;cin>>N>>V;for(int i=1;i<=N;i++) {cin>>w[i]>>c[i]>>n[i];}for(int i=1;i<=N;i++) {for(int j=0;j<=V;j++) {for(int k=0;k<=n[i];k++) {if(j>=c[i]*k) {dp[i][j]=max(dp[i-1][j-c[i]*k]+w[i]*k,dp[i][j]);}}}}cout<<dp[N][V]<<endl;return 0;
}
3 完全背包问题
除了物品数量无限制外其余同01背包
模版
#include <iostream>
#include <cstring>
using namespace std;
int dp[21][1010];
int w[21],c[21];
int main() {int N,V;cin>>N>>V;for(int i=1;i<=N;i++) {cin>>w[i]>>c[i];}for(int i=1;i<=N;i++) {for(int j=0;j<=V;j++) {if(j>=c[i]) {dp[i][j]=max(dp[i][j-c[i]]+w[i],dp[i-1][j]);} else {dp[i][j]=dp[i-1][j];}}}cout<<dp[N][V]<<endl;return 0;
}