动态规划解“优惠券使用”问题：最大化优惠金额

问题分析

给定订单总金额 $S$ 和 $n$ 张优惠券，每张券 $i$ 有两个属性：

• 使用门槛 $T_i$（订单金额需 $\geq T_i$）
• 优惠金额 $D_i$（满足门槛可减免的金额）

目标：选择优惠券子集，在满足以下条件下最大化总优惠金额：

1. 每张券使用门槛 $T_i \leq S$（订单金额固定）
2. 总优惠金额 $\leq S$（实际支付金额 $\geq 0$）
3. 优惠券可叠加使用（无互斥规则）

动态规划建模

1. 状态定义：
   $dp[j]$ 表示总优惠金额不超过 $j$ 时的最大优惠值（$j$ 从 $0$ 到 $S$）

2. 状态转移方程：
   $$ dp[j] = \max \begin{cases} dp[j] & \text{（不选当前券）} \ dp[j - D_i] + D_i & \text{（选当前券，需 } j \geq D_i\text{）} \end{cases} $$

3. 初始化：
   $dp[0..S] = 0$（初始无优惠）

算法步骤

1. 过滤无效券：仅保留 $T_i \leq S$ 的券
2. 特判优化：若券总优惠 $\sum D_i \leq S$，直接返回 $\sum D_i$
3. 动态规划求解：
   • 遍历每张券
   • 倒序更新 $dp[j]$（避免重复选择）

Python实现

def max_discount(S, coupons):
    # 步骤1：过滤无效券（T_i > S的券不可用）
    valid_coupons = [c for c in coupons if c['threshold'] <= S]
    if not valid_coupons:
        return 0
    
    # 步骤2：特判优化（总优惠不超S时直接返回）
    total_discount = sum(c['discount'] for c in valid_coupons)
    if total_discount <= S:
        return total_discount
    
    # 步骤3：动态规划
    dp = [0] * (S + 1)  # 初始化dp数组
    
    for coupon in valid_coupons:
        d = coupon['discount']
        # 倒序更新（从S到d）
        for j in range(S, d - 1, -1):
            if dp[j] < dp[j - d] + d:
                dp[j] = dp[j - d] + d
    
    return dp[S]  # 最大优惠金额

复杂度分析

• 时间复杂度：$O(n \times S)$
  （$n$ 为券数量，$S$ 为订单金额）
• 空间复杂度：$O(S)$
  （优化为一维DP数组）

示例验证

# 输入：订单金额S=100，优惠券列表
coupons = [
    {'threshold': 50, 'discount': 20},
    {'threshold': 80, 'discount': 30},
    {'threshold': 30, 'discount': 10},
    {'threshold': 120, 'discount': 40}  # 此券被过滤（T_i>100）
]

print(max_discount(100, coupons))  # 输出：60 (20+30+10)

业务逻辑说明

1. 门槛检查：仅当 $S \geq T_i$ 时券可用
2. 金额约束：总优惠不超过 $S$（实际支付 $\geq 0$）
3. 最优子结构：通过DP保证局部最优解导向全局最优
4. 叠加规则：默认所有券可叠加（无互斥限制）

关键点：倒序遍历确保每张券仅选一次，正序会导致重复选择（类似背包问题）。