题目链接：hdu1171
思路：将多重背包转为成完全背包和01背包问题，转化为01背包是用二进制思想，即件数amount用分解成若干个件数的集合，这里面数字可以组合成任意小于等于amount的件数
比如：7的二进制 7 = 111 它可以分解成 001 010 100 这三个数可以组合成任意小于等于7 的数，而且每种组合都会得到不同的数； 如果13 = 1101 则分解为 0001 0010 0100 0110 前三个数字可以组合成7以内任意一个数，加上 0110 = 6 可以组合成任意一个大于6 小于13 的数，虽然有重复但总是能把 13 以内所有的数都考虑到了，基于这种 思想去把多件物品转换为，多种一件物品，就可用01 背包求解了。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int V,v[105],num[105],d[100000];
void ZeroOnePack(int c,int v)//01背包
{
for(int j = V ; j >= c ; j --)
d[j] = max(d[j - c] + v,d[j]);
}
void CompletePack(int c,int v)//完全背包
{
for(int j = c ; j <= V ; j ++)
d[j] = max(d[j - c] + v,d[j]);
}
void MultiplePack(int c,int v,int amount)//多重背包
{
if(amount * c >= V)
{
CompletePack(c,v);
return ;
}
for(int k = 1 ; k <= amount ; k *= 2)//二进制优化
{
ZeroOnePack(c*k,v*k);
amount -= k;
}
ZeroOnePack(amount*c,amount*v);
}
int main()
{
int i,n;
while(scanf("%d",&n) && n >= 0)
{
int sum = 0 ;
for(i = 0 ; i < n ; i ++)
{
scanf("%d%d",&v[i],&num[i]);
sum += v[i] * num[i];
}
memset(d,0,sizeof(d));
V = sum/2;
for(i = 0 ; i < n ; i ++)
MultiplePack(v[i],v[i],num[i]);
printf("%d %d\n",sum - d[V],d[V]);
}
return 0;
}