題目大意：給出n種面值的硬幣， 和這些硬幣每一種的數量， 要求求出能組成的錢數（小於等於m）
Ps：用多重背包的方法做在poj上超時了（hdoj行）， 然後在網上看到一個方法， 用f[j]表示能組成這價值為j的錢和不能（0與1）， 用used[j]表示當前這種面值為j時用了A[i]多少次。
code：
#include <stdio.h>
#include <string.h>
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<n; i++)
scanf("%d",&A[i]);
for(i = 0; i<n; i++)
scanf("%d",&C[i]);
f[0] = 1;
for(i = 0; i<n; 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]]<C[i])//f[j]為1時used[j]=0
{
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 <stdio.h>
#include <string.h>
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<n; i++)
scanf("%d",&A[i]);
for(i = 0; i<n; i++)
scanf("%d",&C[i]);
for(i = 0; i<n; 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<C[i])//2進制拆分
{
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
}
