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：

输入：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
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 对每个「礼包」如何选择进行爆搜即可。

代码：

class Solution {
    int ans = 0x3f3f3f3f;
    List<Integer> price, needs;
    List<List<Integer>> special;
    Map<Integer, Integer> map = new HashMap<>();
    int n, m;
    public int shoppingOffers(List<Integer> _price, List<List<Integer>> _special, List<Integer> _needs) {
        price = _price; special = _special; needs = _needs;
        n = price.size();
        List<Integer> temp = new ArrayList<>();
        for (int i = 0; i < n; i++) temp.add(0);
        for (int i = 0; i < n; i++) {
            List<Integer> clone = new ArrayList<>(temp);
            clone.set(i, 1);
            clone.add(price.get(i));
            special.add(clone);
        }
        m = special.size();
        for (int i = 0; i < m; i++) {
            List<Integer> x = special.get(i);
            int max = 0;
            for (int j = 0; j < n; j++) {
                int a = x.get(j), b = needs.get(j);
                if (a == 0 || b == 0) continue;
                max = Math.max(max, (int)Math.ceil(b / a));
            }
            map.put(i, max);
        }
        dfs(0, needs, 0);
        return ans;
    }
    void dfs(int u, List<Integer> list, int cur) {
        if (cur >= ans) return ;
        if (u == m) {
            for (int i = 0; i < n; i++) {
                if (list.get(i) != 0) return ;
            }
            ans = Math.min(ans, cur);
            return ;
        }
        List<Integer> x = special.get(u);
        out:for (int k = 0; k <= map.get(u); k++) {
            List<Integer> clist = new ArrayList<>(list);
            for (int i = 0; i < n; i++) {
                int a = x.get(i), b = clist.get(i);
                if (a * k > b) break out;
                clist.set(i, b - a * k);
            }
            dfs(u + 1, clist, cur + k * x.get(n));
        }
    }
}

时间复杂度：令物品数量为 $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 风险，我们可以对维度进行压缩处理，而最简单的方式可以通过与排列数建立映射关系。

代码：

class Solution {
    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        int n = price.size();
        int[] g = new int[n + 1];
        g[0] = 1;
        for (int i = 1; i <= n; i++) {
            g[i] = g[i - 1] * (needs.get(i - 1) + 1);
        }
        int mask = g[n];
        int[] f = new int[mask];
        int[] cnt = new int[n];
        for (int state = 1; state < mask; state++) {
            f[state] = 0x3f3f3f3f;
            Arrays.fill(cnt, 0);
            for (int i = 0; i < n; i++) {
                cnt[i] = state % g[i + 1] / g[i];
            }
            for (int i = 0; i < n; i++) {
                if (cnt[i] > 0) f[state] = Math.min(f[state], f[state - g[i]] + price.get(i));
            }
            out:for (List<Integer> x : special) {
                int cur = state;
                for (int i = 0; i < n; i++) {
                    if (cnt[i] < x.get(i)) continue out;
                    cur -= x.get(i) * g[i];
                }
                f[state] = Math.min(f[state], f[cur] + x.get(n));
            }
        }
        return f[mask - 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 原题链接和其他优选题解。

DFS 背包问题完全背包

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 240. 搜索二维矩阵 II 上一篇

LC 492. 构造矩形下一篇