相同。
思路:多重背包 算出总的val的一半,如果dp[val]==val/2 那就能dividing
//1844K
0MS
#include <stdio.h>
#include <string.h>
#define Max 430000
const int n = 6;
int dp[Max];
int count[n],val;
int max (int a,int b)
{
> b ? a : b;
}
void MulPack(int cost,int
amount)
{
(cost*amount >= val)
for (i = cost; i <= val; i ++)
dp[i] = max (dp[i],dp[i-cost] + cost);
return ;
1;
< amount)
for (i = val; i >= k*cost; i --)
dp[i] = max (dp[i],dp[i - k*cost] + k*cost);
amount -= k;
k *= 2;
val; i >= amount*cost; i --)
dp[i] = max (dp[i],dp[i - amount*cost] + amount*cost);
}
int main ()
{
= 0;;
(1)
sum = 0,val = 0;
memset (dp,0,sizeof(dp));
for (i = 0; i < 6; i ++)
{
scanf ("%d",&count[i]);
val += count[i]*(i+1);
if (!count[i])
sum ++;
}
if (sum == n)
break;
printf ("Collection #%d:\n",++t);
if (val%2 ==
1)
//值为奇的话,就直接不可能