0-1背包专题

第一题：

HDU2546 饭卡

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2546

题目意思：中文题目，不解释题意

思路：选出最贵的一道菜和其他菜分离出来，然后把预算减去5元，以剩下的预算和剩下的菜进行0-1背包，然后将M-dp[M-5]-maxdish就是答案。

代码：

 1 //Author: xiaowuga
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <set>
 5 #include <vector>
 6 #include <queue>
 7 #include <cmath>
 8 #include <cstring>
 9 #include <cstdio>
10 #include <ctime>
11 #include <map>
12 #include <bitset>
13 #include <cctype>
14 #define maxx INT_MAX
15 #define minn INT_MIN
16 #define inf 0x3f3f3f3f
17 #define mem(s,ch) memset(s,ch,sizeof(s))
18 #define nc cout<<"nc"<<endl
19 #define sp " "
20 const long long N=100000; 
21 using namespace std;
22 typedef long long LL;
23 typedef int II;
24 II n,M;
25 II dish[N];
26 II d[N];
27 II ct=1;
28 II dp[N];
29 II maxdish;
30 void DP(){
31     II V=M-5;
32     mem(dp,0);
33     for(II i=1;i<ct;i++)
34         for(II j=V;j>=d[i];j--){
35             dp[j]=max(dp[j],dp[j-d[i]]+d[i]);
36         }
37 }
38 int main() {
39     ios::sync_with_stdio(false);cin.tie(0);
40     while(cin>>n&&n){
41         maxdish=-inf;
42         ct=1;
43         II pos;
44         for(II i=1;i<=n;i++){
45             cin>>dish[i];
46             if(maxdish<dish[i]){
47                 maxdish=dish[i];
48                 pos=i;
49             }
50         }
51         for(int i=1;i<=n;i++){
52             if(i!=pos) d[ct++]=dish[i];
53         }
54         cin>>M;
55         if(M<5){
56             cout<<M<<endl;continue;
57         }
58         DP();
59         cout<<M-dp[M-5]-maxdish<<endl;
60     }    
61     return 0;
62 }

View Code

第二题：

UVA624 CD

题目链接：https://vjudge.net/problem/UVA-624

题目意思：非常常规的0-1背包，唯一的就是需要打印路径，采用的是递归打印的方法

代码：

 1 //Author: xiaowuga
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <set>
 5 #include <vector>
 6 #include <queue>
 7 #include <cmath>
 8 #include <cstring>
 9 #include <cstdio>
10 #include <ctime>
11 #include <map>
12 #include <bitset>
13 #include <cctype>
14 #define maxx INT_MAX
15 #define minn INT_MIN
16 #define inf 0x3f3f3f3f
17 #define mem(s,ch) memset(s,ch,sizeof(s))
18 #define nc cout<<"nc"<<endl
19 #define sp " "
20 const long long N=100000; 
21 using namespace std;
22 typedef long long LL;
23 typedef int II;
24 II V,n,d[N];
25 II dp[N];
26 II ans[N],ct;
27 II path[100][N];
28 void DP(){
29     mem(dp,0);
30     mem(path,0);
31     for(II i=1;i<=n;i++) 
32         for(II j=V;j>=d[i];j--){
33             if(dp[j]<=(dp[j-d[i]]+d[i])){
34                 dp[j]=dp[j-d[i]]+d[i];
35                 path[i][j]=1;
36             }
37         }
38 }
39 void printpath(II x,II m){
40     if(x==0) return;
41     if(path[x][m]==0) printpath(x-1,m);
42     else{
43         printpath(x-1,m-d[x]);
44         ans[ct++]=d[x];
45     } 
46 }
47 int main() {
48     ios::sync_with_stdio(false);cin.tie(0);
49     while(cin>>V){
50         cin>>n;
51         for(II i=1;i<=n;i++) cin>>d[i];
52         DP();
53         ct=0;
54         printpath(n,V); 
55         for(II i=0;i<ct;i++){
56             cout<<ans[i]<<sp;
57         }
58         cout<<"sum:"<<dp[V]<<endl; 
59     } 
60     return 0;
61 }

View Code

第三题：

UVA562 Dividing coins

题目链接：https://vjudge.net/problem/UVA-562

题目意思：0-1背包的问题的一个变形，平衡问题，将n个硬币的总价值累加得到sum，再用sum/2作为背包容量对n个硬币做01背包处理，看能组成的最大容量是多少，使得分开的两堆硬币，价值的差最接近。

