HDU - 1059 背包dp
2024-09-07 02:40:48
题目：
有两个小朋友想要平分一大堆糖果，但他们不知道如何平分需要你的帮助，由于没有spj我们只需回答能否平分即可。
糖果大小有6种分别是1、2、3、4、5、6，每种若干颗，现在需要知道能不能将这些糖果分成等额的两堆。
一颗大小为6的糖果，可以相当于2颗大小为3的糖果，其他同理，即大小满足加法，但是1颗糖果是不能被拆分的。
Input
多组输入，每行输入6个非负整数，分别表示大小为1、2、3、4、5、6的糖果的数量，若输入6个0代表输入结束。
单种糖果的数量不会超过20000。
Output
每组询问先输出一行 "Collection #k:"，k表示第几组询问。
再输出一行表示答案，若能分割，输出 “Can be divided.”，若不能输出 ”Can't be divided.“
每组输出后空一行
Sample Input
1 0 1 2 0 0
1 0 0 0 1 1
0 0 0 0 0 0
Sample Output
Collection #1:
Can't be divided. Collection #2:
Can be divided.
题解：
这道题原本以为是一个思路题，没去想算法，，，其实这道题用多重背包dp套一下模板就可以了
首先求一下所有糖果的总价值sum
如果sum不是一个偶数，那就直接输出（糖果总价值都是奇数，那就肯定不可能平分）
Can't be divided.
每一个糖果有一个价值，这些糖果还有数量，那么就把糖果的价值看成重量，，，对背包总容量sum/2跑一遍多重背包dp
我们只需要最后的结果dp[sum/2]==sum/2那么就输出
Can be divided.
因为我们把糖果的价值看成了容量，那么dp[sum/2]就相当于容量为sum/2的背包能获得的最大价值，如果dp[sum/2]==sum/2,那么也就说明了可以用一些糖果来装满容量为sum/2的背包
dp数组开多大？因为每种糖果最多20000，那么6*20000=120000，我们开1000000肯定够用
代码1（交的G++）：
1 #include<stdio.h>
2 #include<iostream>
3 #include<cstring>
4 using namespace std;
5 int dp[1000000],a[20],sum;
6 void DP(int cost,int num)
7 {
8 int i;
9 if(cost*num>=sum) //完全背包模板
10 {
11 //如果cost*num大于sum的话，那也就相当于完全背包了
12 for(i=cost;i<=sum;i++)
13 dp[i]=max(dp[i],dp[i-cost]+cost);
14 return ;
15 }
16
17 //下面代码是二进制枚举
18 int k=1;
19 while(k<num)
20 {
21 for(i=sum;i>=k*cost;i--)
22 dp[i]=max(dp[i],dp[i-cost*k]+cost*k);
23 num-=k;
24 k*=2;
25 }
26 //如果二进制枚举后还有剩余，那就把剩下的当为一个整体，用01背包模板枚举
27 for(i=sum;i>=num*cost;i--)
28 dp[i]=max(dp[i],dp[i-cost*num]+cost*num);
29 }
30 int main(void)
31 {
32 int pt=1,i,j;
33 while(cin>>a[1]>>a[2]>>a[3]>>a[4]>>a[5]>>a[6])
34 {
35 if(!a[1]&&!a[2]&&!a[3]&&!a[4]&&!a[5]&&!a[6]) break;
36 sum=0;
37 for(i=1;i<=6;i++) sum+=a[i]*i;
38 printf("Collection #%d:\n",pt++);
39 if(sum%2)
40 {
41 printf("Can't be divided.\n\n");
42 continue;
43 }
44 sum/=2;
45 memset(dp,0,sizeof(dp));
46 for(i=1;i<=6;i++) //这个for循环相当于枚举物品
47 DP(i,a[i]);
48 if(dp[sum]==sum) printf("Can be divided.\n\n");
49 else printf("Can't be divided.\n\n");
50 }
51 return 0;
52 }
代码2：
1 #include<stdio.h>
2 #include<iostream>
3 #include<cstring>
4 using namespace std;
5 struct shudui
6 {
7 int c,p;
8 }rice[10];
9 int dp[1000000];
10 int main()
11 {
12 int a,b,c,d,e,cnt=0;
13 rice[1].p=1;
14 rice[2].p=2;
15 rice[3].p=3;
16 rice[4].p=4;
17 rice[5].p=5;
18 rice[6].p=6;
19 while(~scanf("%d%d%d%d%d%d",&rice[1].c,&rice[2].c,&rice[3].c,&rice[4].c,&rice[5].c,&rice[6].c))
20 {
21 int sum=rice[1].c+rice[2].c*2+rice[3].c*3+rice[4].c*4+rice[5].c*5+rice[6].c*6;
22 if(rice[1].c==0 && rice[2].c==0 && rice[3].c==0 && rice[4].c==0 && rice[5].c==0 && rice[6].c==0) return 0;
23 printf("Collection #%d:\n",++cnt);
24
25 if(sum%2) //一定要加这个判断
26 {
27 printf("Can't be divided.\n\n");
28 continue;
29 }
30 sum/=2;
31 memset( dp, 0, sizeof( dp ) );
32 for( int i = 1; i <= 6; i++ ) //枚举物品
33 {
34 int p = 1;
35 while( p < rice[i].c ) //把物品二进制分开
36 {
37 for( int j = sum; j >= rice[i].p * p; j-- )
38 if( dp[j] < dp[j - rice[i].p * p] + rice[i].p * p)
39 dp[j] = dp[j - rice[i].p * p] + rice[i].p * p;
40
41 rice[i].c -= p;
42 p <<= 1; //相当于乘与2
43 }
44 for( int j = sum; j >= rice[i].p * rice[i].c; j-- ) //把二进制枚举后剩下的物品看成一个整体采用01背包
45 if( dp[j] < dp[j - rice[i].p * rice[i].c] + rice[i].p * rice[i].c )
46 dp[j] = dp[j - rice[i].p * rice[i].c] + rice[i].p * rice[i].c;
47 }
48 if(dp[sum]==sum)
49 {
50 printf("Can be divided.\n");
51 }
52 else
53 {
54 printf("Can't be divided.\n");
55 }
56 printf("\n");
57 }
58 return 0;
59 }
最新文章
- C#面向对象设计模式纵横谈——6.Prototype 原型模式(创建型模式)
- EF的性能改善和思考
- WPF DatePicker默认显示当前日期
- SPOJ AMR10I Dividing Stones --DFS
- php Xdebug调试
- mdf与ldf文件如何还原到SQLserver数据库
- ASP.NET MVC5总结（一）@HTML和对应的HTML
- VC提交网页表单（一共八篇）
- Business Analysis and Essential Competencies
- ORACLE 数据库总结
- [TCO 2012 Round 3A Level3] CowsMooing （数论，中国剩余定理，同余方程）
- git使用前配置
- tky项目第①个半月总结
- (8) Xamarin使用Jar檔
- RH033读书笔记(4)-Lab 5 File Permissions
- 团队作业2--需求分析&原型设计
- dtls_srtp学习笔记
- SpringBoot集成RabbitMQ 从零到一,学会MQ异步和解耦--
- tcping 与 telnet命令粗略使用
- Android自定义控件三种方式