以前只会写多重背包的原版，渣的不行，为了做此题不得不学习了一下，发现其实也不难，只要理解了方法就好多了（PS：其实和倍增挺像的）

8756:砝码称重V2

总时间限制: 1000ms 内存限制: 65536kB

描述

设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=100,000），要求：计算用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况。

输入

一行，包括六个正整数a1,a2,a3,a4,a5,a6，表示1g砝码有a1个，2g砝码有a2个，……，20g砝码有a6个。相邻两个整数之间用单个空格隔开。

输出

以“Total=N”的形式输出，其中N为可以称出的不同重量的个数。

样例输入

1 1 0 0 0 0

样例输出

Total=3

提示

样例给出的砝码可以称出1g，2g，3g三种不同的重量。

多重背包的2^n拆分，就是把一种多份的物体分解成几种价值高的物体来进行01背包就好，举个栗子：

**对于数量为 n 的同种物品 k 价值为 v

可以拆分打包为 1 , 2 , 4 , 8 , 16 …… ,2^x , n的剩余数量

价值为 v , 2*v ……

例如 32 个 价值为 2 的物品可以拆为

1个价值为 1*2 的物品，

1个价值为 2*2 的物品，

1个价值为 4*2 的物品，

1个价值为 8*2 的物品，

1个价值为 16*2 的物品，

1个价值为 31*2 的物品，

用这6个物品可以组合出原先32个物品的所有状态**

下面是代码：

#include
     
      #include
      
       #include
       
        #include
        
          using namespace std;int a[1000100]={
    0};int f[1000100]={
    0};int zz=0;int value[7]={
    0,1,2,3,5,10,20};int fm[7]={
    0};int sum=0;int total=0;const int cf[] = {
    1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072};//以二为底的指数为i的值 void fj(int ki,int valuei)//二进制分解的过程 {    int i=0;    while (cf[i] <= ki)         {            a[++zz]=cf[i]*valuei;//zz是一个指针，指向当前地址             ki-=cf[i];            i++;        }    if (ki > 0)        a[++zz]=ki*valuei;}int main(){    int i,j;    for (i=1;i<=6;i++)        {            scanf("%d",&fm[i]);            sum+=fm[i]*value[i];//最高价值             fj(fm[i],value[i]);        }    f[0]=1;    for (i=1;i<=zz;i++)    for (j=sum; j>=a[i];j--)         f[j]=f[j] || f[j - a[i]];//只是一个普通的01背包     for (i=1;i<=sum;i++)        if (f[i])             total++;    printf("%s%d","Total=",total);  return 0; }
        
       
      
     

“`