代码：

 1 //Author: xiaowuga
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <set>
 5 #include <vector>
 6 #include <queue>
 7 #include <cmath>
 8 #include <cstring>
 9 #include <cstdio>
10 #include <ctime>
11 #include <map>
12 #include <bitset>
13 #include <cctype>
14 #define maxx INT_MAX
15 #define minn INT_MIN
16 #define inf 0x3f3f3f3f
17 #define mem(s,ch) memset(s,ch,sizeof(s))
18 #define nc cout<<"nc"<<endl
19 #define sp " "
20 const long long N=100000; 
21 using namespace std;
22 typedef long long LL;
23 typedef int II;
24 II n,d[N],dp[N];
25 II sum=0;
26 void DP(){
27     mem(dp,0);
28     II V=sum/2;
29     for(II i=1;i<=n;i++)
30         for(II j=V;j>=d[i];j--){
31             dp[j]=max(dp[j],dp[j-d[i]]+d[i]);
32         }
33     cout<<sum-2*dp[V]<<endl;
34 } 
35 int main() {
36     ios::sync_with_stdio(false);cin.tie(0);
37     II T;
38     cin>>T;
39     while(T--){
40        cin>>n; 
41        sum=0;
42        for(II i=1;i<=n;i++){
43            cin>>d[i];
44            sum+=d[i];
45        } 
46        DP();
47     }
48     return 0;
49 }

View Code

第四题：

HDU2955 Robberies

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2955

题目意思：有一个强盗要去几个银行偷盗，他既想多投点钱，又想尽量不被抓到。已知各个银行的金钱数和被抓的概率，以及强盗能容忍的最大被抓概率。求他最多能偷到多少钱？

题目思路：原先想的是把概率当做背包，在这个范围内最多能抢多少钱，但是wa了，问题在于最大不被抓概率不是简单的累加。而是p = (1-p1)(1-p2)(1-p3) 其中p为最大不被抓概率，p1，p2，p3为各个银行被抓概率。现在是以抢到的钱为背包，求最大的被抓概率。从大到小枚举背包，第一个被抓概率小于可容忍程度的的背包容量就是答案，个人感觉非常好的一道题。

代码：

 1 //Author: xiaowuga
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <set>
 5 #include <vector>
 6 #include <queue>
 7 #include <cmath>
 8 #include <cstring>
 9 #include <cstdio>
10 #include <ctime>
11 #include <map>
12 #include <bitset>
13 #include <cctype>
14 #define maxx INT_MAX
15 #define minn INT_MIN
16 #define inf 0x3f3f3f3f
17 #define mem(s,ch) memset(s,ch,sizeof(s))
18 #define nc cout<<"nc"<<endl
19 #define sp " "
20 const long long N=10000+10; 
21 using namespace std;
22 typedef long long LL;
23 typedef int II;
24 II w[N];
25 double g[N],P,dp[N];
26 II n;
27 II sum=0;
28 void DP(){
29     memset(dp,0,(sum+1)*sizeof(dp[0]));
30     dp[0]=1;
31     for(II i=1;i<=n;i++)
32         for(II j=sum;j>=w[i];j--){
33             double t=(1.0-g[i])*dp[j-w[i]];
34             dp[j]=max(dp[j],t);
35         }
36     II x;
37     for(x=sum;1-dp[x]>=P;x--);
38    cout<<x<<endl; 
39    return ;
40 }
41 int main() {
42     ios::sync_with_stdio(false);cin.tie(0);
43     II T;
44     cin>>T;
45     while(T--){
46         cin>>P>>n;
47         sum=0;
48         for(II i=1;i<=n;i++){
49             cin>>w[i]>>g[i];
50             sum+=w[i];
51         }
52         if(P<=1-1e-8){
53             DP();
54         }
55         else{
56             cout<<sum<<endl;
57         }
58     }
59     return 0;
60 }

View Code

第五题：

POJ2184 Cow Exhibition

题目链接：http://poj.org/problem?id=2184

题目意思：这是又是一道01背包的变体，题目要求选出一些牛，使smartness和funness值的和最大，而这些牛有些smartness或funness的值是负的，还要求最终的smartness之和以及funness之和不能为负。

