Hdu链接
牛客网链接
@[toc]

题目描述

在这里插入图片描述
输入描述:
在这里插入图片描述
输出描述:
在这里插入图片描述
示例1
输入

1 0 1 2 0 0 
1 0 0 0 1 1 
0 0 0 0 0 0

输出

Collection #1:
Can't be divided.

Collection #2:
Can be divided.

题意：

有价值分别是1~6的6种大理石，每种大理石的数量是ni，问能否将这些大理石分成完全相同的两部分？

题解：

这个题和hdu 2844 Coins做法基本一样，不过本题要稍微转变下思路
我们考虑用背包方法来做，题目给了数量，价值，却没有给总容量和体积。我们结合题意思考一下，要分成价值完全相同的两份，其实就是找到一份大理石，使得这一份的价值是总价值的一半。如果我们这样想，我们就会发现，总容量其实就是大理石总价值的一半，每个大理石的体积就是其价值，我们要做的就是找到“一些商品使得其体积满足总容量一半的情况是否存在”，这不就可以用混合背包来做。
对于数量多的用完全背包，对于数量少的用多重背包

代码：

#include<bits/stdc++.h>
using namespace std;
int a[8];
int sum=0;
int dp[120005];
bool f=0;;
void zerone(int cost,int val)
{
    for(int i=sum;i>=cost;i--)
    {
        dp[i]=max(dp[i],dp[i-cost]+val);
    }

}
void complet(int cost)
{
    for(int i=cost;i<=sum;i++)
    dp[i]=max(dp[i],dp[i-cost]+cost);
}
void mul(int cost,int val,int num)
{
    if(cost*num>=sum)
    {
        complet(cost);
        return ;
    }

    for(int i=1;i<=num;i<<=1)
    {
        zerone(i*cost,i*val);
        num-=i;
    }
    zerone(num*cost,num*val);
}
int main()
{
    int case1=0;
    while(cin>>a[1]>>a[2]>>a[3]>>a[4]>>a[5]>>a[6])
    {
        case1++;

        f=0;
        memset(dp,0,sizeof(dp));
        if(a[1]==0&&a[2]==0&&a[3]==0&&a[4]==0&&a[5]==0&&a[6]==0)break;
        printf("Collection #%d:\n",case1);
        sum=a[1]*1+2*a[2]+3*a[3]+4*a[4]+5*a[5]+6*a[6];
        if(sum%2)
        {
            printf("Can't be divided.\n");
            printf("\n");
            continue;
        }
        sum/=2;
        for(int i=1;i<=6;i++)
        {
            mul(i,i,a[i]);//花费，价值，数量 
        }

        if(dp[sum]==sum)f=1;

        if(f==1)cout<<"Can be divided."<<endl;
        else cout<<"Can't be divided."<<endl;
        cout<<endl;
    }
    return 0;
}