题解 | 称砝码

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int m[] = new int[n];
        int x[] = new int[n];
        for(int i = 0; i < n; i++){
            m[i] = in.nextInt();
        }
        int sum = 0;//最高能达到sum重量
        for(int i = 0; i < n; i++){
            x[i] = in.nextInt();
            sum += x[i] * m[i];
        }
        int b[] = new int[sum + 1]; // 10 * 2000 * 10 = 200 000
        b[0] = 1; //最开始只有 0g
        for(int i = 0; i < n; i++){// 第 x[i]种重量
            for(int j = 0; j < x[i]; j++){ //数量j个
                for(int k = sum; k >= 0; k--){//为什么k从sum开始减少
                    if(b[k] == 1){// 重量k能达到
                        int cur = k + m[i]; //在k基础上加上个m[i]
                        b[cur] = 1;
                    }
                }
            }
        }
        int res = 0;
        for(int i = 0; i <= sum; i++){
            if(b[i] == 1){
                res++;
            }
        }
        System.out.println(res);
    }
}

使用动态规划；遍历每种类型的砝码x[i]；第二层遍历的是添加多少个x[i]类型的砝码；第三层遍历的是在前面能组成的砝码 + 当前砝码数据 = 现在组成的砝码数量。

为什么要从后往前遍历？

内层循环从后往前遍历是为了避免重复计算。如果从前往后遍历，可能会在同一个循环中多次添加同一个砝码，导致结果错误。例如，假设当前砝码是 m[i]，如果从前往后遍历，可能会在同一个数量循环中多次加上 m[i]，而实际上每种砝码的数量是有限的。

从后往前的话，你加过的重量肯定比下一次访问的重量大，就不会造成重复计算。

https://www.nowcoder.com/practice/f9a4c19050fc477e9e27eb75f3bfd49c