Node.js如何高效实现数字划分问题？

数字划分问题（Number Partitioning）的目标很明确：给一个整数数组，将其划分为两个不相交子集，使两个子集的元素和尽量接近。它与子集和问题、背包问题关系密切，也是任务调度、负载均衡、数据分片等领域的基础模型。例如有一个任务执行时间列表，要把任务分给两台机器，理想情况就是两边耗时相等。直接枚举所有划分方式是 2 的 n 次方复杂度，当数组长度超过几十就不再可行，因此需要根据数字范围选择动态规划或启发式策略。

一、用动态规划求精确最优差

动态规划的核心是子集和可达性。设数组总和为 S，如果能找到某个子集的和等于 floor(S/2)，那么另一个子集和就是 S - floor(S/2)，两边差值最小。当 S 为偶数且存在这样的子集时，差值就是 0；当 S 为奇数时，理论最小差值至少为 1。即使达不到 floor(S/2)，我们也可以在所有可达子集和中选一个最接近 floor(S/2) 的值，记作 closest，最终差值为 Math.abs(S - 2 * closest)。

实现时用一维布尔数组 dp，dp[j] 表示前 i 个数字能否组成和 j。初始 dp[0] = true，其余为 false。每遍历一个数字 num，需要从 target 向下更新到 num，保证每个数字只使用一次：dp[j] = dp[j] || dp[j - num]。更新完成后再从 target 向下扫描，找到第一个为 true 的下标即可。下面是完整实现。

function partitionDP(nums) {
  if (!Array.isArray(nums) || nums.length === 0) {
    return 0;
  }
  const sum = nums.reduce((a, b) => a + b, 0);
  const target = Math.floor(sum / 2);
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;

  for (const num of nums) {
    if (num <= target) {
      for (let j = target; j >= num; j--) {
        dp[j] = dp[j] || dp[j - num];
      }
    }
  }

  let closest = 0;
  for (let j = target; j >= 0; j--) {
    if (dp[j]) {
      closest = j;
      break;
    }
  }

  return Math.abs(sum - 2 * closest);
}

这段代码返回两个子集和的最小差值。它的时间复杂度是 O(n * target)，其中 target 是总和的一半。空间复杂度是 O(target)。对于总和较小、数字个数适中的情况，这个方案非常稳定，可以保证得到精确最优解。比如任务列表总耗时只有几千毫秒时，target 只有几千，DP 数组完全可承受。但如果某些任务的耗时达到百万级别，target 会变得很大，数组长度和循环次数都会迅速膨胀，这时需要换用启发式方案。

二、Karmarkar-Karp 启发式：大数差分合并

Karmarkar-Karp 算法简称 KK，是一种专门针对数字划分问题的启发式方法。它的思路是不断从当前集合中取出两个最大的数，把它们的差值放回集合。如果两个数相等，它们直接抵消；如果不相等，差值就代表两者分区后形成的净差。重复这个过程，直到集合里只剩一个数或没有数，最终剩下的值就是分区差。这个差值通常比简单贪心更接近最优解，因为它不是一次性地把大数放进某一侧，而是通过差分不断修正两侧的平衡。

这种“最大两个数相减”的操作天然适合使用最大堆来实现。JavaScript 本身没有内置优先队列，但可以自己写一个二叉堆。下面给出一个简洁的最大堆实现，然后基于它完成 KK 算法。需要注意的是，KK 算法只返回最终差值，若要还原具体分区，还需要维护额外的合并树，这里先聚焦差值计算。

class MaxHeap {
  constructor() {
    this.heap = [];
  }

  size() {
    return this.heap.length;
  }

  push(value) {
    this.heap.push(value);
    this._siftUp(this.heap.length - 1);
  }

  pop() {
    if (this.heap.length === 0) {
      return null;
    }
    const top = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this._siftDown(0);
    }
    return top;
  }

  _siftUp(index) {
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2);
      if (this.heap[parent] >= this.heap[index]) {
        break;
      }
      [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]];
      index = parent;
    }
  }

  _siftDown(index) {
    const length = this.heap.length;
    while (index < length) {
      let largest = index;
      const left = index * 2 + 1;
      const right = index * 2 + 2;
      if (left < length && this.heap[left] > this.heap[largest]) {
        largest = left;
      }
      if (right < length && this.heap[right] > this.heap[largest]) {
        largest = right;
      }
      if (largest === index) {
        break;
      }
      [this.heap[largest], this.heap[index]] = [this.heap[index], this.heap[largest]];
      index = largest;
    }
  }
}

