题解 | 称砝码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] m = new int[n];
        for (int i = 0; i < n; i++) {
            m[i] = scanner.nextInt();
        }
        int[] x = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = scanner.nextInt();
        }

        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += m[i] * x[i];
        }

        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;

        for (int i = 0; i < n; i++) {
            int mi = m[i];
            int xi = x[i];
            List<Integer> di = new ArrayList<>();
            for (int k = 0; k <= xi; k++) {
                di.add(k * mi);
            }

            boolean[] temp = new boolean[sum + 1];
            for (int j = 0; j <= sum; j++) {
                if (dp[j]) {
                    for (int d : di) {
                        if (j + d <= sum) {
                            temp[j + d] = true;
                        }
                    }
                }
            }
            dp = temp;
        }

        int count = 0;
        for (boolean b : dp) {
            if (b) {
                count++;
            }
        }
        System.out.println(count);
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1.输入处理：读取砝码种类数、砝码重量数组和数量数组。

2.总重量计算：计算所有砝码的最大可能总重量。

3.动态规划初始化：初始化dp数组，只有重量0是可能的。

4.处理每个砝码：生成当前砝码的所有可能增量，并使用这些增量更新动态规划数组。

5.结果统计：统计动态规划数组中为true的元素数量。