题目描述

给定N种硬币，其中第 i 种硬币的面值为Ai,共有Ci个。

从中选出若干个硬币，把面值相加，若结果为S，则称“面值S能被拼成”。

求1~M之间能被拼成的面值有多少个。
输入格式
输入包含多组测试用例。

每组测试用例第一行包含两个整数N和M。

第二行包含2N个整数，分别表示A1,A2,…,AN和C1,C2,…,CN。

当输入用例N=0，M=0时，表示输入终止，且该用例无需处理。

输出格式
每组用例输出一个结果，每个结果占一行。

数据范围
1≤N≤100,
1≤M≤105,
1≤Ai≤105,
1≤Ci≤1000

样例

输入用例：
3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0
输出用例：
8
4

算法1

多重背包，先转化为01背包，再对1…M-1分别考虑能不能组成，dp[i]表示能否组成i，是则为1，否则为0。
对于dp[i]，显然，如果dp[i - 面值] = 1，则dp[i] = 1。最后用res变量统计dp数组中1的个数即为答案。

java 代码

import java.util.*;

public class Main {
    static class Coin{
        int v;
        int w;

        public Coin(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }
    public static void main(String[] args) {
                Scanner in = new Scanner(System.in);

        while (in.hasNext()) {
            int N = in.nextInt();
            int M = in.nextInt();
            if (N == 0 && M == 0) {
                return;
            }
            int[] A = new int[N];
            int[] C = new int[N];
            List<Coin> coins = new ArrayList<>();

            for (int i = 0; i < N; i++) {
                A[i] = in.nextInt();
            }
            for (int i = 0; i < N; i++) {
                C[i] = in.nextInt();
            }

            for (int i = 0; i < N; i++) {
                for (int j = 1; j <= C[i]; j *= 2) {
                    coins.add(new Coin(j,A[i] * j));
                    C[i] -= j;
                }
                if (C[i] > 0) {
                    coins.add(new Coin(C[i],A[i] * C[i]));
                }
            }

            int res = 0;
            int[] dp = new int[M + 1];
            dp[0] = 1;
            for (Coin coin : coins) {
                for (int i = M; i >= 1; i--) {
                    if (dp[i] == 1) {
                        continue;
                    } else {
                        if (i - coin.w >= 0 && dp[i - coin.w] == 1) {
                            dp[i] = 1;
                        }
                    }
                }
            }

            for (int i = 1; i <= M; i++) {
                if (dp[i] == 1) {
                    res++;
                }
            }

            System.out.println(res);
        }

        in.close();
    }
}