function karmarkarKarp(nums) {
  if (!Array.isArray(nums) || nums.length === 0) {
    return 0;
  }
  const heap = new MaxHeap();
  for (const num of nums) {
    heap.push(num);
  }

  while (heap.size() > 1) {
    const first = heap.pop();
    const second = heap.pop();
    const diff = first - second;
    if (diff > 0) {
      heap.push(diff);
    }
  }

  return heap.size() === 0 ? 0 : heap.pop();
}

KK 算法的时间复杂度为 O(n log n)，空间复杂度为 O(n)，特别适合数字总和非常大、无法使用动态规划的场景。不过它不是精确算法。例如输入 [8, 7, 6, 5, 4]，真实最优差是 0，因为 8+7=15，6+5+4=15；但 KK 会先取 8 和 7 得到 1，再取 6 和 5 得到 1，接着 4 和 1 得到 3，最终差值为 2。这个例子说明 KK 可能出现偏差，但在大多数随机数据上，它的平均表现远好于降序贪心，而且运行速度稳定。

三、降序贪心与三种方案对比

降序贪心是最直观的在线分配策略：先对数组降序排序，然后维护两个子集和。每拿到一个数字，就把它放进当前和较小的子集，直到全部处理完。这个算法实现简单、执行快，但属于典型的局部最优，不一定能拿到全局最优。代码可以同时返回两个子集，便于实际展示分区结果。

function greedyPartition(nums) {
  if (!Array.isArray(nums) || nums.length === 0) {
    return { diff: 0, subsetA: [], subsetB: [] };
  }

  const sorted = [...nums].sort((a, b) => b - a);
  const subsetA = [];
  const subsetB = [];
  let sumA = 0;
  let sumB = 0;

  for (const num of sorted) {
    if (sumA <= sumB) {
      subsetA.push(num);
      sumA += num;
    } else {
      subsetB.push(num);
      sumB += num;
    }
  }

  return {
    diff: Math.abs(sumA - sumB),
    subsetA,
    subsetB
  };
}

从准确度角度看，动态规划是精确算法，KK 是高质量启发式，降序贪心则更简单直接。可以用一个随机数组来观察差异：当数组为 [10, 8, 7, 6, 5] 时，动态规划能得到最优差 0，KK 得到 2，降序贪心得到 2；但如果换成更分散的数据，三者差距会增大。工程上常根据数组长度和总和大小来选择方案。若 total sum 在百万以内，优先用 DP；若达到千万甚至更大，建议用 KK；若只是需要快速给出一个可接受的分配结果，贪心已经够用。

下面用表格汇总三种方案的特性，方便在实际项目里做决策。

还需要注意输入中的非负性。动态规划的前提是数字均为非负整数；如果包含负数，可以把所有数加上同一个偏移量再处理，但分区结果需要额外还原。实际业务中，数字划分更多用于耗时、权重、容量等非负指标，因此这一限制通常不会造成太大困扰。空数组或单元素数组属于退化情况，直接返回 0 或单个元素即可。

四、在 Node.js 项目中封装与测试

把上述三个函数放在一个模块中，可以方便地在不同业务里调用。Node.js 遵循 CommonJS 模块规范，用 module.exports 导出即可。测试时可以直接比较三种算法在同一输入下的结果，也可以对 DP 和 KK 的差值做相对误差统计。下面给出一个最小可运行的封装与测试示例。

const { partitionDP, karmarkarKarp, greedyPartition } = require('./number-partition');

const tasks = [23, 45, 12, 67, 34, 89, 21, 56];

console.log('动态规划精确差：', partitionDP(tasks));
console.log('Karmarkar-Karp 差：', karmarkarKarp(tasks));
console.log('降序贪心差：', greedyPartition(tasks).diff);

在这个测试中，任务总时长并不大，动态规划可以快速给出精确值，KK 和贪心则可以作为对照组。如果换成更大的数据集，比如随机生成 1000 个 1 到 100000 之间的整数，动态规划的内存占用会非常高，这时 KK 的优势就显现出来。实际调优时，可以先统计数组总和，再决定走哪条分支：总和小于某个阈值走 DP，否则走 KK；若对实时性要求极高，也可以直接使用贪心或 KK。

数字划分问题看似简单，但它反映了 NP 难问题在工程中的典型处理方式：小规模用精确算法，大规模用启发式算法。Node.js 的异步和非阻塞特性并不会改变这些算法本身的复杂度，但由于 JavaScript 对象和数组操作比较灵活，实现这些算法时可以更专注于逻辑本身。只要根据数据规模选对算法，就能在调度、分片、负载均衡等场景中快速得到可用的划分结果。

Node.js数字划分Number Partitioning修改时间：2026-10-06 10:28:32