同PKU 1014 Dividing的一樣，上次做SuQiang博客的那20道題目里剩下此題，因?yàn)槭嵌嘀乇嘲鼪]有去切，今天把遺憾解決。
多重背包看來還是得按照偽代碼上的寫法，自己的寫法還是有點(diǎn)問題。
#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;
}