题目：Coins

链接：http://poj.org/problem?id=1742

题意：给你n 种硬币，每一种的价值Ai ，每一种的数量Ci ，问你用这n 枚硬币可以凑成1-m 中的多少值，输出数量。(n<=100,m<=10万,1<=Ai<=10万,1<=Ci<=1000)

思路：如果用普通的背包算法的话时间复杂度为n*m*Ci，会达到O(100亿)，肯定会超时的，现在我们定义：dp[i][j]：前i 种硬币，组成j ，第i种硬币还剩下多少，如果无法组成j 就设为负数。那么，dp[i][j]=dp[i-1][j]>=0?C[i]:dp[i][j-A[i]]-1。意思就是说：如果前i 种已经能够直接组成j ，那么我第i 种肯定全剩下了，如果不能的话，我就看组成j-A[i] 第i种用了多少，现在多用一个A[i]，所以剩余数量减1 。当然，二维的dp数组可以压缩成一维。

 

1 #include
     
       2 #include
      
        3 int n,m; 4 int a[110]; 5 int c[110]; 6 int dp[100010]; 7 int main() 8 { 9   while(scanf("%d%d",&n,&m)!=EOF)10   {11     if(n==0&&m==0) break;12     for(int i=0;i
       
        =0) dp[j]=c[i];31         else dp[j]=dp[j-a[i]]-1;32       }33     }34     int co=0;35     for(int i=1;i<=m;i++)36       if(dp[i]>=0) co++;37     printf("%d\n",co);38   }39   return 0;40 }