LC 638. 大礼包
题目描述
这是 LeetCode 上的 638. 大礼包 ,难度为 中等。
在 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:
1 |
|
示例 2:
1 |
|
提示:
- n == price.length
- n == needs.length
- 1 <= n <= 6
- 0 <= price[i] <= 10
- 0 <= needs[i] <= 10
- 1 <= special.length <= 100
- special[i].length == n + 1
- 0 <= special[i][j] <= 50
转换 DFS(转换为礼包处理)
对于某个 $need[i]$ 而言,既可以「单买」也可以使用「礼包形式购买」,同时两种购买方式都存在对「份数」的决策(单买多少份/买多少个相应的礼包)。
利用物品数量和礼包数量数据范围都较少,我们可以先对「单买」情况进行预处理,将其转换为「礼包」形式。若 $price[0] = 100$,则使用礼包 $[1, 0, 0, …,0, 100]$ 来代指。
然后再预处理每个礼包最多选多少个,并使用哈希表进行存储。
最后使用 DFS
对每个「礼包」如何选择进行爆搜即可。
代码:
1 |
|
- 时间复杂度:令物品数量为 $n$,原礼包数量为 $m$。将「单买」预处理成「礼包」,共有 $n$ 中「单买」情况需要转换,同时每个转换需要对数组进行复制,复杂度为 $O(n^2)$,预处理完后,共有 $n + m$ 个礼包;预处理每个礼包所能选的最大数量,复杂度为 $O((n m) n)$;对礼包的选择方案进行决策,一个礼包最多选择 $k = \max(needs[i]) = 10$ 个,复杂度为 $O(k ^ {n + m})$
- 空间复杂度:$O(k ^ {n + m})$
完全背包
这还是一道很有意思的「完全背包」问题。
不了解「完全背包」的同学,可以先看前置🧀:完全背包。目前「背包问题」专题 已经讲了 $21$ 篇,大概还有 $2$ - $4$ 篇彻底讲完,完全覆盖了所有的「背包问题」。
背包问题难点在于对「成本」和「价值」的抽象。
对于本题,我们可以定义 $f[i, j0, j_1, j_2, … , j{n - 1}]$ 为考虑前 $i$ 个大礼包,购买 $j0$ 件物品 $0$,购买 $j_1$ 件物品 $1$,….,购买 $j{n - 1}$ 件物品 $n - 1$ 时的最小花费。
同时,我们有初始化条件 $f[0, 0, 0, … , 0] = 0$(其余 $f[0, x_0, x_1, x_2, …, x_n]$ 为正无穷)的初始化条件,最终答案为 $f[m - 1, need[0], need[1], …, need[n - 1]]$。
这样的朴素完全背包做法复杂度过高,根据我们的前置🧀 完全背包 中的数学推导分析,我们发现完全背包的一维空间优化,是具有优化复杂度的意义。
因此,我们可以对礼包维度进行优化,使用 $f[need[0], need[1], … , need[n - 1]]$ 来作为状态表示。
不失一般性的考虑 $f[j0, j_1, … , j{n - 1}]$ 该如何转移(以物品 $0$ 为例进行分析,其他同理):
- 不选择任何大礼包,只进行单买:$f[j0, j_1, … , j{n - 1}] = min(f[j0, j_1, … , j{n - 1}], f[j0 - 1, j_1, …, j{n - 1}] + price[0]$;
- 购买大礼包:$f[j0, j_1, … , j{n - 1}] = min(f[j0, j_1, … , j{n - 1}], f[j0 - special[i][0], j_1 - special[i][1],, …, j{n - 1} - special[i][n - 1]] + special[i][n]$
最终的 $f[j0, j_1, … , j{n - 1}]$ 为上述所有方案中的最小值。
一些细节:实现时,为了防止过多的维度,以及可能存在的 MLE 风险,我们可以对维度进行压缩处理,而最简单的方式可以通过与排列数建立映射关系。
代码:
1 |
|
- 时间复杂度:令物品数量为 $n$,原礼包数量为 $m$。每个物品最多需要 $k = \max(needs[i]) = 10$ 个,共有 $k^n$ 个状态需要转移,转移时需要考虑「单买」和「礼包」决策,复杂度分别为 $O(n)$ 和 $O(m n)$。整体复杂度为 $O(k^n (m * n))$
- 空间复杂度:$O(k^n (m n))$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.638
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!