admin 管理员组

文章数量: 1086455

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， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。