题意：有n种纸币面额(a1,a2,...an),每种面额对应有(c1,c2,...cn)张。问这些钱能拼成1-m中多少种值。

题解：背包dp问题。若ci=1,是01背包，若ci*ai>=m则是完全背包，否则是多重背包。（详见《背包九讲》）

先复习一下三种简单背包形式：

　01背包（F[v] ← max{F[v], F[v −Ci] +Wi} ）：

　

　　

　完全背包（F[i, v] = max(F[i − 1, v], F[i, v −Ci] +Wi)）:

　 

　多重背包（利用二进制思想转化为01背包）：

　　

利用三种背包形式就可以轻松解决此题：

　　

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7  8 int f[100005]; 9 int c[105],a[105];10 int n,m;11 12 void ZeroOnePack(int w,int v)13 {14     for(int j=m;j>=v;j--)15         f[j]=max(f[j],f[j-w]+v);16 }17 18 void CompletePack(int w,int v)19 {20     for(int j=v;j<=m;j++)21         f[j]=max(f[j],f[j-w]+v);22 }23 24 void MultiplePack(int w,int v,int c)25 {26     int k=1;27     while(k
          
           =m)47 CompletePack(a[i],a[i]);48 else49 MultiplePack(a[i],a[i],c[i]);50 }51 int ans=0;52 for(int i=1;i<=m;i++)53 if(f[i]==i) ans++;54 printf("%d\n",ans);55 }56 return 0;57 }