题解 | #称砝码#

import java.util.HashSet;
import java.util.Scanner;

public class Main {
    private static HashSet<Integer> set = new HashSet<Integer>();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int[] ms = new int[n]; // 重量
            int[] xs = new int[n]; // 数量
            for(int i = 0;i < n;++i){
                ms[i] = in.nextInt(); // 读取重量
            }
            int count = 0;
            for(int i = 0;i < n;++i){
                xs[i] = in.nextInt(); // 读取数量
                count += xs[i]; // 计算总数量
            }
            int[] arr = new int[count]; // 新的数组，储存每一个重量值，长度为总数量
            int idx = 0;
            for(int i = 0;i < n;++i){
                int x = xs[i];
                while(x-- > 0){
                    arr[idx++] = ms[i]; // 遍历得到新的数组
                }
            }
            set.clear();
            set.add(0); // 先添加一个初始值0
            for(int i = 0;i < count;++i){
                int cur = arr[i]; // 获取当前重量
                HashSet<Integer> set_ = new HashSet<Integer>(set); // 用new初始化，防止一直，更新，即先记录好原本的set，不能用set_ = set
                for(Integer j : set_){
                    set.add(cur + j); // 更新
                }
            }
            System.out.println(set.size()); // 输出
        }
    }

}

最开始做的时候，昨天想了一下背包问题，即一个物品放不放入背包，这道题有异曲同工之妙，对于一个当前砝码，可以有两种选择，一是不算这砝码的重量，二是对当前可称的重量加上这一部分，比如，对于3个砝码1，1，2

初始为0，

第一个砝码为1，则set更新为 0+0，0+1，即0，1

第二个砝码亦为1，则set更新为0 + 0，0 + 1, 1 + 0, 1 + 1，即0，1，2

最后一个砝码为2，则set更新为0 + 0，0 + 2, 1 + 0, 1 + 2, 2 + 0, 2 + 2，即0，1，2，3，4

因为初始有0，不用再考虑不算重量（即0 + 0，1 + 0，2 + 0，原本就有了，已保留），遍历set中值，将其与当前砝码重量的和add进去，set自动去重

最开始想到的是递归，后来也做出来了，发现其实改成for循环遍历即可，也做出来了，并且刚开始用的是hashmap，看人家发现可以直接用set，傻了，改成set即可