通勤者最优购票组合Web应用实现技术咨询

嘿，这个问题我之前帮朋友做类似工具时碰到过，确实和背包问题沾边，但因为是最小化成本而非最大化价值，反而有更直接的解法。咱们一步步来拆解：

先理清三种车票的性价比 #

先算清楚每种票的单位成本，帮你快速判断方向：

• 单次票：$6.50/次（最不划算，仅适合偶尔出行）
• 10次票：$49.80/10 = $4.98/次（比单次划算很多，适合每月出行10-29次的情况）
• 月卡：$149.40固定成本，相当于当你每月出行≥30次时，和3张10次票成本持平；超过30次后，月卡直接更划算。

解法一：枚举法（简单直接，适合当前3种票的场景） #

因为选项只有3种，直接枚举所有可能的组合，取成本最低的即可：
对于给定的每月出行次数N，我们需要计算三种核心场景的成本：

1. 全买单次票：cost_single = N * 6.5
2. 直接买月卡：cost_month = 149.4
3. 10次票+单次票组合：遍历所有可能的10次票数量k（从0到Math.floor(N/10)），计算成本k*49.8 + (N - 10*k)*6.5，取这个序列里的最小值cost_combination

最终最优成本就是Math.min(cost_single, cost_month, cost_combination)

举个例子：当N=25时

• 全单次：25*6.5=162.5
• 月卡：149.4
• 组合：2张10次+5张单次=49.82 +6.55=132.1
  显然组合是最优解。

解法二：动态规划（扩展性强，适合未来加更多票种） #

如果以后要新增周卡、5次票等类型，动态规划会更灵活。我们定义dp[i]为覆盖i次出行的最小成本，然后逐步推导：

核心思路 #

• 初始化：dp[0] = 0（0次出行成本为0），其他dp[i]初始化为无穷大
• 对于每个i（从1到N），我们有三种选择：
  1. 买一张单次票：dp[i] = Math.min(dp[i], dp[i-1] + 6.5)
  2. 买一张10次票（如果i≥10）：dp[i] = Math.min(dp[i], dp[i-10] + 49.8)
  3. 直接买月卡：dp[i] = Math.min(dp[i], 149.4)
• 最后dp[N]就是最小成本，还可以通过回溯找到具体的车票组合

代码示例（JavaScript） #

function getCheapestTicketCombo(rideCount) {
    // 转成整数避免浮点数精度问题（单位：分）
    const single = 650;
    const tenTrip = 4980;
    const monthly = 14940;

    const dp = new Array(rideCount + 1).fill(Infinity);
    dp[0] = 0;

    // 填充dp数组
    for (let i = 1; i <= rideCount; i++) {
        // 选项1：加一张单次票
        dp[i] = Math.min(dp[i], dp[i - 1] + single);
        // 选项2：加一张10次票
        if (i >= 10) {
            dp[i] = Math.min(dp[i], dp[i - 10] + tenTrip);
        }
        // 选项3：直接买月卡
        dp[i] = Math.min(dp[i], monthly);
    }

    // 回溯找到具体组合
    let remaining = rideCount;
    const combo = {
        single: 0,
        tenTrip: 0,
        monthly: 0
    };

    if (dp[remaining] === monthly) {
        combo.monthly = 1;
        remaining = 0;
    } else {
        while (remaining > 0) {
            if (remaining >= 10 && dp[remaining] === dp[remaining - 10] + tenTrip) {
                combo.tenTrip += 1;
                remaining -= 10;
            } else if (dp[remaining] === dp[remaining - 1] + single) {
                combo.single += 1;
                remaining -= 1;
            }
        }
    }

    return {
        minCost: (dp[rideCount] / 100).toFixed(2),
        combination: combo
    };
}

// 测试用例
console.log(getCheapestTicketCombo(25));
// 输出：{ minCost: "132.10", combination: { single: 5, tenTrip: 2, monthly: 0 } }
console.log(getCheapestTicketCombo(31));
// 输出：{ minCost: "149.40", combination: { single: 0, tenTrip: 0, monthly: 1 } }

注意事项 #

• 浮点数精度：建议把金额转成整数（比如分）计算，避免JavaScript中浮点数相加的精度误差
• 边界情况：比如N=0（不需要买票）、N=30（月卡和3张10次票成本相同，两种组合都可以）

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