题解 | 称砝码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] sMs = new int[n];
            int[] sXs = new int[n];
            HashSet<Integer> set = new HashSet<>();
            //关键点就是set必须手动添加一个元素，从而进入循环，添加元素。
            set.add(0);
            // 砝码种类
            for (int i = 0; i < n; i++) {
                sMs[i] = sc.nextInt();
            }
            // 砝码个数
            for (int i = 0; i < n; i++) {
                sXs[i] = sc.nextInt();
            }
            for (int i = 0; i < n; i++) {
                ArrayList<Integer> list = new ArrayList<>(set);
                //每个砝码的个数，关键步骤，只要有砝码，至少为1个
                for (int j = 1; j <= sXs[i]; j++) {
                    for (int k = 0; k < list.size(); k++) {
                        set.add(list.get(k) + sMs[i] * j);
                    }
                }
            }
            System.out.println(set.size());
        }
    }
}

能跑过的版本，ArrayList<Integer> list = new ArrayList<>(set);这里每次记忆前文的写法太6了

自己写的dfs超时了

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

while (in.hasNext()) {

int n = in.nextInt();

int[] weights = new int[n];

int[] counts = new int[n];

// 读取每个物品的重量

for (int i = 0; i < n; i++) {

weights[i] = in.nextInt();

}

// 读取每个物品的数量

for (int i = 0; i < n; i++) {

counts[i] = in.nextInt();

}

// 使用 HashSet 记录所有可能的总重量

Set<Integer> possibleWeights = new HashSet<>();

// 从第 0 个物品开始 DFS，初始重量为 0

dfs(weights, counts, 0, 0, possibleWeights);

// 输出不同重量的个数

System.out.println(possibleWeights.size());

}

in.close();

}

/**

* DFS 枚举所有可能的总重量

* @param weights: 物品重量数组

* @param counts: 物品剩余数量数组

* @param index: 当前处理到第几个物品（避免重复组合）

* @param currentWeight: 当前累计重量

* @param set: 记录所有可能的重量

*/

private static void dfs(int[] weights, int[] counts, int index,

int currentWeight, Set<Integer> set) {

// 将当前重量加入集合

set.add(currentWeight);

// 从当前物品开始枚举，避免重复（如 1+2 和 2+1 视为同一种）

for (int i = index; i < weights.length; i++) {

if (counts[i] > 0) {

// 选择一个物品 i

counts[i]--; // 数量减一

dfs(weights, counts, i, currentWeight + weights[i], set); // 可以继续选 i

counts[i]++; // 回溯：数量恢复

}

}

}

}