儿童金融练习项目：实现指定金额的纸币选取函数求助

我正在开发一款面向儿童的金融练习项目，其中一个练习环节为学生将纸币添加至钱包，钱包数据以如下数组形式存储：

var walletArray = [
  {
    code: 'aed',
    denomination: 0.5,
    image: "/assets/images/coin50",
    type: "coin",
  },
  { code: 'aed', denomination: 1, image: "/assets/images/coin1", type: "coin" },
  { code: 'aed', denomination: 5, image: "/assets/images/bill5", type: "bill" },
  { code: 'aed', denomination: 5, image: "/assets/images/bill5", type: "bill" },
  { code: 'aed', denomination: 10, image: "/assets/images/bill10", type: "bill" },
  { code: 'aed', denomination: 50, image: "/assets/images/bill50", type: "bill" },
];

需要编写一个函数，接收用户输入的整数金额（例如17），输出需要支付的对应纸币（如面额5、5、10），后续将基于此计算找零。目前已实现计算钱包总金额并判断输入金额是否超出余额的calculateTotal函数，但无法实现从数组中选取对应金额纸币的逻辑，仅能处理输入金额与单张纸币面额完全匹配的情况。

1. 修正现有calculateTotal函数 #

原函数存在全局变量污染、payAmount未作为参数传入的问题，修正后版本：

function calculateTotal(walletArray) {
  let total = 0;
  for (let i = 0; i < walletArray.length; i++) {
    total += walletArray[i].denomination;
  }
  return total;
}

// 判断支付金额是否超出余额的独立函数
function isAmountExceed(walletArray, payAmount) {
  const total = calculateTotal(walletArray);
  if (payAmount > total) {
    console.log("ABOVE LIMIT");
    return true;
  }
  return false;
}

2. 纸币选取函数实现 #

贪心算法版本（优先大面额，符合日常支付逻辑）

先将钱包内纸币按面额从大到小排序，依次选取纸币凑够目标金额，适合儿童理解的支付场景：

function selectPaymentNotes(walletArray, targetAmount) {
  if (isAmountExceed(walletArray, targetAmount)) {
    return null;
  }

  // 复制数组并降序排序，避免修改原钱包数据
  const sortedWallet = [...walletArray].sort((a, b) => b.denomination - a.denomination);
  
  let remaining = targetAmount;
  const selectedNotes = [];

  for (const note of sortedWallet) {
    if (note.denomination <= remaining) {
      selectedNotes.push(note);
      remaining -= note.denomination;
      
      // 处理浮点数运算精度误差
      if (Math.abs(remaining) < 0.001) {
        remaining = 0;
        break;
      }
    }
  }

  return remaining === 0 ? selectedNotes.map(note => note.denomination) : null;
}

// 测试示例
const target = 17;
const result = selectPaymentNotes(walletArray, target);
if (result) {
  console.log(`需要支付的纸币面额：${result.join(', ')}`); // 输出：10, 5, 5
} else {
  console.log("无法凑出目标金额");
}

回溯算法版本（处理特殊组合场景）

如果钱包存在特殊纸币组合（比如[3,3,5]凑6），贪心算法会失效，此时用回溯枚举所有可能组合：

function selectPaymentNotesBacktrack(walletArray, targetAmount) {
  if (isAmountExceed(walletArray, targetAmount)) {
    return null;
  }

  let result = null;
  const sortedWallet = [...walletArray].sort((a, b) => b.denomination - a.denomination);

  function backtrack(start, currentSum, selected) {
    if (result) return; // 找到解后立即终止
    if (Math.abs(currentSum - targetAmount) < 0.001) {
      result = [...selected];
      return;
    }
    if (currentSum > targetAmount) return;

    for (let i = start; i < sortedWallet.length; i++) {
      // 跳过重复面额，避免生成重复组合
      if (i > start && sortedWallet[i].denomination === sortedWallet[i-1].denomination) continue;
      selected.push(sortedWallet[i]);
      backtrack(i + 1, currentSum + sortedWallet[i].denomination, selected);
      selected.pop();
    }
  }

  backtrack(0, 0, []);
  return result ? result.map(note => note.denomination) : null;
}

// 测试特殊场景
const testWallet = [
  { code: 'aed', denomination: 3, type: "bill" },
  { code: 'aed', denomination: 3, type: "bill" },
  { code: 'aed', denomination: 5, type: "bill" },
];
console.log(selectPaymentNotesBacktrack(testWallet, 6)); // 输出：[3, 3]

内容的提问来源于stack exchange，提问作者Abrar Anwar