正向01背包和数组保存简化背包

#include <iostream> #include <string.h> #include <algorithm> using namespace std; int dp[20][20]; int m,n; int w[20],v[20]; int rec(int i,int j) { if(dp[i][j]>=0) { return dp[i][j]; } int res; if(i==n) { res=0; } else if(j<w[i]) { res=rec(i+1,j); } else { res=max(rec(i+1,j),rec(i+1,j-w[i])+v[i]); } return dp[i][j]=res; } int main () { cin >> m >> n; memset(dp,0,sizeof(dp)); for(int i=0; i<m; i++) { cin >> w[i] >> v[i]; } // Ccout << rec (0,n); for(int i=0;i<m;i++) { for(int j=0;j<=n;j++) { if(j<w[i]) { dp[i+1][j]=dp[i][j]; } else { dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]); } } } cout << dp[m-1][n]; return 0; }

m是数量，n是容量

#include <iostream> #include <string.h> #include <algorithm> using namespace std; int dp[200][200]; int m,n; int w[2000],v[2000]; //int rec(int i,int j) //{ // // if(dp[i][j]>=0) // { // return dp[i][j]; // } // int res; // if(i==n) // { // res=0; // } // else if(j<w[i]) // { // res=rec(i+1,j); // } // else // { // res=max(rec(i+1,j),rec(i+1,j-w[i])+v[i]); // } // return dp[i][j]=res; //} int main () { cin >> m >> n; memset(dp,0,sizeof(dp)); for(int i=0; i<m; i++) { cin >> w[i] >> v[i]; } // Ccout << rec (0,n); // for(int i=0;i<m;i++) // { // for(int j=0;j<=n;j++) // { // if(j<w[i]) // { // dp[i+1][j]=dp[i][j]; // // } // else // { // dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]); // } // } // } for(int i=0;i<m;i++) { for(int j=0;j<=n;j++) { dp[i+1][j]=max(dp[i+1][j],dp[i][j]); if(j+w[i]<=n) { dp[i+1][j+w[i]]=max(dp[i+1][j+w[i]],dp[i][j]+v[i]); } } } cout << dp[m-1][n]; return 0; }