PHP如何通过产品组合计算对应预订时长的最优定价

需求背景 #

需要根据用户预订时长组合不同档位的时长产品，计算最低支付价格，最低预订时长为1小时。定价规则如下：

• 1小时产品价格200美元
• 1小时30分钟产品价格280美元
• 额外30分钟附加产品价格90美元
• 若总时长无法通过1小时、1小时30分钟产品恰好凑出，不足部分按每30分钟90美元补收

产品明细 #

最优解决思路 #

该问题本质是可重复选物品的最小成本凑数问题（无界背包问题），不需要暴力枚举所有组合，用动态规划方案可以高效求解，时间复杂度仅为O(n)，n为取整后的预订时长/30，远优于递归枚举方案：

1. 时长预处理：将用户输入的预订时长转换为分钟数，首先兜底到最低1小时（60分钟），再向上取整到最近的30的倍数（所有产品时长都是30的倍数，不足部分自动补30分钟产品）
2. 动态规划定义：设dp[i]为凑出i分钟时长需要的最低价格，初始化dp[0]=0（0分钟价格为0），其余位置初始化为无穷大
3. 状态转移：遍历每个时长点位，用所有可选用的产品更新当前点位的最低价格：如果当前时长i大于等于某产品时长，那么dp[i] = min(dp[i], dp[i-产品时长] + 产品价格)
4. 最终dp[预处理后的时长]就是所求的最低价格

原PHP代码问题原因 #

你改写的PHP代码和JS版本逻辑不一致，主要错误点：

1. JS版本每次递归传递的是r.slice().concat(a)，是新生成的数组，不同递归分支互不干扰；而PHP版本直接修改传入的$resultTracker数组，没有做副本，导致不同分支的结果互相污染
2. 递归返回的结果没有展平，最终得到的是多层嵌套数组，无法直接统计组合价格

PHP高效实现代码 #

/**
 * 计算预订时长的最优价格
 * @param int $bookMinutes 用户预订的分钟数
 * @return int 最低价格（单位：美元）
 */
function getOptimalPrice(int $bookMinutes): int
{
    // 定义产品列表：[时长（分钟）, 价格（美元）]
    $products = [
        ['duration' => 30, 'price' => 90],
        ['duration' => 60, 'price' => 200],
        ['duration' => 90, 'price' => 280],
    ];

    // 最低预订时长1小时兜底
    if ($bookMinutes < 60) {
        $bookMinutes = 60;
    }

    // 向上取整到最近的30的倍数，自动覆盖不足补30分钟的规则
    $targetMinutes = (int)ceil($bookMinutes / 30) * 30;

    // 初始化DP数组
    $dp = array_fill(0, $targetMinutes + 1, PHP_INT_MAX);
    $dp[0] = 0;

    // 状态转移计算每个时长的最低价格
    for ($i = 1; $i <= $targetMinutes; $i++) {
        foreach ($products as $product) {
            $d = $product['duration'];
            $p = $product['price'];
            if ($d <= $i && $dp[$i - $d] !== PHP_INT_MAX) {
                $dp[$i] = min($dp[$i], $dp[$i - $d] + $p);
            }
        }
    }

    return $dp[$targetMinutes];
}

// 测试示例
// 预订2小时（120分钟），输出370，符合预期
echo getOptimalPrice(120);
// 预订1小时30分钟（90分钟），输出280，符合预期
echo getOptimalPrice(90);
// 预订70分钟，向上取整到90分钟，输出280
echo getOptimalPrice(70);

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