如何用 JavaScript 实现按指定张数精确拆分金额的找零函数-js教程-PHP中文网

如何用 JavaScript 实现按指定张数精确拆分金额的找零函数

本文介绍一个递归回溯算法，用于将给定总金额 price 拆分为恰好 pcs 张预设面额的组合（如 [100000, 50000, 20000, 10000, 5000, 2000, 1000]），若无解则返回空数组。

本文介绍一个递归回溯算法，用于将给定总金额 price 拆分为恰好 pcs 张预设面额的组合（如 [100000, 50000, 20000, 10000, 5000, 2000, 1000]），若无解则返回空数组。

该问题本质是带数量约束的整数划分问题：在固定面额集合中，选出恰好 pcs 个数（可重复），使其和等于 price。由于面额不可分割、数量严格限定，贪心策略（如优先用大面额）在此失效——例如 price=10000, pcs=4 时，若贪心选 5000 后剩余 5000 需拆成 3 张，但 5000 无法被 2000/1000 组合成 3 张有效解（2000+2000+1000=5000 ✅），而纯贪心可能误入死路。因此需采用回溯搜索，系统性尝试所有可行组合。

核心思路是深度优先递归，每层决策是否“选用当前面额”：

选：从 price 中减去该面额，pcs 减 1，保持当前面额索引不变（允许重复使用同一面额）；
不选：跳过当前面额，索引 +1，继续尝试更小面额。

递归终止条件：

✅ 成功：price === 0 && pcs === 0 → 返回空数组（递归底，由上层拼接结果）；
❌ 失败：price 、<code>pcs 或面额索引越界 → 返回 <code>null 表示此路径无效。

以下是完整实现：

Alibabacloud Sdk Client Initialization For Java

在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。

下载

const denominations = [100000, 50000, 20000, 10000, 5000, 2000, 1000];

const findDenominations = (price, pcs, start = 0) => {
  // 成功终止：金额与张数均耗尽
  if (price === 0 && pcs === 0) return [];
  // 失败终止：超支、张数过多、面额用尽
  if (price = denominations.length) return null;

  const current = denominations[start];

  // 尝试选用当前面额（可重复）
  const withCurrent = findDenominations(price - current, pcs - 1, start);
  if (withCurrent !== null) {
    return [current, ...withCurrent];
  }

  // 尝试跳过当前面额，试下一张
  return findDenominations(price, pcs, start + 1);
};

const distributeDenominations = (price, pcs) => findDenominations(price, pcs) || [];

// 测试用例
console.log(distributeDenominations(40000, 4)); // [10000, 10000, 10000, 10000]
console.log(distributeDenominations(10000, 4)); // [5000, 2000, 2000, 1000]
console.log(distributeDenominations(40000, 2)); // [20000, 20000]
console.log(distributeDenominations(50000, 2)); // []

⚠️ 注意事项：

该算法时间复杂度最坏为指数级 O(d^pcs)（d 为面额种类数），适用于 pcs 较小（如 ≤ 10）的业务场景；
若需更高性能，可引入记忆化（Memoization）缓存 (price, pcs, start) 状态，避免重复计算；
面额数组必须降序排列（已满足），确保优先尝试大面额，提升早期剪枝效率；
返回结果不保证唯一性（如 40000,4 也可能返回 [20000,10000,5000,5000]），若需“最简组合”（最少不同面额数），需额外添加启发式排序或动态规划优化。