首页 > 代码库 > 多重背包——平分娃娃

多重背包——平分娃娃

2024-11-02 10:45:39   209人阅读

蒜头君酷爱收集萌萌的娃娃。蒜头君收集了 6 种不同的娃娃，第 i 种娃娃的萌值为 i(1≤i≤6)。现在已知每种娃娃的数量 m?i??，蒜头君想知道，能不能把娃娃分成两组，使得每组的娃娃萌值之和相同。

输入格式

输入一行，输入 6 个整数，代表每种娃娃的数量 m?i??(0≤m?i??≤20,000)。

输出格式

输出一行。如果能把所有娃娃分成萌值之和相同的两组，请输出Can be divided.，否则输出Can‘t be divided.。

样例输入1

2 0 1 1 2 1

样例输出1

Can‘t be divided.

样例输入2

2 2 2 2 2 2

样例输出2，

Can be divided.

分析：要平分成两组，那么总萌值V必为偶数。然后不妨设娃娃的体积等于萌值（背包问题中，只有价值没有体积时，这么干挺好用），于是能平分的话必有dp[V/2]=V/2.
接下来就是求多重背包问题了。

#include <cstdio>
#include <algorithm>
using namespace std;
int m[7];//记录每种娃娃数量
int a[820020];//存储二进制优化后的娃娃萌值
int dp[820020]={0};//存储最大萌值
int V=0;//记录娃娃总萌值
void DP()
{
    int sum=0;
    for(int i=1;i<=6;i++)//二进制表示
    {
        int  j=0;
        while(m[i])
        {
            int t=(1<<j++);
            if(t<m[i])
            {
                m[i]-=t;
                a[++sum]=t;
            }
            else
            {
                a[++sum]=m[i];
                m[i]=0;
            }
        }
    }

    for(int i=1;i<=sum;i++)
        for(int j=V;j>=a[i];j--)
    {
        dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
    }
}
int main()
{
    for(int i=1;i<=6;i++)
    {
        scanf("%d",&m[i]);
        m[i]*=i;
        V+=m[i];
    }
    if(V%2!=0)
    {
        printf("Can‘t be divided.\n");
        return 0;
    }
    DP();
    if(dp[V/2]==V/2)
        printf("Can be divided.\n");
    else
        printf("Can‘t be divided.\n");
    return 0;
}

　　

多重背包——平分娃娃


联系
我们