原文链接: https://leetcode-cn.com/problems/shopping-offers

英文原文

In LeetCode Store, there are n items to sell. Each item has a price. However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.

You are given an integer array price where price[i] is the price of the ith item, and an integer array needs where needs[i] is the number of pieces of the ith item you want to buy.

You are also given an array special where special[i] is of size n + 1 where special[i][j] is the number of pieces of the jth item in the ith offer and special[i][n] (i.e., the last integer in the array) is the price of the ith offer.

Return the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers. You are not allowed to buy more items than you want, even if that would lower the overall price. You could use any of the special offers as many times as you want.

 

Example 1:

Input: price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2]
Output: 14
Explanation: There are two kinds of items, A and B. Their prices are $2 and $5 respectively. 
In special offer 1, you can pay $5 for 3A and 0B
In special offer 2, you can pay $10 for 1A and 2B. 
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.

Example 2:

Input: price = [2,3,4], special = [[1,1,0,4],[2,2,1,9]], needs = [1,2,1]
Output: 11
Explanation: The price of A is $2, and $3 for B, $4 for C. 
You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C. 
You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer #1), and $3 for 1B, $4 for 1C. 
You cannot add more items, though only $9 for 2A ,2B and 1C.

 

Constraints:

• 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

中文题目

在 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

通过代码

高赞题解

写在前面

emmmm 祝大家 $1024$ 节日快乐 🤣

---

转换 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 k = 0;
            for (int j = 0; j < n; j++) {
                int a = x.get(j), b = needs.get(j);
                if (a == 0 || b == 0) continue;
                if (a > b) {
                    k = 0;
                    break;
                }
                k = k == 0 ? b / a : Math.min(k, b / a);
            }
            map.put(i, k);
        }
        dfs(0, needs, 0);
        return ans;
    }
    void dfs(int u, List<Integer> list, int cur) {
        if (cur >= ans) return ;
        int cnt = 0;
        for (int i = 0; i < n; i++) cnt += list.get(i);
        if (cnt == 0) {
            ans = cur;
            return ;
        }
        if (u == m) 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} + (n + m) * n)$
• 空间复杂度：$O(k ^ {n + m})$

---

完全背包

这还是一道很有意思的「完全背包」问题。

不了解「完全背包」的同学，可以先看前置🧀：完全背包。目前「背包问题」专题 已经讲了 $21$ 篇，大概还有 $2$ - $4$ 篇彻底讲完，完全覆盖了所有的「背包问题」。

背包问题难点在于对「成本」和「价值」的抽象。

对于本题，我们可以定义 $f[i, j_0, j_1, j_2, … , j_{n - 1}]$ 为考虑前 $i$ 个大礼包，购买 $j_0$ 件物品 $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[j_0, j_1, … , j_{n - 1}]$ 该如何转移（以物品 $0$ 为例进行分析，其他同理）：

1. 不选择任何大礼包，只进行单买：$f[j_0, j_1, … , j_{n - 1}] = min(f[j_0, j_1, … , j_{n - 1}], f[j_0 - 1, j_1, …, j_{n - 1}] + price[0]$；
2. 购买大礼包：$f[j_0, j_1, … , j_{n - 1}] = min(f[j_0, j_1, … , j_{n - 1}], f[j_0 - special[i][0], j_1 - special[i][1],, …, j_{n - 1} - special[i][n - 1]] + special[i][n]$

最终的 $f[j_0, 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))$

---

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

统计信息

通过次数	提交次数	AC比率
28358	43927	64.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言