题目描述：
| 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. 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 Sample Output |
题意：给你 n 种硬币 ，问用这些硬币可以组成多少种小于等于 m 的金额。
给你每种金币的面额， 数量。
思路：多重背包。
代码：
#include <stdio.h>
#include <string.h>#define N 110
#define M 101000// dp[i] 任意块硬币组成金额 i (i<m)
int dp[M], time[M];
// 分别为 第 i 种硬币的面额和数量
int cash[N], num[N];int main() {int n, m, i, j;while(scanf("%d %d", &n, &m), n!=0||m!=0) {memset(dp, 0, sizeof(dp));for(int i=1; i<=n; i++) {scanf("%d", &cash[i]);}for(int i=1; i<=n; i++) {scanf("%d", &num[i]);}dp[0] = 1;int ans = 0;for (int i=1; i<=n; i++) {memset(time, 0, sizeof(time));// time[j] 组成金额 j 需要的 第 i 种硬币的数量// time[j] 肯定是要 小于等于 num[i]for(j=cash[i]; j<=m; j++) {// 金额 j 没组成过 ， j-cash[i] 组成过// 且必须满足 ，组成金额 j， 硬币 i 的数量足够用if(dp[j]==0 && 1==dp[j-cash[i]] && (time[j-cash[i]]+1) <= num[i]) {dp[j] = 1;// 每当组成一个新的符合要求的金额，答案 +1++ ans;time[j] = time[j-cash[i]] + 1;}}}printf("%d\n",ans);}return 0;
}