基于NodeJS高效计算Team Fortress 2货币支付组合

货币兑换规则 #

在《Team Fortress 2》中，流通货币及与ref的兑换关系（以ref为基准）：

• 1 weapon = 1/18 ref ≈ 0.05 ref
• 1 scrap = 1/9 ref ≈ 0.11 ref
• 1 rec = 1/3 ref ≈ 0.33 ref
• 1 key = 90 ref

价格示例 #

• 1.49 ref = 1 ref + 1 rec + 1 scrap + 1 weapon
• 2.11 ref = 2 ref + 1 scrap
• 1.50 keys = 1 key + 45 ref

需求说明 #

需要用Node.js实现以下功能：

1. 输入目标价格后，生成所有可行的支付组合
2. 组合按货币总数量从少到多排序（例如0.22 ref的组合排序为：2 scrap、1 scrap+2 weapons、4 weapons）
3. 结合库存数据，筛选出库存可实现的首个最优组合

现有代码问题 #

原代码存在以下缺陷：

• 浮点数计算精度误差，导致剩余价格判断失效
• 生成的组合为单个货币的数组，未统计每种货币的数量，不利于排序和展示
• 未对组合按总数量排序
• 未筛选库存可实现的最优组合

原代码如下：

function findCombinations(price, inventory) {
  const combinations = [];

  function generateCombinations(remainingPrice, currentCombination, currentInventory) {
    if (remainingPrice === 0) {
      combinations.push(currentCombination);
      return;
    }

    for (const item in currentInventory) {
      const itemPrice = getItemPrice(item);

      if (itemPrice <= remainingPrice && currentInventory[item] > 0) {
        const updatedCombination = [...currentCombination, item];
        const updatedInventory = { ...currentInventory };
        updatedInventory[item]--;

        generateCombinations(
          remainingPrice - itemPrice,
          updatedCombination,
          updatedInventory
        );
      }
    }
  }

  function getItemPrice(item) {
    const prices = {
      weapon: 0.05, 
      scrap: 0.11, 
      rec: 0.33, 
      ref: 1, 
      key: 90.0 
    };

    return prices[item];
  }

  generateCombinations(price, [], inventory);

  return combinations;
}

// Example:

const price = 0.22;
const inventory = {
  weapon: 4,
  scrap: 5
};

const combinations = findCombinations(price, inventory);

console.log("Combinations to pay", price, "refs:");
combinations.forEach((combination, index) => {
  console.log(`Combination ${index + 1}:`, combination);
});

优化后的代码 #

核心优化点 #

1. 用整数计算避免精度误差：将所有价格转换为以1/18 ref为单位的整数（即weapon的价格为1），彻底解决浮点数精度问题
2. 组合统计结构化：生成的组合以{ weapon: x, scrap: y, ... }的形式存储，方便统计总数量和展示
3. 按总数量排序：生成所有组合后，按货币总数量升序排列
4. 库存筛选：从排序后的组合中，找出第一个库存可满足的组合

// 定义每种货币对应的单位数量（1单位 = 1/18 ref）
const UNIT_PRICES = {
  weapon: 1,
  scrap: 2,    // 1/9 ref = 2/18 ref
  rec: 6,      // 1/3 ref = 6/18 ref
  ref: 18,     // 1 ref = 18/18 ref
  key: 90 * 18 // 90 ref = 1620/18 ref
};

// 将目标价格转换为整数单位
function priceToUnits(price) {
  // 处理keys转ref的情况，比如输入1.5 keys则转换为1.5*90=135 ref
  if (typeof price === 'object' && price.type === 'key') {
    return Math.round(price.amount * UNIT_PRICES.key);
  }
  // 默认按ref计算
  return Math.round(price * 18);
}

// 生成所有可能的支付组合
function generateAllCombinations(targetUnits) {
  const combinations = [];
  // 按货币价值从高到低遍历，优先生成高价值货币的组合（减少后续排序压力）
  const currencyTypes = ['key', 'ref', 'rec', 'scrap', 'weapon'];

  function backtrack(remaining, current, index) {
    if (remaining === 0) {
      // 计算总数量并加入组合
      const total = Object.values(current).reduce((sum, count) => sum + count, 0);
      combinations.push({ ...current, total });
      return;
    }
    if (index >= currencyTypes.length) return;

    const type = currencyTypes[index];
    const unitPrice = UNIT_PRICES[type];
    // 当前货币最多能用的数量
    const maxCount = Math.floor(remaining / unitPrice);

    // 从0到maxCount尝试每种数量
    for (let count = maxCount; count >= 0; count--) {
      current[type] = count;
      backtrack(remaining - count * unitPrice, current, index + 1);
      // 回溯，清除当前货币的数量（可选，因为下一次循环会覆盖）
      delete current[type];
    }
  }

  backtrack(targetUnits, {}, 0);
  return combinations;
}

// 筛选库存可实现的组合，并返回首个最优组合
function findOptimalCombination(price, inventory) {
  const targetUnits = priceToUnits(price);
  if (targetUnits <= 0) return null;

  // 生成所有组合并按总数量升序排序
  const allCombinations = generateAllCombinations(targetUnits).sort((a, b) => a.total - b.total);

  // 筛选库存满足的组合
  for (const combo of allCombinations) {
    let isValid = true;
    for (const [type, required] of Object.entries(combo)) {
      if (type === 'total') continue;
      if ((inventory[type] || 0) < required) {
        isValid = false;
        break;
      }
    }
    if (isValid) {
      // 移除total字段，返回纯组合数据
      const { total, ...result } = combo;
      return result;
    }
  }

  // 没有可用组合
  return null;
}

// 示例使用
// 示例1：0.22 ref的情况
const price1 = 0.22;
const inventory1 = {
  weapon: 4,
  scrap: 5
};
const optimal1 = findOptimalCombination(price1, inventory1);
console.log(`0.22 ref的最优支付组合：`, optimal1); // 输出：{ scrap: 2 }

// 示例2：1.5 keys的情况
const price2 = { type: 'key', amount: 1.5 };
const inventory2 = {
  key: 1,
  ref: 50
};
const optimal2 = findOptimalCombination(price2, inventory2);
console.log(`1.5 keys的最优支付组合：`, optimal2); // 输出：{ key: 1, ref: 45 }

代码说明 #

• 单位转换：通过将所有价格转为整数单位，彻底避免了浮点数运算的精度问题
• 回溯生成组合：按货币价值从高到低遍历，生成所有可能的组合，同时统计总数量
• 排序与筛选：先按总数量升序排序，再依次检查库存，返回第一个满足条件的组合，即为最优解

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