题目分析:简单的01背包
#include<iostream> #include<cstdio> using namespace std; int f[1100]; int w[1100],v[1100]; int main() { int t,i,j; cin>>t; while(t--) { int N,V; cin>>N>>V; for(i=1;i<=N;i++) cin>>w[i];//¼ÛÖµ for(i=1;i<=N;i++) cin>>v[i];//Ìå»ý memset(f,0,sizeof(f)); for(i=1;i<=N;i++) for(j=V;j>=v[i];j--) { if(f[j]<f[j-v[i]]+w[i]) f[j]=f[j-v[i]]+w[i]; } printf("%d\n",f[V]); } //system("pause"); return 0; }
//用 二位数组做竟然过不了****纳闷呀 #include<iostream> #include<cstdio> using namespace std; int f[1100][1100]; int w[1100],v[1100]; int main() { int t; cin>>t; while(t--) { int N,V; cin>>N>>V; for(int i=1;i<=N;i++) cin>>w[i];//价值 for(int i=1;i<=N;i++) cin>>v[i];//体积 memset(f,0,sizeof(f)); for(int i=1;i<=N;i++) for(int j=V;j>=v[i];j--) { if(f[i-1][j]<f[i-1][j-v[i]]+w[i]) f[i][j]=f[i-1][j-v[i]]+w[i]; /*else f[i][j]=f[i-1][j];*/ } /* for(int i=1;i<=N;i++) { for(int j=1;j<=V;j++) cout<<f[i][j]<<"* "; cout<<endl; }*/ printf("%d\n",f[N][V]); } system("pause"); return 0; }