You are to write a program which reads n,m,A1,A2,A3...An and C1,C2,C3...Cn corresponding to the number of Tony's coins of value A1,A2,A3...An then calculate how many prices(form 1 to m) Tony can pay use these coins.
Input
The input contains several test cases. The first line of each test case contains two integers n(1<=n<=100),m(m<=100000).The second line contains 2n integers, denoting A1,A2,A3...An,C1,C2,C3...Cn (1<=Ai<=100000,1<=Ci<=1000). The last test case is followed by two zeros.Output
For each test case output the answer on a single line.Sample Input
3 10 1 2 4 2 1 1 2 5 1 4 2 1 0 0
Sample Output
8 4
题意：给你一定种类（n）的不同价值的硬币，每种价值的硬币给定一定的数目。
问你使用这些硬币可以组合出多少种不大于m的价格。 输入包含几个测试用例。
每个测试用例的第一行包含两个整数n（1<=n<=100），m（m<=100000），第二行包含2n个整数，
表示a1，a2，a3…an，c1，c2，c3…cn（1<=ai<=100000，1<=ci<=1000）。
最后一个测试用例后面跟着两个零。
思路：典型的男人八题。具体思路详见代码。
1 #include <cstdio>
2 #include <fstream>
3 #include <algorithm>
4 #include <cmath>
5 #include <deque>
6 #include <vector>
7 #include <queue>
8 #include <string>
9 #include <cstring>
10 #include <map>
11 #include <stack>
12 #include <set>
13 #include <sstream>
14 #include <iostream>
15 #define mod 1000000007
16 #define ll long long
17 using namespace std;
18
19 int n,m;
20 int a[105],b[105];
21 int dp[100005];//
22 int main()
23 {
24 while(scanf("%d %d",&n,&m)&&n!=0)
25 {
26 for(int i=0;i<n;i++)//硬币价值
27 {
28 scanf("%d",&a[i]);
29 }
30 for(int i=0;i<n;i++)//每种硬币的数量
31 {
32 scanf("%d",&b[i]);
33 }
34 memset(dp,-1,sizeof(dp));//dp[i] >= 0 表示价值i可以被凑齐，而 dp[i] = -1 ,表示无法凑齐
35 dp[0]=0;//表示价值为0 的不需要任何银币，所以其值为0
36 for(int i=0;i<n;i++)//n种硬币
37 {
38 for(int j=0;j<=m;j++)//枚举价值，检验是否某一价值可以利用 第 i 个银币转移而来
39 {
40 if(dp[j]>=0)//这意味着这个价值已经被找到，不需要判断是否可以凑齐
41 {
42 dp[j]=b[i];//表示这一状态还剩下可以用于转移的银币数量，不过这是初始设定的，已经凑齐的价值可以通过加上若干个第i中银币找到下一个可以凑齐的价值
43 }
44 //前一个条件表示剩余价值不能再加上一个该种银币以实现状态转移
45 //后一个条件表示用了这个价值的银币用完了，或者用之前的状态凑不齐，没有根基，转移不起
46 //也就是上一个状态不能实现，那么在上一状态的基础上加上银币，不能保证目前状态可以实现。
47 //dp[j]的值表示还可以使用第i中银币数，银币数不足的时候自然不能继续转移下去
48 //对于这种清空，此时 dp[ j- a[i]]的值为0 ，则转移后dp[j]的值变为-1，表示无法凑成
49 else if(j<a[i]||dp[j-a[i]]<=0)
50 {
51 dp[j]=-1;//表示无法实现
52 }
53 //执行到了这一步，满足条件：
54 //1:这一价值还没有被确定可以凑齐，dp[j]在复制之前值为-1
55 //2：用价值为a[i] 的银币，凑成价值为j的状态是存在的，也就是有路可以继续走下的意思
56 //3：此时的j一定可以被凑齐
57 else
58 {
59 dp[j]=dp[j-a[i]]-1;
60 }
61 }
62 }
63 int ans=0;
64 for(int i=1;i<=m;i++)
65 {
66 if(dp[i]>=0)
67 {
68 ans++;
69 }
70 }
71 printf("%d\n",ans);
72 }
73 }