题解 | #称砝码#

import java.util.*;
public class Main {
    /**
       * 现有n种砝码，重量互不相等，分别为 m1,m2,m3…mn ；
       * 每种砝码对应的数量为 x1,x2,x3...xn 。现在要用这些砝码去称物体的重量(放在同一侧)，问能称出多少种不同的重量。
       * 注：
       * 称重重量包括 0
       * 对于每组测试数据：
       * 第一行：n --- 砝码的种数(范围[1,10])
       * 第二行：m1 m2 m3 ... mn --- 每种砝码的重量(范围[1,2000])
       * 第三行：x1 x2 x3 .... xn --- 每种砝码对应的数量(范围[1,10])
       */

    /**
    * 首先根据输入顺序，将砝码用数字序列表示，例如 2个 1g 和 1个 2g，就用 1 1 2 的序列表示
    * 使用 Set 表示加入当前砝码之前能产生的重量种类
    * set 初始化为 {0}；
    * 当第一个 1g 砝码放入时，则 set 中需要插入原先 set 中的所有元素 +1g后的结果，即 {0, 0+1}
    * 当第二个 1g 加入时，则 set 会插入 {0+1, 1+1}，所以 set 最终变为{0, 1, 2}
    * 重复上述步骤加入所有砝码
    * 最后 set 的大小即为能产生的重量种类
    */
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            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();
            }
            for (int i = 0; i < n; i++) {
                xs[i] = in.nextInt();
            }

            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {//所有砝码放到一个list中
                for (int j = 0; j < xs[i]; j++) {
                    list.add(ms[i]);
                }
            }

            Set<Integer> set = new HashSet<>();
            set.add(0);//0算一种重量
            for (Integer i : list) {
                List<Integer> tempList = new ArrayList<>(set.size());
                for (Integer val :
                        set) {//Set表示加入当前砝码之前能产生的重量种类
                    tempList.add(val + i);//新产生的重量种类
                }
                set.addAll(tempList);//去重
            }
            System.out.println(set.size());
        }
    }
}

动态规划和回溯算法 实在看不懂 只有偷偷学一种更好理解的办法