题目传送门：Problem - 1059 (hdu.edu.cn)
问题描述
玛莎和比尔拥有一些弹珠。他们希望在自己之间分配收藏品，以便双方都获得平等的弹珠份额。如果所有弹珠都具有相同的价值，这将很容易，因为这样他们就可以将收藏品分成两半。但不幸的是，有些弹珠比其他弹珠更大或更漂亮。因此，Marsha 和 Bill 首先为每颗弹珠分配一个值，一个介于 1 到 6 之间的自然数。现在他们想把弹珠分开，这样每个弹珠都得到相同的总价值。不幸的是，他们意识到以这种方式划分弹珠可能是不可能的（即使所有弹珠的总价值是偶数）。例如，如果有一个值为 1 的弹珠、一个值为 3 的弹珠和两个值为 4 的弹珠，则不能将它们拆分为相等值的集合。因此，他们要求您编写一个程序来检查弹珠是否存在公平的分区。 输入 输入中的每一行都描述了一个要分割的弹珠集合。这些线由六个非负整数 n1、n2、...、n6 组成，其中 ni 是值为 i 的弹珠数。因此，上面的示例将由输入行“1 0 1 2 0 0”描述。弹珠的最大总数为 20000 个。
输入文件的最后一行将是 ''0 0 0 0 0 0'';不要处理此行。 输出 对于每个 colletcion，输出 ''Collection #k：“''，其中 k 是测试用例的编号，然后是 ''Can be divided.' 或 ''Can't be divided.''。
在每个测试用例后输出一个空行。 样本输入 1 0 1 2 0 0 1 0 0 0 1 1 0 0 0 0 0 0 示例输出 Collection #1: Can't be divided. Collection #2: Can be divided.
题目大意：有6种不同大小的弹珠，价值依次为1-6。现在给你一些这些不同种类的弹珠，让你进行分配，使两个人手上的弹珠价值之和相同，一个弹珠不能划分。
题解思路·：读题发现这是一个多重背包问题，最多20000个弹珠，总价值可能为6*20000，直接三重循环暴力dp肯定会超时，考虑用二进制拆分来写
直接上代码：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 20010;
int n, c; // n原有物品总价值
int v[N], m[N];
int new_n; // 二进制拆分后的新物品总数量
int new_v[N]; // 拆分后新物品的价值
int dp[N];
int main()
{
int t = 0;
while (cin >> m[1] >> m[2] >> m[3] >> m[4] >> m[5] >> m[6])
{
memset(dp, 0, sizeof dp);
t++;
n = 0, new_n = 0;
for (int i = 1; i <= 6; i++)
{
n += m[i] * i;
v[i] = i;
}
if (n == 0)
break;
if (n & 1) // 如果总价值为奇数，必定不可平分
{
printf("Collection #%d:\nCan't be divided.\n", t);
cout << endl;
continue;
}
n /= 2;
c = n;
for (int i = 1; i <= 6; ++i)
{
for (int j = 1; j <= m[i]; j <<= 1) // 二进制枚举：1，2，4，...
{
m[i] -= j; // 减去已拆分的
new_v[++new_n] = j * v[i]; // 新物品价值
}
if (m[i]) // 余数
new_v[++new_n] = m[i] * v[i];
}
// 01背包（滚动数组版）
for (int i = 1; i <= new_n; ++i) // 枚举物品
for (int j = c; j >= new_v[i]; --j) // 枚举价值（容量）
dp[j] = max(dp[j], dp[j - new_v[i]] + new_v[i]);
if (dp[c] == n)
printf("Collection #%d:\nCan be divided.\n", t);
else
printf("Collection #%d:\nCan't be divided.\n", t);
cout << endl;
}
return 0;
}收获：
二进制拆分模板：
int new_n = 0;
for (int i = 1; i <= 6; ++i)
{
for (int j = 1; j <= m[i]; j <<= 1)//二进制枚举：1，2，4，...
{
m[i] -= j;//减去已拆分的
new_v[++new_n] = j * v[i];//新物品价值
new_w[new_n] = j * w[i];
}
if (m[i])//余数
{
new_v[++new_n] = m[i] * v[i];
new_w[new_n] = j * w[i];
}
}