题解 | 称砝码

#牛客创作赏金赛# #刷题我是认真的#

解题思路：

1. 这个题还是很巧妙的
2. 利用Set的不能重复的特性，过滤出来所有的可能性
3. 初始值的Set集合中值仅有有0，然后加上n1个w1砝码的所有可能重量数，得到集合set1,然后合并allSet中；再次遍历allSet,然后依次和n2个w2砝码的所有可能重量数累加，得到集合set2,再合并的allSet中，如此往复，即可得到最后重量数的可能性

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


public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine());
        String[] weighttArr = in.nextLine().split(" ");
        String[] numArr = in.nextLine().split(" ");
        // 用Set存储可能的数量
        Set<Integer> allSet = new HashSet<>();
        // 先将0增加上
        allSet.add(0);
        // 第一层for循环，n表示总共有几种砝码
        for (int i = 0; i < n; i++) {
            Set<Integer> curSet = new HashSet<>();
            // 每次set表示第一种砝码的可能性
            // set中包含0：就可以针对一种砝码自己组成相关的重量可能性
            // 每次用已经存在的set中的值，和新的一种砝码累加，得到新的可能性重量
            for (int s : allSet) {
                // 从1开始，找出砝码i的所有可能性
                for (int j = 1; j <= Integer.parseInt(numArr[i]); j++) {
                    int newWeight = s + j * Integer.parseInt(weighttArr[i]);
                    curSet.add(newWeight);
                }
            }
            // 从1开始，找出砝码i的所有可能性
            allSet.addAll(curSet);
        }
        System.out.println(allSet.size());
    }
}