各类背包问题

1、0-1背包问题

（1）用二维数组动态规划

#include<bits/stdc++.h>
using namespace std;
int m,n;
int w[50],c[50];
int dp[210][210];
int main()
{cin>>m>>n;for(int i=1;i<=n;i++){cin>>w[i]>>c[i];}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(w[i]<=j) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i]);else dp[i][j]=dp[i-1][j];}cout<<dp[n][m];return 0;
}

（2）一维数组解法

#include <bits/stdc++.h>
using namespace std;int m,n;
int w[100],v[100];
int dp[200];
int main()
{cin>>m>>n;for(int i=1; i<=n; i++){cin>>w[i]>>v[i];}for(int i=1; i<=n; i++){//01背包用一维数组，要从数组右边开始循环for(int j=m; j>=1; j--){if(j>=w[i]){dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}}}cout<<dp[m];
}

2、完全背包问题

（1）二维数组解法

#include <bits/stdc++.h>
using namespace std;
int m,n;
int w[210],c[210];
int f[210][210];
int main()
{cin>>m>>n;for(int i=1;i<=n;i++)cin>>w[i]>>c[i];for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(w[i]>j) f[i][j]=f[i-1][j];else{f[i][j]=max(f[i-1][j],f[i][j-w[i]]+c[i]);}}}cout<<"max="<<f[n][m]<<endl;return 0;
}

（2）一维数组解法

完全背包用一维数组，要从数组左边开始循环

#include <bits/stdc++.h>
using namespace std;int m,n;
int w[100],v[100];
int dp[200];
int main()
{cin>>m>>n;for(int i=1; i<=n; i++){cin>>w[i]>>v[i];}for(int i=1; i<=n; i++){//完全背包用一维数组，要从数组左边开始循环for(int j=1; j<=m; j++){if(j>=w[i]){dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}}}cout<<"max="<<dp[m];
}