题目大意是给出一些面值的硬币和数量。问在1-m中能凑出多少种钱。
设 dp[i+1][j] 为前i种凑成j元第i种最多剩下多少。
1. dp[i+1][j] = mi ( dp[i][j]>=0) 前i-1种已经能凑成j了
2.dp[i+1][j] = -1 （ j<a[i] || dp[i+1][j-a[i]] <=0 )
3. dp[i+1][j] = dp[i+1][j-a[i]] -1
题目：
Description
Input
Output
Sample Input
3 10 1 2 4 2 1 1 2 5 1 4 2 1 0 0
Sample Output
8 4
代码：
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 6 int n,m; 7 int A[200]; 8 int C[200]; 9 int dp[100000+10]; 10 int main() 11 { 12 while(scanf("%d%d",&n,&m)!=EOF) 13 { 14 if(n==0)break; 15 for(int i=0;i<=m;i++) 16 dp[i] = -1; 17 18 for(int i=0;i<n;i++) 19 { 20 scanf("%d",&A[i]); 21 } 22 for(int i=0;i<n;i++) 23 { 24 scanf("%d",&C[i]); 25 } 26 //dp 27 dp[0]=0; 28 for(int i=0;i<n;i++) 29 { 30 for(int j=0;j<=m;j++) 31 { 32 if( dp[j] >=0) 33 dp[j] = C[i]; 34 else if( j<A[i] || dp[j-A[i]]<=0) 35 dp[j] = -1; 36 else 37 dp[j] = dp[j-A[i]]-1; 38 } 39 } 40 int cnt =0; 41 for(int i=1;i<=m;i++) 42 { 43 if( dp[i]>=0)cnt++; 44 } 45 printf("%d\n",cnt); 46 } 47 return 0; 48 }
原文：http://www.cnblogs.com/doubleshik/p/3537917.html