题解 P1537 【弹珠】

· · 题解

不难看出本题是背包问题，类似经典的拔河问题，但是对于权值不同的弹珠，会有不同的数量，因此衍生出两种不同的算法：

朴素背包算法

第一反应想到可以将权值不同的弹珠，根据数量依次扫一次布尔 dp 数组（背包数组），初始化 v[0] = true，其余值为 false，逆序扫数据，如果存在 v[j - i]（i 为弹珠的价值）为 true，则有 v[j] 为 true 。最后如果 v[s] 为 true 则可以平分（s 为所有弹珠总价值的一半）。这种方法简单，但弊端明显：弹珠数量过大，数据组数较多导致本算法妥妥超时。

优化多重背包算法

上面的算法中，我们将弹珠数量建立为组数，即若干个权值为 1 * i 的弹珠，这样子不同的状态（在单种弹珠权值总和以下的状态）都能被若干个 1 * i 来表示。这是一种对单种弹珠分组。但有没有更优化的分组呢？我们可以看一下这一题：P2320 鬼谷子的钱袋，本题中，将钱分成若干个组，使总钱数以下的值都能被某些组的钱数之和所表示。刚刚好能用在这一题。算法核心代码：

for(int t = x ; t > 0 ; t >>= 1)
      f = (t >> 1) + (t & 1);

以上核心算法代码中，将 x 为单种弹珠数代入，循环内得到的所有 f 都是一种分组。例如，将 11 代入，先得到 6，接着得到 3，最后还能得到两个 1。

可列出：

1 = 1
2 = 1 + 1
3 = 3
4 = 3 + 1
5 = 3 + 1 + 1
……

接下来，我们就可以将每个组都当做一个独立的物品代入背包扫一遍 dp 数据了。复杂度瞬间降到了 log 级别。

另外，由于本题是多组数据，我们可以写一个 Solve 函数，专门解决每一组数据。本算法中，同样是初始化 v[0] = true，其余值为 false，但逆序扫数据，如果存在 v[j - fi]（f 为某组的弹珠数量，i 为弹珠的价值）为 true，则有 v[j] 为 true。

如果讲的还不太清晰，结合下面的代码和注释理解吧：

#include <cstdio>
#include <cstring>

inline int Input(){
    char C = getchar();
    int N = 0;
    while(C < '0' || C > '9')
        C = getchar();
    while(C >='0' && C <='9')
        N = (N << 1) + (N << 3) + (C - 48) , C = getchar();
    return N;
} // 读入优化（直觉告诉我数据量很大QAQ） 

int a[7] , s , k = 0;
bool v[60001];

inline bool ReadData(){
    s = 0; // s 变量用于记录每组数据价值总和 
    for(int i = 1 ; i <= 6 ; i++)
        s += (a[i] = Input()) * i;
    return s; // 如果 s 变量为 0 ，即数据结束，返回 false 
}
bool Solve(){
    memset(v , false , sizeof(v)); v[0] = true; // 清空 dp 数组（背包） 
    // 类似经典的拔河问题，本来应给 s 除以 2 做 dp
    // 这里不给 s 除以二，以免 s 为奇数，因此给权值乘 2 
    for(int i = 1 ; i <= 6 ; i++)
        for(int t = a[i] ; t > 0 ; t >>= 1){ // “鬼谷子的钱袋”中的类似做法
            int f = (t >> 1) + (t & 1); // 变量 f 存储弹珠分组的当前组量
            for(int j = s ; j >= f * i * 2 ; j--)
                if(v[j - f * i * 2])
                    v[j] = true;
                // 接下来就是简单做一次背包了             
        }
    return v[s]; // 返回弹珠是否能按价值平分 
}

int main(){
    while(ReadData()){
        if(k)
            printf("\n");
        printf("Collection #%d:\n" , ++k);
        if(Solve()) // 写一个函数专门来解决每一组数据 
            printf("Can be divided.\n");
        else
            printf("Can't be divided.\n");
    }
    return 0;
}