01背包
上面讲的很清楚了,直接贴代码了:
通过搜索解决:
1 /* 有n个物品,每个物品有两种情况,放或不放,所以有2^n种可能性, 2 我们比较所有的可能性,就会得出最优解*/ 3 #include <iostream> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 8 const int MAXN=105; 9 int w[MAXN],v[MAXN]; //w[i],v[i]分别表示第i个物品的重量w[i]和价值v[i] 10 int N,V; 11 int dp[MAXN][MAXN]; 12 13 //穷竭化搜索O(2^n) 14 int rec(int step,int j){ 15 int res=0; 16 if(step==N){ 17 return 0; 18 } 19 20 if(w[step]>j){ 21 rec(step+1,j); 22 }else{ 23 res=max(rec(step+1,j),rec(step+1,j-w[step])+v[step]); 24 } 25 return res; 26 } 27 28 //记忆化搜索O(nW) 29 int mrec(int step,int j){ 30 if(step==N) 31 return 0; 32 if(dp[step][j]!=-1) 33 return dp[step][j]; 34 35 int res=0; 36 37 if(w[step]>j){ 38 res=rec(step+1,j); 39 }else{
//比较选,或不选 40 res=max(rec(step+1,j),res(step+1,j-w[step])+v[step]); 41 }
//将结果记录到数组中 42 dp[step][j]=res; 43 return res; 44 } 45 int main(){ 46 while(cin>>N){ 47 for(int i=0;i<N;i++) 48 cin>>w[i]>>v[i]; 49 int W; 50 cin>>W; 51 memset(dp,-1,sizeof(dp)); 52 cout<<rec(0,W)<<endl; 53 } 54 }
//动态规划
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 const int MAXN=100; 7 int f1[MAXN],f2[MAXN],f[MAXN]; 8 int w[MAXN],c[MAXN] ; //w,c分别代表物品的价值和体积 9
//这个v是从0开始的所以要用两个一维坐标 10 int dp1(int N,int V){ 11 memset(f1,0,sizeof(f2)); 12 for(int i=0;i<N;i++){ 13 for(int v=c[i];v<=V;v++){ 14 f2[v]=max(f1[v],f1[v-c[i]]+w[i]); 15 } 16 memcpy(f1,f2,sizeof(f2)); 17 } 18 return f2[V]; 19 } 20 //这个的v是从V开始的所以用一个一维坐标就行了 21 int dp2(int N,int V){ 22 memset(f,0,sizeof(f)); 23 for(int i=0;i<N;i++) 24 for(int v=V;v-c[i]>=0;v--) 25 f[v]=max(f[v],f[v-c[i]]+w[i]); 26 return f[V]; 27 } 28 29 30 int main(){ 31 int N,V; 32 while(cin>>N>>V){ 33 for(int i=0;i<N;i++){ 34 cin>>w[i]>>c[i]; 35 } 36 cout<<dp1(N,V)<<endl; 37 cout<<dp2(N,V)<<endl; 38 } 39 }