题目描述
输入描述:
输出描述:
示例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;
}
京公网安备 11010502036488号