用 PHP 实现一个简单的“背包算法”，解决优惠券最优组合问题。

它的本质是：在有限的“预算约束”（背包容量）下，从一组“优惠券”（物品）中选择子集，使得“减免金额”（价值）最大化。这是一个经典的0/1 背包问题 (0/1 Knapsack Problem)——因为每张优惠券通常只能用一次。

如果把购物比作装箱游戏：

• 背包容量 (W WW)：你的订单总金额（或者你愿意支付的最高金额，视具体业务定义而定，通常是满减门槛或总预算）。
• 物品 (I t e m s ItemsItems)：可用的优惠券。
• 物品重量 (w i w_iwi​)：使用这张券所需的最低消费门槛，或者券的面额（取决于业务逻辑，通常我们将“节省的钱”视为价值，将“占用预算”视为重量，但在优惠券场景中，更常见的是多重约束或互斥选择。为了简化，我们假设目标是：在不超过订单总额的前提下，选择能减免最多金额的券组合）。
• 物品价值 (v i v_ivi​)：券能减免的金额。
• 核心逻辑：别贪心（只选面值最大的），要全局最优。有时候两张小券组合比一张大券更划算。

⚠️ 业务修正：真实的优惠券系统非常复杂（互斥、叠加、品类限制）。这里我们简化为：给定一组可用优惠券，找出一个组合，使得总减免金额最大，且满足所有券的使用条件（如满100减10，订单需>100）。

为了演示算法本质，我们采用最标准的模型：假设订单金额固定为M MM，有一组优惠券，每张券有“门槛”和“减免额”。我们要选出若干张券（假设可叠加，或仅选一张最优，此处演示多选一或有限叠加的简化版）。

更贴切的场景是：你有 100 元预算，想买几样东西（物品），每样东西有价格和满意度（价值）。这是标准背包。

针对“优惠券组合”的特殊性：通常优惠券是互斥的（只能选一张）或分层叠加的。如果完全互斥，只需遍历找最大值O ( N ) O(N)O(N)。如果需要组合（如店铺券+平台券），则是多维背包或分组背包。

下面实现一个通用的 0/1 背包模型，场景设定为：
“你有 N 张可用的‘立减券’（无门槛，但每人限用一张组合中的特定类型），或者更常见的：你要从一堆‘满减券’中，选出能用的、且减免最多的那张。”

等等，如果只能选一张，那太简单了。让我们做一个更有意义的场景：**
“凑单神器”：你购物车里有若干商品（物品），你有固定的预算（背包容量）。如何选择商品组合，使得在预算内，获得的总积分/满意度（价值）最高？

或者，回到题目：优惠券最优组合。
假设场景：平台允许叠加使用多张“折扣券”（例如：一张9折券，一张满100减10券，一张满200减30券）。但通常优惠券有互斥规则。

为了体现算法价值，我们解决这个经典变体：
“你有W WW元的预算，要去超市买东西。超市里有N NN种商品，每种商品有价格w i w_iwi​和 效用值v i v_ivi​（比如喜好程度或刚需程度）。如何在预算内让效用值最大？”

既然题目明确说“优惠券最优组合”，我们换一个更贴合的算法题：“代金券组合支付”。
场景：你有一堆小额代金券（1元、5元、10元…），你要支付一笔订单。如何组合这些券，使得使用的券总面额最接近订单金额（且不超支），从而最大化抵扣？
这就是标准的Subset Sum Problem(子集和问题)，是背包问题的特例（价值=重量）。

以下我将实现**“代金券最大化抵扣”**（子集和问题/0/1背包特例）的 PHP 代码。

一、算法核心：动态规划 (DP)

1. 状态定义

dp[j]表示：当可用预算（或目标抵扣额）为j元时，能凑出的最大抵扣金额。

2. 状态转移方程

对于每一张面额为cost的代金券：

// 逆序遍历，确保每张券只用一次 (0/1 背包)for($j=$target;$j>=$cost;$j--){$dp[$j]=max($dp[$j],$dp[$j-$cost]+$cost);}

• 解释：对于当前金额j，我有两个选择：
  1. 不用这张券：最大抵扣额依然是$dp[$j]。
  2. 用这张券：最大抵扣额是$dp[$j - $cost](剩余金额的最大抵扣) +$cost(当前券面额)。
  3. 取两者较大值。

3. 初始条件

dp[0] = 0(0元订单抵扣0元)，其余为 0。

二、PHP 实战代码