题目思路：一是将smartness看作花费、将funness看作价值，从而转化为01背包；二是对负值的处理，引入一个shift来表示“0”，这里的shift一定要大于每一个smartness的绝对值。

一遇到负值我们就懵逼了，实际上负值也可以加入背包，整个背包的容量为N，0为左端点，N为右端点，shift为中点（实际意义上的零点）。

当花费为正的时候，假设花费为x，那么区间【x，N】内的任意状态i都有可能并可以从i-x转移而来，而区间【0，x）则不可能，因为向他们转移的状态超出边界了，大状态从小状态转移而来，所以我们先更新大状态再更新小状态。所以反向枚举。

当花费为负的时候，假设花费为x（x为负数），那么区间【0，N+x】内任意状态i都可以并可能从i-x转移而来，而区间（N-x，N】则不行，因为向他们转移的状态都超出边界了。由于小状态是由大状态转移而来，先更新小状态在更新大状态，所以正向枚举。

最后由于题目要求花费得是正数，价值也要是正数，所以遍历区间【shift,N】（shift是实际意义上的零点），去寻找下标(真实下标为i-shift)+dp[i]的最大值，就是符合题目意思的答案。

总结：个人认为是一道好题，把各种限制转化为背包的问题，通过背包的性质将其一一解决，说明对于和最大问题背包也是一个可以思考的方向。

代码：

 1 //Author: xiaowuga
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <set>
 5 #include <vector>
 6 #include <queue>
 7 #include <cmath>
 8 #include <cstring>
 9 #include <cstdio>
10 #include <ctime>
11 #include <map>
12 #include <bitset>
13 #include <cctype>
14 #define maxx INT_MAX
15 #define minn INT_MIN
16 #define inf 0x3f3f3f3f
17 #define mem(s,ch) memset(s,ch,sizeof(s))
18 #define nc cout<<"nc"<<endl
19 #define sp " "
20 const long long N=200000+100; 
21 using namespace std;
22 typedef long long LL;
23 typedef int II;
24 II dp[N];
25 II w[N],v[N];
26 II n;
27 II shift;
28 void DP(){
29     for(II i=1;i<=n;i++){
30         if(w[i]>=0){
31             for(II j=N-1;j>=w[i];--j){
32                 dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
33             }
34         }
35         else{
36             for(II j=0;j<N+w[i];j++){
37                 dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
38             }
39         }
40     }
41     LL ans=0; 
42     for(II i=shift;i<N;i++){
43         if(dp[i]>=0&&i-shift+dp[i]>ans){
44             ans=i-shift+dp[i];
45         }    
46     }
47     cout<<ans<<endl;
48 }
49 int main() {
50     ios::sync_with_stdio(false);cin.tie(0);
51     while(cin>>n){
52         for(II i=1;i<=n;i++) cin>>w[i]>>v[i];
53         mem(dp,-inf);  
54         shift=100000;
55         dp[shift]=0;
56         DP(); 
57     } 
58     return 0;
59 }

View Code

第六题：

HDU2639 Bone Collector II

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2639

题目意思：求K大背包，某个状态的下第k大价值

思路：多开一维空间来记录k个状态，即每个状态有k个值。每次转移的时候实际上转移态的k个状态想被转移态的k个状态发生转移，去前k个不同的值，思路很简单，感觉代码很有意思。

代码：

 1 //Author: xiaowuga
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <set>
 5 #include <vector>
 6 #include <queue>
 7 #include <cmath>
 8 #include <cstring>
 9 #include <cstdio>
