HDU--2602 (0-1背包)
#include<iostream> using namespace std; #define N 1010 int w[N],v[N],f[N][N]; //f[i][j]---背包容量为j存放前i件物品的最大价值 int main() { int vol,i,num,t; //num---物品的数量,vol---背包的容量,value--背包的最大价值 cin>>t; while(t--) { memset(f,0,sizeof(f)); cin>>num>>vol; for(i=1;i<=num;i++) cin>>v[i]; for(i=1;i<=num;i++) cin>>w[i]; for(i=1;i<=num;i++) for(int j=vol;j>=0;j--) { if(j>=w[i]) f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]); else f[i][j]=f[i-1][j]; } cout<<f[num][vol]<<endl; } return 0; }
注:全局变量在静态存储区分配内存,局部变量是在栈上分配内存空间的
VC堆栈默认是1M
上述代码也可用一维数组(备忘录记录区--dp[N])
#include<iostream> using namespace std; #define N 1010 int w[N],v[N],dp[N]; //f[i][j]---背包容量为j存放前i件物品的最大价值 int main() { int vol,i,num,t; //num---物品的数量,vol---背包的容量,value--背包的最大价值 cin>>t; while(t--) { memset(dp,0,sizeof(dp)); cin>>num>>vol; for(i=1;i<=num;i++) cin>>v[i]; for(i=1;i<=num;i++) cin>>w[i]; for(i=1;i<=num;i++) for(int j=vol;j>=w[i];j--) { dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } cout<<dp[vol]<<endl; } return 0; }