题解 | #称砝码#

主要思路：

一共有多少个砝码，一个一个和已经有的重量组合累加然后再放到set中。

注意是一共有多少个砝码，不是多少种砝码

输入举例：

2
1 2
2 1

大致流程：

• 起始 set = [0]
• 开始遍历第0个砝码weight[0]，第0个砝码有num[0]个：
• 用一个第0个砝码，加上之前已经有的重量组合weight[0] + set[...]放入set中 ---> set = [0, 1]
• 再用一个第0个砝码，加上之前已经有的重量组合wight[0] + set[...]放入set中 ---> set = [0, 1, 2]
• 开始遍历第1个砝码weight[1]，第1个砝码有num[1]个：
• 用一个第1个砝码，加上之前已经有的重量组合weight[1] + set[...]放入set中 ---> set = [0, 1, 2, 3, 4]

所以set.size() = 5

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) { 
            int n = in.nextInt();
            // 每种砝码的重量
            int[] weight = new int[n];
            // 每种砝码的数量
            int[] num = new int[n];
            for(int i=0; i<n; i++) {
                weight[i] = in.nextInt();
            }
            for(int i=0; i<n; i++) {
                num[i] = in.nextInt();
            }

            // 计算可以称出多少种重量
            HashSet<Integer> set = new HashSet<>();
            set.add(0);
            for(int i=0; i<n; i++) { // 第i个砝码的重量
                for(int j=1; j<=num[i]; j++) { // 第i个玛法的数量
                    List<Integer> list = new ArrayList<>();
                    for (Integer w : set) {
                        list.add(weight[i]  + w);
                    }
                    set.addAll(list);
                }
            }

            System.out.println(set.size());
        }
    }
}