Coins
Description
People in Silverland use coins.They have coins of value A1,A2,A3…An Silverland dollar.One day Tony opened his money-box and found there were some coins.He decided to buy a very nice watch in a nearby shop. He wanted to pay the exact price(without change) and he known the price would not more than m.But he didn’t know the exact price of the watch.
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
我的代码
这一题和多重背包的区别在于，多重背包要求的是最优解问题，然而这一题可以理解成求能构成的背包的个数。如果按照多重背包的方式处理面值相同的硬币，再回溯，复杂度是nlnc的阶乘，时间会爆炸掉。所以需要考虑dp。
这一题需要这么考虑：在用了前i种货币之后，如果能构成总额j，那么dp[j]赋值为1，在考虑第i+1种货币时，只需要考虑dp[j]=0的总额是否能在使用了这一种货币后被构成。此外还需要一个数组sum来记录构成总额j时已经用了第i+1种货币sum[j]枚，控制sum[j]<=c[i+1]。
其实啊，这里的dp只是一个标志数组，真正用到dp的是sum数组。dp方程是sum[j]=sum[j-w[i]]+1，意思是构成面值j所需要用到的第i种货币的数量为构成面值j-w[i]所用到的货币数量。由于sum只是记录本次货币的使用数量，所以每遍历一种货币时都需要清空。
#include<stdio.h>
#include<string.h>
int w[105],c[105],sum[100005],dp[100005];
int main()
{
int m,n;
while(scanf("%d%d",&n,&m)==2&&n!=0)
{
int ans=0;
for (int i=0;i<n;i++) scanf("%d",&w[i]);
for (int i=0;i<n;i++) scanf("%d",&c[i]);
memset(dp,0,sizeof(dp));
dp[0]=1;
for (int i=0;i<n;i++)
{
memset(sum,0,sizeof(sum));
for (int j=w[i];j<=m;j++)
{
if (dp[j]==0&&dp[j-w[i]]==1&&sum[j-w[i]]<c[i])
{
dp[j]=1;
ans++;
sum[j]=sum[j-w[i]]+1;
}
}
}
printf("%d\n",ans);
}
return 0;
}反思
这一题是对于每一种硬币都分别用了dp，而不是对所有硬币dp，这个是很不好取想到的。