这里是简介

思路

简单分析题目可以看出这是一道多重背包题目，不妨将价值看成重量，于是有我们要凑出的重量为：$w=\frac{\sum_{i=1}^{6}{w[i]*i}}{2}$
但是当前复杂度会超时…所以我们要优化时间复杂度
因为当我们做多重背包时，我们是将它转化成01背包来做的（即选1件-N件）
所以我们可以采用二进制拆分的方式进行优化：

不妨设当前有7件价值为1的物品。
7(10) = 111(2)，将7分成1件，2件和4件
选一件+选两件=选三件，以此类推
于是就从多重背包变成了裸的01背包！

代码

#include <cstdio>
#include <cstring>
typedef long long ll;

const ll N = 6e4 + 10, M = 2e4 + 10;
ll n[7], sum, yq, t, w[M], cnt;
bool dp[N];

int main () {
    while (true) {
        memset (dp, false, sizeof dp);
        cnt = 0, sum = 0, ++t;
        for (register ll i = 1; i <= 6; ++i) {
            scanf ("%lld", n + i);
            sum  += n[i] * i;
        }
        if (!sum) return 0;
        //特判，当和为奇数时，显然不能分 
        if (sum & 1) {
            printf ("Collection #%lld:\n", t); 
            puts("Can't be divided." "\n");
            continue;
        }    
        yq = sum >> 1, dp[0] = true;
        //二进制拆分 
        for (register ll i = 1; i <= 6; ++i) {
            ll k = 1, tot = n[i];
            while (k <= tot) {
                w[++cnt] = k * i;
                tot -= k, k <<= 1;
            }
            if (tot) w[++cnt] = tot * i;
        }
        //01背包 
        for (register ll i = 1; i <= cnt; ++i)
            for (register ll j = yq; j >= w[i]; --j)
                dp[j] |= dp[j - w[i]];
        printf ("Collection #%lld:\n", t); 
        puts (dp[yq] ? "Can be divided.\n" : "Can't be divided.\n");
    }
    return 0;
}