POJ 1742 Coins 【可行性背包】【非原创】

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

题意：给你n种面值的硬币，面值为a1...an，数量分别为c1...cn，求问，在这些硬币的组合下，能够多少种面值，该面值不超过m

思路：设d[i][j]——前i种硬币，凑成总值j时，第i种硬币所剩余的个数。（能否想到这样构造是个难点

　　　默认d[i][j] = -1，代表无法凑成总值j

　　　转移方程为，若d[i-1][j]≥0，代表前i-1种已能够凑成j，那么就不必花费第i种硬币，所以d[i][j] = c[i]

　　　否则就看d[i][j-a[i]]的值，显然如果j < a[i]，那么d[i][j] = -1，否则d[i][j-a[i]] ≤ 0，代表此刻第i种硬币已使用完了，所以自然d[i][j] = -1;

　　　否则，d[i][j] = d[i][j-a[i]]-1;

　　　可以看到d[i][]的值只与d[i-1][]和d[i][]有关，所以我们可以采用一维数组的形式，从而能够节省内存空间。

AC代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 typedef unsigned long long ll;
 6 const int maxn = 1e3 + 10;
 7 const int inf = 0x3f3f3f3f;
 8 const int maxx = 1e5 + 10;
 9 int dp[maxx];
10 int a[maxn];
11 int c[maxn];
12 bool vis[maxx];
13 int main()
14 {
15     int n, m;
16     while(~scanf("%d %d", &n, &m),(n||m))
17     {
18 
19         memset(dp, -1, sizeof(dp));
20         for(int i = 1; i <= n; ++i)
21         {
22             scanf("%d", a+i);
23        //     printf("%d ", a[i]);
24         }
25         for(int i = 1; i <= n; ++i)
26         {
27             scanf("%d", c+i);
28         }
29         dp[0] = 0;
30         for(int i = 1; i <= n; ++i)
31         {
32             for(int j = 0; j <= m; ++j)
33             {
34                 if(dp[j] >= 0)
35                 {
36                     dp[j] = c[i];
37                 }
38 
39                 else if(j - a[i] >= 0 && dp[j - a[i]] > 0)
40                 {
41                     dp[j] = dp[j - a[i]] - 1;
42                 }
43             }
44         }
45         int ans = 0;
46         for(int i = 1; i <= m; ++i)
47         {
48          //   printf("%d ", dp[i]);
49             if(dp[i] >= 0) ++ans;
50         }
51         printf("%d
",ans);
52     }
53     return 0;
54 }

View Code

转载博客：戳这里