今天终于整理完了堆积了好几天的多重背包了，一开始研究多重背包的时候开着解题思路很简单就是01背包稍微变化一下就行，但是我做了半天却是TimeLimited，查过之后才知道为了缩减时间开销需要二进制拆分，也没来得及弄，今天终于整理完了
多重背包就是变形的01背包，多重背包转换成 01 背包问题就是多了个初始化，只是把一样的物品拆分一下就好了，关键是一个叫二进制拆分的算法，感觉这个算法很好，在以后的时候能够用的着，所以有必要好好说说理解一下
把它的件数C 用分解成若干个件数的集合，这里面数字可以组合成任意小于等于C 的件数，而且不会重复，之所以叫二进制分解，是因为这样分解可以用数字的二进制形式来解释比如：
7的二进制 7 = 111 它可以分解成 001 010 100 这三个数可以组合成任意小于等于7 的数，而且每种组合都会得到不同的数
15 = 1111 可分解成 0001 0010 0100 1000 四个数字如果13 = 1101 则分解为 0001 0010 0100 0110 前三个数字可以组合成7以内任意一个数，加上 0110 = 6 可以组合成任意一个大于6 小于13的数，虽然有重复但总是能把 13 以内所有的数都考虑到了，基于这种思想去把多件物品转换为，多种一件物品，就可用01 背包求解了。
一开始的没有用二进制拆分的算法，超时~~~
#include <iostream>
using namespace std;
int main ()
{
int a[6],count=1;
int vol[20010],f[20010*6];
while ( scanf("%d %d %d %d %d %d",&a[0],&a[1],&a[2],&a[3],&a[4],&a[5]))
{
if( a[0]==0 && a[1]==0 && a[2]==0 && a[3]==0 && a[4]==0 && a[5]==0 )
break;
int sum = a[0]+a[1]+a[2]+a[3]+a[4]+a[5];
if((a[0]+a[1]*2+a[2]*3+a[3]*4+a[4]*5+a[5]*6)%2)//如果总数为奇数，就直接判断
{
printf("Collection #%d:
Can't be divided.
",count++);
continue;
}
int divideAllValue = (a[0]+a[1]*2+a[2]*3+a[3]*4+a[4]*5+a[5]*6)/2;
int w=0;
int i,j;
for( i=0; i<=5 ;i++)
for( j=1 ; j<=a[i] ; j++)//把这a[i]件物品全部放进数组中
vol[w++] = i+1 ;
memset(f,0,sizeof(f));
for(i = 0 ; i < sum ; i++) //遍历i件物品
{
for(j = divideAllValue ; j >= vol[i] ; j--)
{
int tem = f[ j-vol[i] ] + vol[i];
if( f[j] < tem )
f[j] = tem;
}
}
if(f[divideAllValue]==divideAllValue)
printf("Collection #%d:
Can be divided.
",count++);
else
printf("Collection #%d:
Can't be divided.
",count++);
}
return 0;
}
含二进制拆分的经典算法：
#include <iostream>
#include <fstream>
using namespace std;
int a[6],allcase=1;
int vol[20010],f[20010*6];
int count;
void divide(){
for(int i=0;i<6;i++)
{
for (int k=1; k<=a[i]; k<<=1) { //<<右移 相当于乘二
vol[count++] = k*(i+1);
a[i] =a[i] - k;
}
if (a[i] > 0)
vol[count++] = a[i] * (i+1);
}
}
/*
for( i=0; i<=5 ;i++)
for( j=1 ; j<=a[i] ; j++)//把这a[i]件物品全部放进数组中
vol[w++] = i+1 ;
*/
int main ()
{
while (scanf("%d %d %d %d %d %d",&a[0],&a[1],&a[2],&a[3],&a[4],&a[5]))
{
count = 0;
if( a[0]==0 && a[1]==0 && a[2]==0 && a[3]==0 && a[4]==0 && a[5]==0 )
break;
int sum = a[0]+a[1]+a[2]+a[3]+a[4]+a[5];
if( (a[0]+a[1]*2+a[2]*3+a[3]*4+a[4]*5+a[5]*6)%2==1 )//如果总数为奇数，就直接判断
{
printf("Collection #%d:
Can't be divided.
",allcase++);
continue;
}
int divideAllValue = (a[0]+a[1]*2+a[2]*3+a[3]*4+a[4]*5+a[5]*6)/2;
int i,j;
memset(f,0,sizeof(f));
divide();
for(i = 0 ; i < count ; i++) //遍历i件物品
{
for(j = divideAllValue ; j >= vol[i] ; j--)
{
int tem = f[ j-vol[i] ] + vol[i];
if( f[j] < tem )
f[j] = tem;
}
}
if(f[divideAllValue]==divideAllValue)
printf("Collection #%d:
Can be divided.
",allcase++);
else
printf("Collection #%d:
Can't be divided.
",allcase++);
}
return 0;
}