D - D 分糖果HDU - 1059(完全背包+二进制优化)

有两个小朋友想要平分一大堆糖果，但他们不知道如何平分需要你的帮助，由于没有spj我们只需回答能否平分即可。

糖果大小有6种分别是1、2、3、4、5、6，每种若干颗，现在需要知道能不能将这些糖果分成等额的两堆。

一颗大小为6的糖果，可以相当于2颗大小为3的糖果，其他同理，即大小满足加法，但是1颗糖果是不能被拆分的。

Input

多组输入，每行输入6个非负整数，分别表示大小为1、2、3、4、5、6的糖果的数量，若输入6个0代表输入结束。

单种糖果的数量不会超过20000。

Output 每组询问先输出一行 "Collection #k:"，k表示第几组询问。

再输出一行表示答案，若能分割，输出 “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.

思路

题意: 给我们6种物品，每种物品有各自的数量，第i种物品的价值、与所占的空间均是i，能否将将这个六种物品的价值均分为两份
分析：1.如果6种物品价值之和sum为奇数，显然不可能均分；否则的有可能均分，那么我们把 \(sum/2\)作为的背包的空间，如果我们在dp之后， \(dp[sum/2] == sum/2\), 说明用 sum/2的空间是可以均分的。
代码1：我是把完全背包转01背包了，这样同种物品就转化为了不同的物品，不过显然由于每种的物品数量太多肯定会T
代码2: 则是把完全背包的每种物品进行 “二进制拆分”这样拆分之后的物品数量就像对于代码1的转化方法大大的减少了

代码一（完全背包转01背包--->T了）

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int Len = 200000;

int ar[7], dp[Len];

int main()

{

    /* freopen("A.txt","r",stdin); */

    int Case = 1;

    while(scanf("%d %d %d %d %d %d", &ar[1], &ar[2], &ar[3], &ar[4], &ar[5], &ar[6]) && ar[1] + ar[2] + ar[3] + ar[4] + ar[5] + ar[6])

    {

        int sum = ar[1]*1 + ar[2]*2 + ar[3]*3 + ar[4]*4 + ar[5]*5 + ar[6]*6;

        if(sum % 2)

        {

            printf("Collection #%d:\nCan't be divided.\n\n", Case ++);

            continue;

        }

        sum /= 2;

        for(int i = 0; i <= sum; i ++)

            dp[i] = 0;

        for(int i = 1; i <= 6; i ++)        //把多重背包拆分成一个一个的01背包

            for(int j = 1; j <= ar[i]; j ++)

                for(int k = sum; k >= ar[i]; k --)

                    dp[k] = max(dp[k], dp[k - i] + i);

        if(dp[sum] == sum)

            printf("Collection #%d:\nCan be divided.\n\n", Case ++);

        else

            printf("Collection #%d:\nCan't be divided.\n\n", Case ++);

    }

    return 0;

}

代码二（完全背包--->二进制优化）

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int Len = 200000;

int ar[7], dp[Len], w[Len];

int main()

{

    /* freopen("A.txt","r",stdin); */

    int Case = 1;

    while(scanf("%d %d %d %d %d %d", &ar[1], &ar[2], &ar[3], &ar[4], &ar[5], &ar[6]) && ar[1] + ar[2] + ar[3] + ar[4] + ar[5] + ar[6])

    {

        int sum = ar[1]*1 + ar[2]*2 + ar[3]*3 + ar[4]*4 + ar[5]*5 + ar[6]*6;

        if(sum % 2)

        {

            printf("Collection #%d:\nCan't be divided.\n\n", Case ++);

            continue;

        }

        //把某个物品有多个的进行二进制拆分

        int cnt = 1;

        for(int i = 1; i <= 6; i ++)

        {

            for(int j = 1; j <= ar[i]; j <<= 1)

                w[cnt ++] = j * i, ar[i] -= j;

            if(ar[i])						//注意：这个地方剩余的数，不要忘了添加上去！

                w[cnt ++] = ar[i] * i;

        }

        sum /= 2;

        for(int i = 0; i <= sum; i ++)

            dp[i] = 0;

        for(int i = 1; i < cnt; i ++)        //把通过二进制优化以后，就变成了一个简单的背包问题了

            for(int k = sum; k >= w[i]; k --)

                dp[k] = max(dp[k], dp[k - w[i]] + w[i]);

        if(dp[sum] == sum)

            printf("Collection #%d:\nCan be divided.\n\n", Case ++);

        else

            printf("Collection #%d:\nCan't be divided.\n\n", Case ++);

    }

    return 0;

}

巴特西

D - D 分糖果HDU - 1059(完全背包+二进制优化)

思路

代码一（完全背包转01背包--->T了）

代码二（完全背包--->二进制优化）

最新文章

热门文章