题目大意：给出n种面值的硬币， 和这些硬币每一种的数量， 要求求出能组成的钱数（小于等于m）

Ps：用多重背包的方法做在poj上超时了（hdoj行）， 然后在网上看到一个方法， 用f[j]表示能组成这价值为j的钱和不能（0与1）， 用used[j]表示当前这种面值为j时用了A[i]多少次。
code：
#include
#include
int main()
{
int i = 0, j = 0, n = 0, m = 0, ans = 0, A[102], C[102], f[100002], used[100002];
while(scanf("%d %d",&n, &m) , n+m)
{
memset(f, 0, sizeof(f));
for(i = 0; i scanf("%d",&A[i]);
for(i = 0; i scanf("%d",&C[i]);
f[0] = 1;
for(i = 0; i {
for(j = 0; j<=m; j++)//全部初始化， 表示当前面值为j时用了A[i]0次
used[j] = 0;
for(j = A[i]; j<=m; j++)
{
if(!f[j] && f[j-A[i]] && used[j-A[i]]
{
f[j] = 1;
used[j] = used[j-A[i]]+1;
}
}
}
ans = 0;
for(i = 1; i<=m; i++)
if(f[i])
ans++;
printf("%d\n",ans);
}
return 0;
}

多重背包
code：
#include
#include
int n = 0, m = 0, A[102], C[102], dp[100002];
void zero_one(int weight, int value)
{
int j = 0;
for(j = m; j>=weight; j--)
dp[j] = dp[j]>dp[j-weight]+value dp[j]:dp[j-weight]+value;
}
int main()
{
int i = 0, j = 0, k = 0, sum = 0, ans = 0;
while(scanf("%d %d",&n, &m), n+m)
{
memset(dp, 0, sizeof(dp));
ans = 0;
for(i = 0; i scanf("%d",&A[i]);
for(i = 0; i scanf("%d",&C[i]);
for(i = 0; i {
sum = A[i]*C[i];
if(sum>m)//完全背包
for(j = A[i]; j<=m; j++)
dp[j] = dp[j]>dp[j-A[i]]+A[i] dp[j]:dp[j-A[i]]+A[i];
else
{
k = 1;
while(k {
zero_one(k*A[i], k*A[i]);
C[i] -= k;
k *= 2;
}
zero_one(C[i]*A[i], C[i]*A[i]);
}
}
for(i = 1; i<=m; i++)
if(dp[i] == i)
ans++;
printf("%d\n",ans);
}
return 0; www.2cto.com
}