LeetCode 题解工作台
大礼包
在 LeetCode 商店中， 有 n 件在售的物品。每件物品都有对应的价格。然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。 给你一个整数数组 price 表示物品价格，其中 price[i] 是第 i 件物品的价格。另有一个整数数组 needs 表示购物清单，其中 needs[i]…
6
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们注意到，题目中物品的种类 $n \leq 6$，而每种物品需要购买的数量不超过 ，我们可以用 个二进制位来表示每种物品需要购买的数量，这样，我们只需要最多 $6 \times 4 = 24$ 个二进制位来表示整个购物清单。 我们首先将购物清单 转换为一个整数 ，其中第 个物品需要购买的数量存储在 的第 $i \times 4$ 位到第 $(i + 1) \times 4 - 1$ 位。…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
在 LeetCode 商店中， 有 n 件在售的物品。每件物品都有对应的价格。然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。
给你一个整数数组 price 表示物品价格，其中 price[i] 是第 i 件物品的价格。另有一个整数数组 needs 表示购物清单，其中 needs[i] 是需要购买第 i 件物品的数量。
还有一个数组 special 表示大礼包，special[i] 的长度为 n + 1 ，其中 special[i][j] 表示第 i 个大礼包中内含第 j 件物品的数量，且 special[i][n] （也就是数组中的最后一个整数）为第 i 个大礼包的价格。
返回 确切 满足购物清单所需花费的最低价格，你可以充分利用大礼包的优惠活动。你不能购买超出购物清单指定数量的物品，即使那样会降低整体价格。任意大礼包可无限次购买。
示例 1：
输入：price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2] 输出：14 解释：有 A 和 B 两种物品，价格分别为 ¥2 和 ¥5 。 大礼包 1 ，你可以以 ¥5 的价格购买 3A 和 0B 。 大礼包 2 ，你可以以 ¥10 的价格购买 1A 和 2B 。 需要购买 3 个 A 和 2 个 B ， 所以付 ¥10 购买 1A 和 2B（大礼包 2），以及 ¥4 购买 2A 。
示例 2：
输入：price = [2,3,4], special = [[1,1,0,4],[2,2,1,9]], needs = [1,2,1] 输出：11 解释：A ，B ，C 的价格分别为 ¥2 ，¥3 ，¥4 。 可以用 ¥4 购买 1A 和 1B ，也可以用 ¥9 购买 2A ，2B 和 1C 。 需要买 1A ，2B 和 1C ，所以付 ¥4 买 1A 和 1B（大礼包 1），以及 ¥3 购买 1B ， ¥4 购买 1C 。 不可以购买超出待购清单的物品，尽管购买大礼包 2 更加便宜。
提示：
n == price.length == needs.length1 <= n <= 60 <= price[i], needs[i] <= 101 <= special.length <= 100special[i].length == n + 10 <= special[i][j] <= 50- 生成的输入对于
0 <= j <= n - 1至少有一个special[i][j]非零。
解题思路
方法一：状态压缩 + 记忆化搜索
我们注意到，题目中物品的种类 ，而每种物品需要购买的数量不超过 ，我们可以用 个二进制位来表示每种物品需要购买的数量，这样，我们只需要最多 个二进制位来表示整个购物清单。
我们首先将购物清单 转换为一个整数 ，其中第 个物品需要购买的数量存储在 的第 位到第 位。例如，当 时，有 。
然后，我们设计一个函数 ，表示当前购物清单的状态为 时，我们需要花费的最少金额。那么答案即为 。
函数 的计算方法如下：
- 我们首先计算当前购物清单 不使用大礼包时的花费，记为 。
- 然后，我们遍历每一个大礼包 ，如果当前购物清单 能够使用大礼包 ，即 中每种物品的数量都不小于大礼包 中的数量，那么我们可以尝试使用这个大礼包。我们将 中每种物品的数量减去大礼包 中的数量，得到一个新的购物清单 ，然后递归计算 的最少花费，并加上大礼包的价格 ，更新 ，即 。
- 最后，返回 。
为了避免重复计算，我们使用一个哈希表 记录每一个状态 对应的最少花费。
时间复杂度 ，其中 表示物品的种类，而 和 分别表示大礼包的数量以及每种物品的最大需求量。空间复杂度 。
class Solution:
def shoppingOffers(
self, price: List[int], special: List[List[int]], needs: List[int]
) -> int:
@cache
def dfs(cur: int) -> int:
ans = sum(p * (cur >> (i * bits) & 0xF) for i, p in enumerate(price))
for offer in special:
nxt = cur
for j in range(len(needs)):
if (cur >> (j * bits) & 0xF) < offer[j]:
break
nxt -= offer[j] << (j * bits)
else:
ans = min(ans, offer[-1] + dfs(nxt))
return ans
bits, mask = 4, 0
for i, need in enumerate(needs):
mask |= need << i * bits
return dfs(mask)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if the candidate can efficiently manage state transitions and handle large numbers of special offers.
- question_mark
Observe how well the candidate applies memoization to avoid redundant calculations.
- question_mark
Assess whether the candidate effectively handles the backtracking approach to explore possible combinations.
常见陷阱
外企场景- error
Forgetting to account for all possible states during the transition, which may lead to missed optimal solutions.
- error
Inefficient implementation of memoization, leading to excessive recomputation and slow performance.
- error
Failing to consider all combinations of offers, which can lead to suboptimal solutions.
进阶变体
外企场景- arrow_right_alt
How does the approach scale when the number of items increases beyond 6?
- arrow_right_alt
What if there were constraints limiting the number of times a single offer can be used?
- arrow_right_alt
Can this problem be solved using a greedy approach instead of dynamic programming?