题目链接：

解题思路：

　　这题实际上就是能否用所给硬币组合出某个价格，然后统计能组合出的价格的总数，然后每个硬币个数不一，所以很明显是多重背包。

  　 对于多重背包我们用二进制优化，也就是对 num 个 a 物品按二进制进行分组，分出的每一组看做一种物品，那么就转化为01背包了。所以这题也算是标准的模板题了，有个坑注意，题目中的M 可以为负数，小心。

 

代码：

#include 
     
      #define MAXS 100016#define INF 0x3f3f3f3fusing namespace std;/* hdu 2844*/int n,m;//how many prices(form 1 to m) Tony can pay use these coins. //也就是算的是该价格能否被组合出来，统计能组合出来的价格的总数//有个坑点 m 可能为负值int value[102];int num[102];int f[MAXS];// 完全背包void competepack(int w,int v)//物重 价值{  for (int i=w;i<=m;++i)    f[i] = max(f[i],f[i-w]+v);}//01 背包void onezeropack(int w,int v) // 01 背包{   for (int i = m;i>=w;i--)     f[i] = max (f[i],f[i-w]+v);}void init()//这里必须是恰好装满背包才行。所以这样初始化而不是全初始化为0{  f[0] = 0;  for (int i=1;i<=m;++i) f[i] = -INF;}int main (){      while( (2 == scanf ("%d%d",&n,&m) ) && n!= 0 && m!= 0 )   {            init();//初始化        int ans = 0;     //输入价值和个数        for (int i=0;i
      
        0 )        for (int i=0;i
       
        = m) //这是就相当于是个完全背包。超过了总容量，不就相当个数无限嘛        competepack(value[i],value[i]);       else  // 多重背包进行分组转化为01 背包       {          //根据num[i]数目进行分组。          for (int k = 1; k < num[i]; k <<= 1 )          {            onezeropack(value[i]*k,value[i]*k);             num[i] -= k;//分组是按二进制，1,2,4,8...          }          if (num[i]) //如果最后分组还有剩           onezeropack(value[i]*num[i],value[i]*num[i]);//这一步是为了对最后剩下的num处理和当num==1时的处理        }        }      else       {               printf("%d\n", ans);        continue;       }      for(int j = 1 ; j <= m ; ++j)           if (f[j] > 0)//说明该容量的背包能被恰好装满，也就是该价格能由coins组合出来         ans++;      //输出答案       if (ans)      printf("%d\n", ans);   } return 0;}