原题链接：https://www.luogu.com.cn/problem/P1537
玛莎和比尔各自有自己的弹珠收藏。他们想重新分配收藏品，使两人能平等拥有弹珠。如果所有的弹珠的价值相同，那么他们就可以平分。但不幸的是，有一些弹珠更大，或者更美丽，所以，玛莎和比尔给每个弹珠一个?1?到?6?的价值。现在他们想平分这些弹珠，使每个人得到的总价值相同。不幸的是，他们发现，他们可能无法以这种方式分弹珠（即使弹珠的总价值为偶数）。例如，如果有一个价值为?1、一个价值为?3?和两个价值为?4?的弹珠，这样他们就不能把弹珠分为价值相等的两部分。因此，他们想要你写一个程序，告诉他们是否能将所有弹珠分成价值相等的两部分。
输入文件有若干行，行中包含六个非负整数 N1?,?,N6?，其中 Ni??是价值为 i?的弹珠的个数。最大弹珠总数将达到 2e4。
输入文件的最后一行是?0 0 0 0 0 0。不要处理这一行。
对于每一组数据，输出?Collection #k:，k为输出的是第几组，接着是?Can be divided.?或?Can't be divided.。
每一组输出后多打一个空行。可以参考样例。
输入 #1
1 0 1 2 0 0 1 0 0 0 1 1 0 0 0 0 0 0
输出 #1
Collection #1: Can't be divided. Collection #2: Can be divided.
解题思路：
首先这里有6种弹珠，每种弹珠的价值为从1到6，每种弹珠有多个，我们需要将这些物品分为俩部分，使得俩部分的价值相同，也就是说现在有俩个人来分这些弹珠，每个人要分得一半价值的弹珠，假设所有弹珠的价值总和为sum，就转换为了要从其中选择若干弹珠，这些弹珠的价值总和为sum/2，看这种选法是否存在。我们可以看到的是有六种弹珠，每种弹珠有多个，从里面选，这不就是经典的多重背包问题吗，多重背包问题的朴素做法时间复杂度为O(n*v*s)，n表示弹珠的种数，v表示弹珠的价值和，s表示每种弹珠的个数，这个题目中,n=6,v=2e4*6,s=2e4，这三个乘起来时间复杂度就达到了1e9,这个时间复杂度是非常高的，肯定过不了，我们考虑一些优化方式，我们考虑多重背包的经典优化二进制优化，可以将时间优化到O(n*v*log(s)),log(s)大概也就是14，所以时间为6*2e4*14,时间大概是1e6，这个时间复杂度是肯定可以过的，多重背包的二进制优化相当于将多重背包问题优化为了01背包问题，然后采用bool类型01背包问题求解即可。
bool类型01背包处理过程
状态定义：
定义f[i][j]表示处理完前i个物品，并且体积刚好为j的选取方案是否存在。
初始化：
f[0][0]=true? 选取完前0个物品的体积只能刚好是0
状态转移：
不选择当前物品
f[i][j]=f[i-1][j]
选择当前物品
f[i][j]=f[i][j] || f[i-1][j-v[i]]
最终答案：
答案就是看f[n][sum/2]这个值为true,还是false,为true表示从前n个物品选取，并且体积刚好为sum/2的选取方案存在，否则说明不存在。
时间复杂度：多重背包二进制优化时间复杂度为O(n*v*log(s)),n=6,v=2e4,log(s)大概是14，所以时间大概为1e6,这个时间是肯定可以过的。
空间复杂度：开了一个bool数组f,空间大概是100*2e4*6/1e6=12M，大概只需要12M，题目给了128M,所以空间是肯定足够的。
cpp代码如下：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e4 + 10;
int s[N];
int v[N];
bool f[100][N * 6]; //bool类型多重背包
int main()
{
int pos = 0;
while (true) //多组测试数据
{
pos++;
bool ok = false;
int sum = 0;
for (int i = 1; i <= 6; i++)
{
scanf("%d", &s[i]);
sum += s[i] * i;
if (s[i] != 0)
ok = true;
}
if (!ok) //当输入的是6个0的时候代表程序处理结束，跳出while循环
break;
if (sum % 2 == 1) //当总和为奇数，那么不管怎么分都不可能将平分为俩份，注意答案输出的个数不要弄错了
{
printf("Collection #%d:\n", pos);
puts("Can't be divided.");
puts("");
continue;
}
int cnt = 0;
for (int i = 1; i <= 6; i++) //多重背包的二进制优化，优化成01背包
{
int x = s[i];
int k = 1;
while (k <= x)
{
cnt++;
v[cnt] = k * i;
x -= k;
k *= 2;
}
if (x)
{
cnt++;
v[cnt] = x * i;
}
}
int n = cnt;
//01背包的处理过程，01背包空间可以优化为一维，我这里写为二维更方便理解，空间要求如果很高的时候我们这里可以将空间压缩为一维
//定义f[i][j]表示处理完前i个物品，并且体积刚好为j的方案是否存在，多组测试数据，二维如下写法可以不清空数组
f[0][0] = true;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= sum / 2; j++)
{
//不选择当前物品
f[i][j] = f[i - 1][j];
//选择当前物品
if (j >= v[i])
f[i][j] = f[i][j] || f[i - 1][j - v[i]];
}
//输出答案
if (f[n][sum / 2])
{
printf("Collection #%d:\n", pos);
puts("Can be divided.");
}
else
{
printf("Collection #%d:\n", pos);
puts("Can't be divided.");
}
puts(""); //每个测试数据中间要有一个空行，每次输出完一个测试数据的答案时，还要记得输出一个空行
}
}