<?php/** * 优惠券/代金券最优组合算法 (0/1 背包变体 - 子集和问题) * * @param int $orderAmount 订单金额 (背包容量) * @param array $coupons 可用代金券面额数组 (物品重量=价值) * 例如: [5, 10, 20, 50, 100] * @return array ['max_deduction' => int, 'used_coupons' => array] */functionoptimizeCouponCombination(int$orderAmount,array$coupons):array{// 1. 数据预处理// 过滤掉面额为0或负数的券$coupons=array_filter($coupons,function($c){return$c>0;});// 重置索引$coupons=array_values($coupons);$n=count($coupons);if($n===0||$orderAmount<=0){return['max_deduction'=>0,'used_coupons'=>[]];}// 2. 初始化 DP 数组// $dp[$j] 表示金额为 $j 时能凑出的最大抵扣额// 大小设为 $orderAmount + 1$dp=array_fill(0,$orderAmount+1,0);// 用于回溯记录选择了哪些券// $path[$j] 存储在金额 $j 时，最后加入的那张券的索引$path=array_fill(0,$orderAmount+1,-1);// 3. 动态规划过程for($i=0;$i<$n;$i++){$cost=$coupons[$i];// 0/1 背包必须逆序遍历，防止同一张券被重复使用for($j=$orderAmount;$j>=$cost;$j--){// 如果使用了这张券，能否获得更大的抵扣额？// 因为是子集和问题，价值=重量，所以其实就是看能不能凑得更满if($dp[$j-$cost]+$cost>$dp[$j]){$dp[$j]=$dp[$j-$cost]+$cost;$path[$j]=$i;// 记录路径：在金额 j 时，选了第 i 张券}}}// 4. 获取最大抵扣额$maxDeduction=$dp[$orderAmount];// 5. 回溯找出具体用了哪些券$usedCoupons=[];$currentWeight=$orderAmount;// 从最终状态往回推while($currentWeight>0&&$path[$currentWeight]!=-1){$couponIndex=$path[$currentWeight];$couponValue=$coupons[$couponIndex];$usedCoupons[]=$couponValue;// 减去这张券的面额，回到上一个状态$currentWeight-=$couponValue;// 为了防止死循环（虽然逻辑上不会），可以标记该路径点已处理// 但在标准回溯中，直接减重量即可，因为 path 是基于上一轮迭代记录的}return['max_deduction'=>$maxDeduction,'used_coupons'=>$usedCoupons,'remaining_pay'=>$orderAmount-$maxDeduction];}// --- 测试案例 ---// 案例 1: 订单 100 元，手上有 [10, 20, 50, 80, 10] 的券$order=100;$myCoupons=[10,20,50,80,10];echo"订单金额:{$order}元\n";echo"可用券: ".implode(', ',$myCoupons)." 元\n";$result=optimizeCouponCombination($order,$myCoupons);echo"最优抵扣:{$result['max_deduction']}元\n";echo"使用券组合: [".implode(', ',$result['used_coupons'])."] 元\n";echo"实际支付:{$result['remaining_pay']}元\n";/* 预期输出: 订单金额: 100 元 可用券: 10, 20, 50, 80, 10 元 最优抵扣: 100 元 (80 + 20 或 50 + 20 + 10 + 10 + ... 取决于具体组合，算法会找刚好等于100的) 使用券组合: [80, 20] (或者 [50, 20, 10, 10, 10] 如果有更多10元) 实际支付: 0 元 */// 案例 2: 订单 95 元，手上有 [10, 20, 50] 的券$order2=95;$myCoupons2=[10,20,50];echo"\n--- 案例 2 ---\n";echo"订单金额:{$order2}元\n";echo"可用券: ".implode(', ',$myCoupons2)." 元\n";$result2=optimizeCouponCombination($order2,$myCoupons2);echo"最优抵扣:{$result2['max_deduction']}元\n";// 应该是 80 (50+20+10)echo"使用券组合: [".implode(', ',$result2['used_coupons'])."] 元\n";echo"实际支付:{$result2['remaining_pay']}元\n";// 15

三、复杂度分析与优化

1. 时间复杂度

• O ( N × W ) O(N \times W)O(N×W)
  • N NN: 优惠券数量。
  • W WW: 订单金额（背包容量）。
• 瓶颈：如果订单金额很大（如 10,000 元），且券很多，循环次数会达到百万级。但在 PHP 中，百万级循环通常在几十毫秒内完成，完全可以接受。

2. 空间复杂度

• O ( W ) O(W)O(W)
  • 只需要一个长度为OrderAmount + 1的数组。
  • 通过滚动数组（逆序遍历）优化，将二维 DP 降为一维。

3. 业务场景的复杂性扩展

真实电商场景远比这个复杂，以下是认知牢笼的突破方向：

四、认知跃迁：从代码到架构

1. 别在 PHP 里做重型计算：

   • 如果N NN和W WW极大（如秒杀场景，万人同时算最优组合），PHP 的单线程会成为瓶颈。
   • 对策：将算法下沉到C 扩展、Go 微服务，或使用Redis Lua 脚本执行简单的贪心逻辑。

2. 预计算与缓存：

   • 优惠券组合是有限的。可以离线计算出常见金额（10-1000元）的最优券组合，存入 Redis。
   • 用户下单时，直接查表：GET coupon_optimal:{order_amount}。

3. 用户体验优先：

   • 算法算出“最优”可能需要 100ms。
   • 工程权衡：是否值得？有时“次优但快速”的方案（如贪心）更能提升转化率。

🚀 总结

PHP 实现背包算法解决优惠券问题，本质是用O ( N ⋅ W ) O(N \cdot W)O(N⋅W)的计算成本，换取用户的“最大实惠”和平台的“精准营销”。

• 核心：动态规划，逆序遍历。
• 关键：理解业务约束（互斥、门槛、叠加）。
• 进阶：从单机 PHP 走向分布式预计算。

行动指令：

1. 复制代码：运行上述 PHP 脚本，验证结果。
2. 修改场景：尝试加入“互斥组”逻辑（分组背包）。
3. 性能测试：生成 1000 张券，订单金额 10000 元，测试耗时。
4. 思维升级：记住，算法不仅是面试题，它是业务利润的杠杆。