题意：
给你n种面值分别为A1,A2,A3………..An的硬币，每种硬币对应的数量分别是C1,C2,C3………Cn。问：在可以凑出多少种不同的面值，凑出来的面值必须在1~m之间。
解题思路:
乍一看以为是母函数问题，但的确可以使用母函数（在不顾时间的情况下也可以得出正确答案），由于题目所给的数值太大，m <= 100000，而硬币数量Ci <= 1000。这套用母函数简直就被炸飞了。最终还得老老实实用动态规划。
乍二看，这不是多重背包问题吗，直接三个for循环干上去，很悲剧，肯定超时，数据这么大，两个for循环都有可能崩，更别说三个了。
最终还是弱弱的参考了大神们的代码，发现这道题虽然套着多重背包的羊皮，但其实却需用到01背包与完全背包的概念才能在不超时的情况下跑过。
这里安利一个讲述完全背包的博客：http://blog.csdn.net/insistgogo/article/details/11081025
感觉讲的超级棒！！！
真正的解题思路：
首先需要用到的第一个技巧便是多重背包问题的二进制优化，使其转变成01背包问题，减少一重循环（如果不明白二进制优化的可以看看我的背包问题2）
第二个技巧：当Ai * Ci >= m时，就没必要再使用二进制优化了，此时可以直接把这种面值的硬币当成无限多个，直接上完全背包的模板。如果优化成二进制比不优化还慢。
第三个技巧：采用滚动数组，由于n*m的最大值为10000000，此处博主怂，不敢开二维怕崩，所以就采用一维。。。。不知有没有壮士开二维过了。
完全背包的状态转移方程：
d[i] = max(d[i],d[i-an]+an); //an代表硬币面值，i代表凑得总钱数。
注意这里的循环是从，i = an 到 i = sum。（why?见上面链接）
01背包的状态转移方程:
d[i] = max(d[i],d[i-an]+an);
具体代码：
#include <set>
#include <numeric>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cctype>
#include <string>
#include <sstream>
#include <map>
#include <functional>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define REP(idx1,num1) for(int idx1=0;idx1<(num1);idx1++)
#define pb push_back
#define empb emplace_back
#define mp make_pair
#define mem(s) memset(s,0,sizeof(s));
const double EPS = 1e-6;
const int maxn = 100000 + 10;
int n,m;
int a[110],c[110];
int d[maxn];
int sum = 0;
//完全背包
//an对应着硬币面值，cnt对应着此面值的硬币个数
void completebag(int an){
for(int i = an; i <= sum; ++i)
d[i] = max(d[i],d[i-an]+an);
}
//01背包
void zeroonebag(int an){
for(int i = sum; i >= an; --i)
d[i] = max(d[i],d[i-an]+an);
}
//二进制优化
void change(int an,int cnt){
if(an*cnt >= m){
completebag(an);
return;
}
else{
int tmp = 0;
for(int j = 1; ; j *= 2){
if(cnt > j){
tmp = an * j;
cnt -= j;
zeroonebag(tmp);
}
else{
tmp = an * cnt;
zeroonebag(tmp);
break;
}
}
}
}
int main(){
while(scanf("%d%d",&n,&m) && n){
for(int i = 1; i <= n; ++i){
scanf("%d",&a[i]);
}
for(int i = 1; i <= n; ++i){
scanf("%d",&c[i]);
sum += a[i] * c[i];
}
mem(d);
if(sum > m) sum = m;
for(int i = 1; i <= n; ++i){
change(a[i],c[i]);
}
int ans = 0;
int kase[maxn];
//判断出现了多少种面值
mem(kase);
kase[0] = 1;
for(int i = 1; i <= m; ++i){
if(!kase[d[i]]){
ans++;kase[d[i]] = 1;
//cout <<d[i] <<" ";
}
}
//cout << endl;
printf("%d\n",ans);
}
return 0;
}