JavaScript 函数实现按指定张数精确拆分金额（基于给定面额列表）-js教程-PHP中文网

JavaScript 函数实现按指定张数精确拆分金额（基于给定面额列表）

本文介绍如何编写一个 JavaScript 函数，根据给定总金额和张数，从预设面额数组中找出恰好 pcs 张、总和等于 price 的组合；若无解则返回空数组。核心采用带回溯的递归搜索策略，支持重复使用同一面额。

本文介绍如何编写一个 javascript 函数，根据给定总金额和张数，从预设面额数组中找出恰好 `pcs` 张、总和等于 `price` 的组合；若无解则返回空数组。核心采用带回溯的递归搜索策略，支持重复使用同一面额。

在实际业务场景中（如现金找零系统、券码面额分配、红包拆分等），常需将一个总金额 price 拆分为严格固定张数 pcs 的若干份，且每份必须来自一组预定义的合法面额（如 [100000, 50000, 20000, 10000, 5000, 2000, 1000]）。这不同于经典“找零问题”（追求最少张数），而是一个约束更强的组合存在性判定问题：既要满足数量约束，又要满足金额约束，且不可超限或欠配。

该问题本质是有界整数划分（bounded integer partition），需在有限面额集合中寻找长度为 pcs、元素均取自 denominations、和为 price 的序列（允许重复）。由于面额无通解数学规律，暴力枚举+剪枝是最可靠方案。以下提供一个高效、可读性强的递归实现：

Alibabacloud Sdk Client Initialization For Java

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

下载

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

/**
 * 递归查找满足条件的面额组合
 * @param {number} price - 目标总金额（非负整数）
 * @param {number} pcs - 目标张数（非负整数）
 * @param {number[]} denoms - 可用面额数组（降序排列，提升剪枝效率）
 * @param {number} start - 当前搜索起始索引（避免重复组合，但允许复用同一面额）
 * @returns {number[] | null} 成功时返回面额数组，失败返回 null
 */
const findDenominations = (price, pcs, denoms, start = 0) => {
  // ✅ 终止成功条件：金额与张数同时耗尽
  if (price === 0 && pcs === 0) return [];

  // ❌ 终止失败条件：任一约束被违反
  if (price = denoms.length) return null;

  const currentDenom = denoms[start];

  // ? 路径一：尝试使用当前面额（可重复使用 → start 不变）
  const withCurrent = findDenominations(
    price - currentDenom,
    pcs - 1,
    denoms,
    start
  );
  if (withCurrent !== null) {
    return [currentDenom, ...withCurrent];
  }

  // ? 路径二：跳过当前面额，尝试下一个（start + 1）
  return findDenominations(price, pcs, denoms, start + 1);
};

/**
 * 主调用函数：封装递归逻辑，统一返回格式
 * @param {number} price - 总金额
 * @param {number} pcs - 张数
 * @returns {number[]} 满足条件的面额数组，否则返回 []
 */
const distributeDenominations = (price, pcs) => 
  findDenominations(price, pcs, denominations) || [];

// ✅ 测试用例验证
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)); // []

关键设计说明：

面额顺序重要：输入 denominations 应按降序排列（已预设），便于优先匹配大面额，显著提升早期剪枝效率。
重复使用支持：递归中 start 参数保持不变（而非 start + 1）时，允许同一面额被多次选取（如 40000/4 全选 10000）。
路径优先级：先尝试“包含当前面额”，再尝试“跳过”，确保找到首个可行解即返回（无需遍历全部解）。
时间复杂度：最坏为 O(D^pcs)（D 为面额种类数），但在实际面额结构（如指数衰减）和剪枝下表现良好。