Coins（DP）

Coins

Time Limit: 3000MS		Memory Limit: 30000K
Total Submissions: 27686		Accepted: 9368

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

 

      题意：

      给出 N ， M 代表有 N（1 ~ 100） 种钱币，和钱币总和 M （0 ~ 100000）。后给出 N 种钱币的价值 和 对应的数量，现要凑钱币，问能凑出 1 ~ M 中几种钱币，输出这个数。

 

      思路：

      DP。设 dp [ j ] 代表要凑足 i 价值的钱币最多剩下的钱币数。

      1. dp [ j ] = m [ i ] ，当 dp [ j ] >= 0 时；

      2. dp [ j ] = -1，当 j < v [ i ] || dp [ j - v[ i ] ] <= 0 时；

      3. dp [ j ] = dp [ j - v [ i ] ] - 1，其他情况。

      初始化时，dp 都为 -1，标记为都不可到达状态，只有 dp [ 0 ] = 0，代表可以到达。若初始化为 0，则只会一直执行 1 公式，最终所有的钱币都能凑成，明显不对。

      dp 过程中，曾经到凑成过的钱币知道最后循环循环结束都是能到达的，至于不能到达的，中途通过式子 3 可以更新得到。

 

      AC：

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int n, m, ans;
int v[105], num[105];
int dp[100005];

void solve() {
        memset(dp, -1, sizeof(dp));
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
                for (int j = 0; j <= m; ++j) {
                        if (dp[j] >= 0) dp[j] = num[i];
                        else if (j < v[i] || dp[j - v[i]] <= 0) dp[j] = -1;
                        else dp[j] = dp[j - v[i]] - 1;
                }
        }

        for (int i = 1; i <= m; ++i)
                if (dp[i] >= 0) ++ans;
}

int main() {

        while (~scanf("%d%d", &n, &m) && (n + m)) {
                ans = 0;

                for (int i = 1; i <= n; ++i) {
                        scanf("%d", &v[i]);
                }

                for (int i = 1; i <= n; ++i) {
                        scanf("%d", &num[i]);
                }

                solve();

                printf("%d\n", ans);
        }
        return 0;
}