用 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我有两个选择不用这张券最大抵扣额依然是$dp[$j]。用这张券最大抵扣额是$dp[$j - $cost](剩余金额的最大抵扣) $cost(当前券面额)。取两者较大值。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或负数的券$couponsarray_filter($coupons,function($c){return$c0;});// 重置索引$couponsarray_values($coupons);$ncount($coupons);if($n0||$orderAmount0){return[max_deduction0,used_coupons[]];}// 2. 初始化 DP 数组// $dp[$j] 表示金额为 $j 时能凑出的最大抵扣额// 大小设为 $orderAmount 1$dparray_fill(0,$orderAmount1,0);// 用于回溯记录选择了哪些券// $path[$j] 存储在金额 $j 时最后加入的那张券的索引$patharray_fill(0,$orderAmount1,-1);// 3. 动态规划过程for($i0;$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($currentWeight0$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] 的券$order100;$myCoupons[10,20,50,80,10];echo订单金额:{$order}元\n;echo可用券: .implode(, ,$myCoupons). 元\n;$resultoptimizeCouponCombination($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] 的券$order295;$myCoupons2[10,20,50];echo\n--- 案例 2 ---\n;echo订单金额:{$order2}元\n;echo可用券: .implode(, ,$myCoupons2). 元\n;$result2optimizeCouponCombination($order2,$myCoupons2);echo最优抵扣:{$result2[max_deduction]}元\n;// 应该是 80 (502010)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. 业务场景的复杂性扩展真实电商场景远比这个复杂以下是认知牢笼的突破方向复杂场景算法变体解决思路优惠券互斥分组背包将互斥的券分为一组如“京东券”组“PLUS券”组每组只能选一个或不选。满减门槛带约束背包券不仅有“价值”减免额还有“重量”门槛。只有当订单金额 门槛时该券才可用。需在 DP 前预过滤。无限张券完全背包如果某种券可以用多次如积分抵扣将内层循环改为正序遍历。最小找零/凑单硬币问题如果目标是“用最少数量的券凑够金额”DP 值存储的是“券的数量”而非“面额总和”。海量数据启发式算法如果券有几千张DP 太慢。可用贪心算法先选大面额或遗传算法求近似解。四、认知跃迁从代码到架构别在 PHP 里做重型计算如果N NN和W WW极大如秒杀场景万人同时算最优组合PHP 的单线程会成为瓶颈。对策将算法下沉到C 扩展、Go 微服务或使用Redis Lua 脚本执行简单的贪心逻辑。预计算与缓存优惠券组合是有限的。可以离线计算出常见金额10-1000元的最优券组合存入 Redis。用户下单时直接查表GET coupon_optimal:{order_amount}。用户体验优先算法算出“最优”可能需要 100ms。工程权衡是否值得有时“次优但快速”的方案如贪心更能提升转化率。 总结PHP 实现背包算法解决优惠券问题本质是用O ( N ⋅ W ) O(N \cdot W)O(N⋅W)的计算成本换取用户的“最大实惠”和平台的“精准营销”。核心动态规划逆序遍历。关键理解业务约束互斥、门槛、叠加。进阶从单机 PHP 走向分布式预计算。行动指令复制代码运行上述 PHP 脚本验证结果。修改场景尝试加入“互斥组”逻辑分组背包。性能测试生成 1000 张券订单金额 10000 元测试耗时。思维升级记住算法不仅是面试题它是业务利润的杠杆。