admin 管理员组文章数量: 1086019
dividing(多重背包)
E - Dividing HDU - 1059
有6种宝石,价值分别为1,2,3,4,5,6。
现在有一个长度为6的数组,第i个数字表示价值为i的宝石的数量。
例如:[1,0,1,2,0,0]表示有一个价值为1的宝石,一个价值为3的宝石和两个价值为4的宝石。
请判断能否将所有宝石分为两部分,使得两部分价值相等。
注意:宝石不能分割,比如价值为6的宝石不能分割为两个价值为3的宝石。
Input
每一行输入描述一个要划分的宝石集合。
每个集合有6个非负整数a1, a2,…, a6,其中ai为价值i的宝石数量。
宝石的最大总数将是20000。
输入文件的最后一行为’’ 0 0 0 0 0 "; 不用处理此行。
Output
对于每一行输入,输出Collection #k:, 其中k表示第一个样例(从1开始),然后输出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.
思路:这是一个多重背包模板题目,我们只需要利用二进制优化一下即可,详细细节见代码。
#include<bits/stdc++.h>using namespace std;
const int N = 42 * 1e4 + 100;int dp[N], a[20000];
int n;int main()
{int b[7];int tmp = 0;while(cin >> b[1] >> b[2] >> b[3] >> b[4] >> b[5] >> b[6]){tmp ++;int t = 0;int sum = 0; // 记录最大价值for(int i = 1; i <= 6; i++){sum += b[i] * i;//key point 要用二进制必须找到最大的p 使 1 + 2 + 4 + '''' + 2^p <= b[i]for(int j = 1; j <= b[i]; j *= 2){a[++t] = j * i;b[i] -= j; // 必须要用b[i] -= j;}if(b[i] != 0)a[++t] = b[i] * i; // 判断是否还有剩下的数据//用找到的 1 2 4 ''' 2^p 和减剩下的 b[i] 可以组成 原来 1 ~ p[i] 中的任何一个数}if(sum == 0) break;printf("Collection #%d:\n", tmp);if(sum % 2 == 1){cout << "Can't be divided.\n" << endl;continue;}memset(dp, 0, sizeof dp);dp[0] = 1; // dp[i] 表示是否可以组成 i 如果可以就为1for(int i = 1; i <= t; i++){for(int j = sum; j >= a[i]; j--)dp[j] = max(dp[j], dp[j - a[i]]);}if(dp[sum / 2] == 1) cout << "Can be divided.\n" << endl;else cout << "Can't be divided.\n" << endl;}return 0;
}
本文标签: dividing(多重背包)
版权声明:本文标题:dividing(多重背包) 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.roclinux.cn/b/1686559299a10234.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论