这题做了将近一个月，断断续续的看背包问题，今天总于一口气把背包九讲中的前三讲看完了。
这个一个很典型的多重背包问题：第i件物品有n[i]种，所占的容量权值分别是c[i],w[i]。求最大容量为V时所得到的最大权值。按照背包九讲的讲解，可以利用二进制思想，把n[i]个物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,...,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。（1.....n[i]中的任意一个数都能由若干个系数相加得到，保证了[1, n[i]]区间上任意一个数都是可达的）
为什么这样正确呢？
证明：
（1） 数列1,2,4,…,2^(k-1),n-2^k+1中所有元素的和为n，所以若干元素的和的范围为：[1, n]；
（2）如果正整数t<= 2^k – 1,则t一定能用1,2,4,…,2^(k-1)中某几个数的和表示，这个很容易证明：我们把t的二进制表示写出来，很明显，t可以表示成 n=a0*2^0+a1*2^1+…+ak*2^（k-1），其中ak=0或者1，表示t的第ak位二进制数为0或者1.
（3）如果t>=2^k,设s=n-2^k+1，则t-s<=2^k-1，因而t-s可以表示成1,2,4,…,2^(k-1)中某几个数的和的形式，进而t可以表示成1,2,4,…,2^(k-1)，s中某几个数的和（加数中一定含有s）的形式。
（证毕！）
转成01背包问题之后，将总的marbles的一半看成V，二进制压缩后的序列W[i]即作为c[i],又作为w[i]。状态转移方程为：
for i: 1 .. n
for j: sum/2 .. w[i]
dp[j] = max(dp[j], dp[j-w[i]] + w[i]);
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 120007;
int num[6];
int w[N], dp[N];
int main()
{
//freopen("data.in", "r", stdin);
int cas = 0, i, j;
while(scanf("%d%d%d%d%d%d", &num[0], &num[1], &num[2], &num[3], &num[4], &num[5]) != EOF)
{
if(!num[0] && !num[1] && !num[2] && !num[3] && !num[4] && !num[5])
break;
memset(w, 0, sizeof(w));
memset(dp, 0, sizeof(dp));
int sum = 0;
for(i = 0; i < 6; i++)
sum += (i+1)*num[i];
printf("Collection #%d:\n", ++cas);
if(sum&1)
{
printf("Can't be divided.\n\n");
continue;
}
int k = 0; sum >>= 1;
for(i = 0; i < 6; i++) //利用二进制思想压缩成0-1背包问题
{
if(!num[i]) continue;
int t = 1;
while(t < num[i])
{
w[k++] = t*(i+1);
num[i] -= t;
t <<= 1;
}
w[k++] = num[i]*(i+1);
}
for(i = 0; i < k; i++)
for(j = sum; j >= w[i]; j--)
dp[j] = max(dp[j], dp[j-w[i]] + w[i]); //0-1背包
if(dp[sum] == sum) //总数的1/2可达。
printf("Can be divided.\n\n");
else
printf("Can't be divided.\n\n");
}
return 0;
}