【贪心】0/1背包

贵有恒，何必三更起五更眠；最无益，莫过一日曝十日寒。

问题 P: 【贪心】0/1背包

【贪心】0/1背包

时间限制: 1 Sec 内存限制: 128 MB

题目描述

有一容量为weight的背包。现在要从n件物品中选取若干装入背包中，每件物品i的重量为w[i]，价值为p[i]。定义一种可行的背包装载为：背包中物品的总重量不能超过背包的容量，并且一个物品要么全部选取，要么不选取。定义最佳装载是指所装入的物品价值最高，并且是可行的背包装载。

输入

第1行一个整数，表示背包的重量weight 第2行一个整数，表示n件物品第3行有n个整数，分别表示n个物品的重量第4行有n个整数，分别表示n个物品的价值

输出

共两行。第1行n个物品的选取状态，0表示不取，1表示取。n个状态用空格分隔，行尾无空格。第2行表示装入物品的最高价值。

样例输入

样例输出

0 1 0 1
23

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int lm,n,weight,w[1111],v[1111],last[1111],dlast[1111];
 7 
 8 
 9 void ss(int i,int dm,int dw)    
10 {
11 /*
12 i——第i个物品
13 dm——当前的最大价值
14 dw——当前的重量
15 */
16     if(i<n)
17     {
18         dlast[i]=0;
19         ss(i+1,dm,dw);
20         if(weight>=dw+w[i])
21         {
22             dm+=v[i];
23             dw+=w[i];
24             dlast[i]=1;
25             ss(i+1,dm,dw);
26         }
27     }
28     else
29     {
30         if(dm>lm)
31         {
32             for(int i=0;i<n;i++)
33                 last[i]=dlast[i];
34             lm=dm;
35         }
36     }
37 }
38 
39 int main()
40 {
41     while(cin>>weight>>n)
42     {
43         lm=0;
44         memset(last,0,sizeof(last));
45         memset(dlast,0,sizeof(dlast));
46         for(int i=0;i<n;i++)
47             cin>>w[i];
48         for(int i=0;i<n;i++)
49             cin>>v[i];
50         ss(0,0,0);
51         for(int i=0;i<n;i++)
52         {
53             if(i==n-1)  //行尾不能有空格
54             {
55                 cout<<last[i]<<endl;
56                 break;
57             }
58             cout<<last[i]<<" ";
59         }
60         cout<<lm<<endl;
61     }
62     return 0;
63 }