本文详解如何在给定一个由 2 的幂组成的服务器容量数组（如 [1, 2, 4, 8, ...]）和目标请求负载 expected_load 的前提下，找出恰好凑出该负载所需的最少服务器数量；若无法精确达成，返回 -1。核心采用记忆化递归（DFS + 剪枝），兼顾正确性与可读性。
本文详解如何在给定一个由 2 的幂组成的服务器容量数组（如 [1, 2, 4, 8, ...]）和目标请求负载 `expected_load` 的前提下，找出**恰好凑出该负载所需的最少服务器数量**；若无法精确达成，返回 -1。核心采用记忆化递归（DFS + 剪枝），兼顾正确性与可读性。
该问题本质是带数量约束的子集和变体（Minimum Subset Sum Count）：数组中每个元素代表一台服务器的处理能力（均为 2 的整数次幂），允许重复使用同一台服务器（注意：题干中 server_array 含重复值如 [1, 1, 2, 4, 8]，表明“同容量服务器可多台部署”），目标是用最少台数组合出精确等于 expected_load 的总处理能力。
⚠️ 关键澄清：
- ❌ 不是「每个索引只能用一次」的 0-1 背包；
- ✅ 是「每台服务器独立可选，相同容量服务器视为不同实体」→ 即 无限背包（Unbounded Knapsack）的数量最小化版本；
- ✅ 但因所有面额为 2 的幂（1, 2, 4, 8, ...），存在贪心直觉——优先用大容量服务器更优。然而，由于数组可能含重复小值（如两个
1）、且要求精确匹配，纯贪心（如从大到小贪心选取）不保最优（例：load=3,arr=[1,1,2]→ 最优为1+2（2台），而非1+1+1（3台）；但若仅按降序遍历未回溯，可能漏解）。因此，稳健解法仍需搜索。
✅ 推荐解法：记忆化深度优先搜索（DFS + Memo）
我们定义递归函数 findMinServers(remaining, idx) 表示：
用
server_array[idx..end]中的服务器，凑出剩余负载remaining所需的最少台数；若不可能，返回-1。
状态转移逻辑：
对当前服务器 arr[idx]，有两种选择：
-
包含它：使用一台
arr[idx]，剩余负载变为remaining - arr[idx]，台数 +1，且仍可继续选用arr[idx]（因允许重复） → 递归调用findMinServers(remaining - arr[idx], idx) -
排除它：跳过
arr[idx]，尝试后续服务器 →findMinServers(remaining, idx + 1)
取二者中可行的最小台数（需妥善处理 -1 边界）。
代码实现（带记忆化优化）
function getMinServers(expected_load, server_array) {
// 优化：按降序排列，有助于剪枝（大数优先，更快触达 base case）
const arr = [...server_array].sort((a, b) => b - a);
const memo = new Map();
function dfs(remaining, idx) {
// Base case: 恰好凑齐
if (remaining === 0) return 0;
// Base case: 负载超支或已无服务器可用
if (remaining < 0 || idx >= arr.length) return -1;
const key = `${remaining},${idx}`;
if (memo.has(key)) return memo.get(key);
// 选择1：使用当前服务器（可重复使用）
const include = dfs(remaining - arr[idx], idx);
// 选择2：跳过当前服务器
const exclude = dfs(remaining, idx + 1);
let result;
if (include === -1 && exclude === -1) {
result = -1;
} else if (include === -1) {
result = exclude;
} else if (exclude === -1) {
result = include + 1; // include 已含台数，+1 表示本次选用
} else {
result = Math.min(include + 1, exclude);
}
memo.set(key, result);
return result;
}
return dfs(expected_load, 0);
}
// 测试用例
console.log(getMinServers(10, [1, 1, 2, 4, 8, 16])); // 输出: 2 （4 + 8 = 12 ❌；2 + 8 = 10 ✅ → 2台）
console.log(getMinServers(3, [1, 1, 2])); // 输出: 2 （1 + 2 = 3）
console.log(getMinServers(7, [2, 4])); // 输出: -1 （无法用 2 和 4 凑出 7）? 为什么不用双层 for 循环暴力？
原始思路中嵌套循环 i, j 仅考虑两台服务器组合，而题目未限定服务器数量上限（例：expected_load=3, arr=[1,1,1] 需 3 台）。穷举所有子集复杂度为 $O(2^n)$，不可行；而记忆化 DFS 将状态空间压缩至 $O(\text{expected_load} \times n)$，在 expected_load 合理范围内高效可靠。
? 进阶优化提示（针对大规模场景）
- 若
expected_load极大（如 $10^9$），需转向数学解法：利用二进制表示特性——任何正整数可唯一表示为若干 2 的幂之和，且最少台数 = 其二进制表示中 1 的个数。但前提是server_array必须包含所有必要位的 2 的幂（如要表示13 = 1101₂，需有1,4,8）。本题中server_array是给定有限集合，故不能直接套用，但可先检查是否覆盖所需位，再贪心选取。
✅ 总结
- 本题是「最小硬币数量」问题的变形，核心在于建模为状态为
(剩余负载, 当前起始索引)的记忆化搜索； - 数组含重复值且允许复用 → 明确指向无限背包的数量最小化；
- 排序 + 记忆化 + 清晰的
-1合并逻辑，是面试中兼顾鲁棒性与可解释性的高分答案； - 下次遇到类似“最小数量凑目标值”，优先思考：能否定义清晰状态？是否存在重叠子问题？能否剪枝？——这比硬写多层循环更体现算法思维。
你离正确答案只差一层记忆化和状态设计；别气馁，这是算法工程师成长路上的经典一课。
