hdu 1059 (多重背包) Dividing

这里;http://acm.hdu.edu.cn/showproblem.php?pid=1059

题意是有价值分别为1,2,3,4,5,6的商品各若干个,给出每种商品的数量,问是否能够分成价值相等的两份.

联想到多重背包,稍微用二进制优化一下。(最近身体不适,压力山大啊)

 #include<iostream>
#include<cstring>
#include<cstdio>
#define inf 70000
using namespace std;
int dp[inf];
int sum;
void pack(int price)
{
for(int i = sum; i >= price; i--) dp[i] = max(dp[i], dp[i - price] + price);
}
int main()
{
int a[],i,q=,j;
while (~scanf("%d %d %d %d %d %d",&a[],&a[],&a[],&a[],&a[],&a[]))
{
if (a[]==&&a[]==&&a[]==&&a[]==&&a[]==&&a[]==)
break;
memset(dp,-inf,sizeof(dp));
dp[]=;
printf("Collection #%d:\n",q++);
sum=;
for (i=;i<=;i++)
sum+=a[i]*i;
if (sum%!=)
{
printf("Can't be divided.\n\n");
continue;
}
sum/=;
for (i=;i<=;i++)
{
if (i*a[i]>=sum)
{
for (j=i;j<=sum;j++)
dp[j]=max(dp[j],dp[j-i]+i);
}
else
{
int k = ;
while(k < a[i])
{
pack(k * i);
a[i] -= k;
k += k;
}
pack(a[i] * i);
}
}
if (dp[sum]==sum)
printf("Can be divided.\n\n");
else
printf("Can't be divided.\n\n");
}
return ;
}
上一篇:linux(ubuntu)下安装phantomjs


下一篇:在优化MySQL查询时,高key_len值表示什么?