HDU - 2844 Coins
POJ - 1742 Coins
给定 N 种硬币，其中第 i 种硬币的面值为 Ai，共有 Ci 个。
从中选出若干个硬币，把面值相加，若结果为 S，则称“面值 S 能被拼成”。
求 1?M 之间能被拼成的面值有多少个。
输入格式
输入包含多组测试用例。
每组测试用例第一行包含两个整数 N 和 M。
第二行包含 2N 个整数，分别表示 A1,A2,…,AN 和 C1,C2,…,CN。
当输入用例 N=0，M=0 时，表示输入终止，且该用例无需处理。
输出格式
每组用例输出一个结果，每个结果占一行。
数据范围
1≤N≤100,
1≤M≤10^5,
1≤Ai≤10^5,
1≤Ci≤1000
Sample Input
3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0
Sample Output
8
4
算法(贪心+动态规划)
时间复杂度O(NM)
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 110, M = 100010;
int n,m;
int f[M],g[M];
int v[N],s[N];
int main()
{
while(scanf("%d%d",&n,&m)&&n+m){
for(int i=1;i<=n;i++) scanf("%d",&v[i]);for(int i=1;i<=n;i++) scanf("%d",&s[i]);memset(f,0,sizeof f);f[0]=1;for(int i=1;i<=n;i++){
memset(g,0,sizeof g);for(int j=v[i];j<=m;j++)if(!f[j]&&f[j-v[i]]&&g[j-v[i]]<s[i]){
g[j]=g[j-v[i]]+1;f[j]=1;}}int res=0;for(int i=1;i<=m;i++) res+=f[i];printf("%d\n",res);}return 0;
}