算法学习之路|平分娃娃

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

输入格式
输入一行，输入 6 个整数，代表每种娃娃的数量 mi​（0≤mi​≤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.

第一种方法：(暴力解决)

行为1~6种，列为萌点的最大值。

dp[sum]即1~6种内，各种组合萌点最接近sum的值。

思路与01背包完全相同，只是最后dp[j]=max(dp[j],dp[j-i],dp[j-2*i].....dp[j-n[i]*i])罢了。

#include<iostream>
#include<algorithm>
using namespace std;
int dp[420001];
int main(){
    int n[7],sum=0;
    for(int i=1;i<=6;++i){
        cin>>n[i];
        sum+=i*n[i];
    }
    if(sum%2!=0)    cout<<"Can't be divided.";
    else
    {
        sum/=2;
        for(int i=1;i<=6;++i){
            for(int j=sum;j>=i;j--){//与01背包思路完全相同
                for(int k=1;k<=n[i];k++)//暴力枚举，其中重复了很多状态。
                    if(j-k*i>=0)    dp[j]=max(dp[j-k*i]+k*i,dp[j]);
            }
        }
        if(dp[sum]==sum)    cout<<"Can be divided.";
        else       cout<<"Can't be divided.";
    }
}

第二种方法：(利用二进制方法优化)

二进制方法将第i种物品分成几个集合：{1，2，4，8，16.....2^k，余数}这些子集加载一起为第i种物品的总数量。

为什么要分子集呢，因为这样可以优化一部分无用的子集，即以上的{3,5,6,7,9,10,11,12,13,14,15}.....

例如：第一种物品n=13，可分为{1,2,4,6}。其中

3=1+2

5=1+4

7=1+2+4

8=2+6

....

13=1+2+4+6

都可以用这些子集表示出来。

这样，在动态规划的过程中，这些3,5,7,8...13都会被这些子集中的状态得到，所以可以省略。

#include<iostream>
#include<algorithm>
using namespace std;
int dp[420001];
int main(){
    int n[7],sum=0;//n[I]第I种的总个数，sum一共的萌点。
    for(int i=1;i<=6;++i){
        cin>>n[i];
        sum+=i*n[i];
    }
    if(sum%2!=0)    cout<<"Can't be divided.";//如果萌点不是偶数，则无法一分为二。
    else
    {
        sum/=2;
        int v[10000];//v[I]表示第I个子集所拥有的萌点。
        int num=0;
        for(int i=1;i<=6;++i){//将1~6种的所有子集和其子集的所有萌点依次存入v[i]
            int tmp=n[i];
            for(int j=1;j<=tmp;j*=2){
                v[++num]=j*i;
                tmp-=j;
            }
            if(tmp>0) v[++num]=tmp*i;//存入余数
        }
        for(int i=1;i<=num;++i){//以子集个数为行
            for(int j=sum;j>=v[i];--j){//以总萌点为列，切记这里从sum开始，为01背包
                dp[j]=max(dp[j-v[i]]+v[i],dp[j]);//及求的是>=sum的最大萌点，转化为01背包问题
            }
        }
        if(dp[sum]==sum)    cout<<"Can be divided.";
        else       cout<<"Can't be divided.";
    }
}