使用贪心+动态规划思想求解“最小服务器数量”问题（幂次数组子集和最优化）-js教程-PHP中文网

使用贪心+动态规划思想求解“最小服务器数量”问题（幂次数组子集和最优化）

本文详解如何在给定一个由 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 = 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 是给定有限集合，故不能直接套用，但可先检查是否覆盖所需位，再贪心选取。