10 #include <ctime>
11 #include <map>
12 #include <bitset>
13 #include <cctype>
14 #define maxx INT_MAX
15 #define minn INT_MIN
16 #define inf 0x3f3f3f3f
17 #define mem(s,ch) memset(s,ch,sizeof(s))
18 #define nc cout<<"nc"<<endl
19 #define sp " "
20 const long long N=1000*2; 
21 using namespace std;
22 typedef long long LL;
23 typedef int II;
24 II dp[N][33],val[N],vol[N],A[33],B[33];
25 II n,v,k;
26 void DP(){
27     II a,b,c;
28     for(II i=1;i<=n;i++)
29         for(II j=v;j>=vol[i];j--){
30             for(II kk=1;kk<=k;kk++){
31                 A[kk]=dp[j-vol[i]][kk]+val[i];
32                 B[kk]=dp[j][kk];
33             }
34             A[k+1]=-1;B[k+1]=-1;
35             a=b=c=1;
36             while(c<=k&&(A[a]!=-1||B[b]!=-1))(
37                 if(A[a]>B[b]) dp[j][c]=A[a++];
38                 else dp[j][c]=B[b++];
39                 
40                 if(dp[j][c]!=dp[j][c-1]) c++;
41             } 
42         }
43         cout<<dp[v][k]<<endl;
44 }
45 
46 int main() {
47     ios::sync_with_stdio(false);cin.tie(0);
48     II T;
49     cin>>T;
50     while(T--){
51         cin>>n>>v>>k;
52         for(II i=1;i<=n;i++) cin>>val[i];
53         for(II i=1;i<=n;i++) cin>>vol[i];
54         mem(dp,0);
55         DP(); 
56     } 
57     return 0;
58 }

View Code

第七题：

POJ2923 Relocation

题目链接：http://poj.org/problem?id=2923

题目意思：有 n 个货物，并且知道了每个货物的重量，有两辆车，载重量分别为c1,c2，两辆车必须同时出发，同时回来，不能说哪辆车单独出发，问最少需要运送多少次可以将货物运完。

分析: 找出所有状态（1.....(1<<n)-1）中选出可以用两辆车一次运完的状态，然后我们通过没有交集状态之间的0-1背包找出，全部都运走的状态下。最少需要多少次。

其中判断两个货物是否可以一起被运走的方法也十分有意思。不好说清楚看代码应该很容易理解。就是从差不多通过组合C1可以满足容量，且剩余重量小于C2的载重量，然后把所有满足的枚举作为物品。

然后以状态为背包，判断在满足某个状态下最少的步数。其中有交集的状态不能转移。位运算或代表状态相加，还有j先j&a[i]发生转移的时候，需要注意j是否已经可以从j从0转移过来。（也就是dp[j]!=inf,所以这道题一开始需要把数组全部初始化为inf，把dp[0]初始化为0）。

代码：

 1 //Author: xiaowuga
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <set>
 5 #include <vector>
 6 #include <queue>
 7 #include <cmath>
 8 #include <cstring>
 9 #include <cstdio>
10 #include <ctime>
11 #include <map>
12 #include <bitset>
13 #include <cctype>
14 #define maxx INT_MAX
15 #define minn INT_MIN
16 #define inf 0x1f1f1f1f
17 #define mem(s,ch) memset(s,ch,sizeof(s))
18 #define nc cout<<"nc"<<endl
19 #define sp " "
20 const long long N=150;
21 using namespace std;
22 typedef long long LL;
23 typedef int II;
24 II dp[1<<11];
25 II a[1<<11];
26 II v[1<<11];
27 II c1,c2,n;
28 II w[N];
29 II st,top;
30 bool OK(II x){
31     II s=0;
32     memset(v,0,sizeof(v));
33     v[0]=1;
34     for(II i=0;i<n;i++){
35         if((1<<i)&x){
36             s+=w[i];
37             if(s>c1+c2) return false;
38             for(II j=c1;j>=w[i];j--){
39                 if(v[j-w[i]]) v[j]=1;
40             }
41         }
42     }
43     for(II i=0;i<=c1;i++)
44         if(s-i<=c2&&v[i]) return true;;
45     return false;
46 }
47 int main() {
48     ios::sync_with_stdio(false);cin.tie(0);
49     II ca=1;
50     II T;
51     cin>>T;
52     while(T--){
53         cin>>n>>c1>>c2;
54         for(II i=0;i<n;i++) cin>>w[i];//读入
55         memset(dp,inf,sizeof(dp));
56         dp[0]=0;top=0;
57         st=(1<<n)-1;
58         top=0;
59         for(II i=1;i<=st;i++) if(OK(i)) a[top++]=i;
60         for(II i=0;i<top;i++)
61             for(II j=st;j>=0;j--){
62                 if(dp[j]!=inf){//首先j状态要存在才能向别人转移
63                     if(j&a[i]) continue;//有冲突
64                     dp[a[i]|j]=min(dp[a[i]|j],dp[j]+1);
65                 } 
66             }
67         cout<<"Scenario #"<<ca++<<":"<<endl;
68         cout<<dp[st]<<endl<<endl;
69     }
70     return 0;
71 }

View Code