同PKU 1014 Dividing的一样，上次做SuQiang博客的那20道题目里剩下此题，因为是多重背包没有去切，今天把遗憾解决。
多重背包看来还是得按照伪代码上的写法，自己的写法还是有点问题。
#include <stdio.h>
#include <string.h>
#define N 60005
#define MAX(a, b) (a > b ? a : b)
int c[N];
void Complete(int cost, int weight, int m)
{
for(int i = cost; i <= m; i++)
c[i] = MAX(c[i], c[i - cost] + weight);
}
void Zero_One(int cost, int weight, int m)
{
for(int i = m; i >= cost; i--)
c[i] = MAX(c[i], c[i - cost] + weight);
}
int main()
{
int cas = 1, sum, a[10];
while(1)
{
sum = 0;
for(int i = 1; i <= 6; i++)
{
scanf("%d", &a[i]);
sum += i * a[i];
}
if(!sum) break;
printf("Collection #%d:\n", cas++);
if(sum & 1)
{
puts("Can't be divided.\n");
continue;
}
memset(c, 0, sizeof(c));
sum >>= 1;
for(int i = 1; i <= 6; i++)
{
int t = i * a[i];
if(t > sum) Complete(i, i, sum);
else
{
int k = 1;
while(k < a[i])
{
Zero_One(k * i, k * i, sum);
a[i] -= k;
k <<= 1;
}
Zero_One(a[i] * i, a[i] * i, sum);
}
}
if(c[sum] == sum) puts("Can be divided.\n");
else puts("Can't be divided.\n");
}
return 0;
}