393小F的超市购物策略

问题描述

小 F 需要在初始金额 x 内购物，每个商品有价格 a[i] 和喜爱度 b[i]。目标是在不超出预算的情况下获得最大化的喜爱度和。特殊之处在于：

• 初始没有优惠机会，只有在原价购买（支付 a[i]）后，才获得下一个商品半价购买（支付 a[i]//2）的优惠机会；
• 如果优惠机会未使用（状态 op 为 1），可以选择对当前商品使用优惠（半价购买），但使用后恢复普通状态（op 变为 0）；
• 跳过或使用优惠购买后，优惠机会均被重置为 0，即必须重新原价购买才能获得优惠资格。

解题思路

用 DFS + 记忆化（cache）来搜索所有可能的购买组合。
定义递归函数 dfs(i, j, op)：

• i：当前处理的商品下标
• j：剩余金额
• op：优惠状态（1 表示可以半价购买，0 表示无优惠机会）
  对于每个商品有三种选择：
• 跳过该商品：金额不变，且状态重置为 0
• 如果有优惠机会（op == 1）且剩余金额够商品半价，则可半价购买，金额减少 a[i]//2，购买后状态置为 0
• 如果剩余金额够以原价购买，则购买该商品，金额减少 a[i]，同时获得下一个商品使用优惠的机会，即状态变为 1
  最终返回达到末尾时获得的喜爱度总和的最大值。

实现代码

from functools import cache

def solution(n: int, x: int, a: list, b: list) -> int:
    @cache
    def dfs(i, j, op):
        if i == n:  # 所有商品处理完毕
            return 0
        # 不购买，且状态重置为 0
        res = dfs(i + 1, j, 0)
        # 若有优惠机会，尝试半价购买
        if op == 1 and j >= a[i] // 2:
            res = max(res, dfs(i + 1, j - a[i] // 2, 0) + b[i])
        # 尝试原价购买，并获得优惠机会
        if j >= a[i]:
            res = max(res, dfs(i + 1, j - a[i], 1) + b[i])
        return res

    return dfs(0, x, 0)

复杂度分析

时间复杂度：$O(n * x)$，其中 n 为商品数量，x 为初始金额。
空间复杂度：$O(n * x)$。