参考资料：

　　[1]:挑战程序设计竞赛（第二版） P62 多重部分和问题

　　[2]:

题解：

　　具体解析看以上参考资料即可，下面只是谈谈我对这道题的进一步理解。

　　1.dp[ i ][ j ] 定义不同，码出程序的时间复杂度也不同

　　　　①若定义bool dp[ i ][ j ]的含义为 ：前 i 种硬币是否可以凑成 j 元 。

　　　　　为了用前 i 中硬币凑成 j 元，也就需要前 i-1 中硬币凑成 j , j-a_i , j-2×a_i ,...., j-c_i×a_i 中的某一种；

　　　　　由此，可得状态转移方程为dp[ i ][ j ]={ 0≤k≤c_i,k×a_i ≤ j 时，判断是否∃k,使得dp[i-1][j-k×a_i]为真}；

for i : 1 to n    for j : 0 to m        for k : 0 to c[i] && k*a[i] ≤ j            //dp[i][j]为true⇔dp[i-1][j-k*a[i]]有一个为true即可            dp[i][j]=dp[i][j] | dp[i-1][j-k*a[i]];

　　　　　易得此状态转移的时间复杂度为O(n*m*c[i])，而题干 m 的最大取值为 1e5，此方法指定超时。

　　　　②若定义int dp[ i ][ j ]的含义为：用前 i 种硬币凑成 j 元，第 i 种硬币剩余的个数，不能得到的情况下赋值为-1。

　　　　　根据此定义，可得状态转移方程为：

　　　　　

　　　　　分析此状态的时间复杂度为O(n*m) ~ O(m) ( n << m)

　　　　　但，提交会返回MLE................

　　　　　那这只需要优化一下空间就好了，当然选择滚动数组啦。

　　　　   注意：用滚动数组时，第二层循环从0开始；

AC代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 #define memF(a,b,n) for(int i=0;i <= n;a[i++]=b); 6 const int maxn=1e5+50; 7  8 int n,m; 9 int a[maxn];10 int c[maxn];11 int dp[maxn];12 13 int Solve()14 {15     memF(dp,-1,m);16     dp[0]=0;17     for(int i=1;i <= n;++i)18     {19         for(int j=0;j <= m;++j)20             if(dp[j] >= 0)///如果在这之前就可以凑出j元，则不需要使用当前硬币21                 dp[j]=c[i];22             ///如果当前面值a[i]比所要凑的面值j大23             ///或在配更小的数[j-a[i]]时就用光了c[i],则赋值为-124             else if(j < a[i] || dp[j-a[i]] <= 0)25                 dp[j]=-1;///来到此判断语句的隐藏条件为在这之前并没有凑出j元26             else27                 dp[j]=dp[j-a[i]]-1;28     }29     return count_if(dp+1,dp+m+1,bind2nd(greater_equal
         
          (),0));///总额0不算在答案内30 }31 int main()32 {33     while(~scanf("%d%d",&n,&m) && n+m)34     {35         for(int i=1;i <= n;++i)36             scanf("%d",a+i);37         for(int i=1;i <= n;++i)38             scanf("%d",c+i);39         printf("%d\n",Solve());40     }41     return 0;42 }
         
        
       
      

用到了一个骚操作：count_if(dp+1,dp+m+1,bind2nd(greater_equal<int>(),0))；

有空再补这个的具体用法，哈哈哈；

 

此题的另一种做法是二进制思想：

　　将第 i 种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。

　　使这些系数分别为 2⁰,2¹,2²,.....,2^k,c[i]-(2^k+1-1)，这样就将第i种物品分成了O(log₂c[i])种物品

　　且k是满足 2⁰+2¹+2²+.....+2^k ≤ c[i]的最大整数，即 2^k+1-1 ≤ c[i]，k=log₂(C[i]+1) -1。

　　例如，如果c[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。 

　　分成的这几件物品的系数和为c[i]，表明不可能取多于c[i]件的第i种物品。

　　另外这种方法也能保证对于0..c[i]间的每一个整数，均可以用若干个系数的和表示；

　　这个证明可以分0..2^k和2^k+1.... c[i]两段来分别讨论得出。

AC代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 #define mem(a,b) memset(a,b,sizeof(a)) 7 const int maxn=110; 8  9 int n,m;10 int A[maxn],C[maxn];11 bool dp[100000+50];12 13 void Solve()14 {15     mem(dp,false);16     dp[0]=true;17     for(int ki=1;ki <= n;++ki)18     {19         int k=log(C[ki]+1)/log(2)-1;20         for(int x=0;x <= k;++x)//取 2^x 个ki硬币21         {22             int val=(1<
          
           = val;--i)24                 if(dp[i-val] == true)25                     dp[i]=true;26         }27         int val=(C[ki]+1-(1<<(k+1)))*A[ki];//取C[i]+1-2^(k+1)个ki硬币28         for(int i=m;i >= val;--i)29             if(dp[i-val] == true)30                 dp[i]=true;31 32     }33     int res=0;34     for(int i=1;i <= m;++i)35         res += (dp[i] == true ? 1:0);36     printf("%d\n",res);37 }38 int main()39 {40     while(scanf("%d%d",&n,&m),n != 0 || m != 0)41     {42         for(int i=1;i <= 2*n;++i)43             if(i <= n)44                 scanf("%d",A+i);45             else46                 scanf("%d",C+i-n);47         Solve();48     }49 }
          
         
        
       
      

　　注： 上AC了，但在poj上超时了，emmmmmm

　　此算法的时间复杂度为O( m(ΣlogC[i]) );

 

分割线：