638 大礼包（记忆化搜索、初始化技巧）

小灰灰 2022-09-02 04:29 151阅读 0赞

**1. 问题描述：**

在 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  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/shopping-offers

**2. 思路分析：**

① 分析题目可以知道这道题目的本质是**多维的完全背包**问题（n最大是6所以为6维完全背包问题），一维完全背包问题是当前有n个物品，我们需要在不超过当前背包容量v的前提下求解能够获得的最大价值，这道题目其实是有t个背包，其中t为len(need)，也即need数组的长度，我们需要求解的是恰好装满每一个背包花费的最少金额。直接使用传统的完全背包的思路可以发现时间复杂度是很高的，因为need数组元素最大为10，最大的长度为6，而且special长度最大为100，所以我们枚举的special的时候时间复杂度为10 \*\* 6 \* 100 = 10 \*\* 8所以很可能会超时。为了避免时间复杂度太高我们可以使用**记忆化搜索**来解决，记忆化搜索可以避免某些状态的重复求解，这样当我们我们发现之前已经求解过当前的状态之后就直接return，而不是继续递归往下求解了。记忆化搜索一般需要借助于一个数据结构来存储递归求解过的状态值，一般使用数组来记录求解过这些状态值（通过这个数组的值来判断之前是否求解过），所以首先我们需要声明一个数组，怎么样确定数组的维度呢？可以发现我们在递归求解的过程中有两个动态变化的参数，第一个是当前递归的special的位置，第二个是选择当前的多个special\[i\]之后或者是不选当前的special\[i\]之后对应的need数组对应的状态，我们需要根据这两个动态变化的参数来声明对应维度的数组，对于第一个参数其实很好处理，主要是第二个参数，因为need是一个数组，数组中的所有元素对应着一个状态，为了方便处理我们需要将need数组中的每一个数字映射为一个十进制数字这样在递归的时候才方便处理，因为need数组中最大为10，所以我们可以将need数组中的每一个元素映射为16进制的数字，need中每一个数字对应着一个4位的二进制这样可以将need数组中的所有数字映射为一个可以看成是16进制的十进制数字，这样我们在处理的时候通过每四位二进制就可以知道原来的need数组中对应的数值是什么。最终我们就可以声明二维dp数组来存储递归过程中之前求解过的状态。由于第二维得长度是远远大于第一维的，第一维长度为len(special) + 1，第二维的长度为1 << n \* 4 （n个数字每一个数字需要4位所以总共需要1 << n \* 4个二进制位），n为need数组的长度，因为使用的是python语言所以如果直接这样初始化二维列表会超时（第二维的状态超级大不能直接初始化），这里可以使用到一个技巧是将第二维声明为一个字典，当我们需要使用到第二维的某个状态的时候才初始化对应的值这样可以大大减少初始化二维列表的时间。

② 确定好了记忆化数组之后那么接下来就是递归求解了，对于当前的special\[i\]，我们可以选择不买，可以选择买多个，分别对应这两种状态进行递归求解即可，如果我们选择买当前的物品那么在当前的状态对应的数字中需要减去对应的物品数，并且我们在选择买的时候需要注意当前买的物品数不能够超过需要的物品数目，否则这种状态是不合法的，只有合法的前提下我们才选择买，最终对于当前的物品买还是不买选择金额最小即可。

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        def dfs(self, prices: List[int], special: List[List[int]], dp: List[dict], x: int, y: int):
            if y in dp[x]: return dp[x][y]
            if x == 0:
                # 当前没有礼包可以买了只能够零散买剩余的需要的数目
                dp[x][y] = 0
                for i in range(len(prices)):
                    # 获取当前第i个状态对应的数值, 也即need数组中的第i个数
                    c = y >> i * 4 & 15
                    dp[x][y] += c * prices[i]
                return dp[x][y]
            # 不选择当前的物品, 所以递归的下一个x状态为x - 1
            dp[x][y] = self.dfs(prices, special, dp, x - 1, y)
            state = 0
            s = special[x - 1]
            for i in range(len(prices) - 1, -1, -1):
                c = y >> i * 4 & 15
                if c < s[i]:
                    state = -1
                    break
                # 减去相应拿取的物品数
                state = state * 16 + c - s[i]
            if state != -1:
                # 拿取当前的第special[i]的物品, 因为可以拿当前的物品无限次的所以递归的下一个位置还是x
                dp[x][y] = min(dp[x][y], self.dfs(prices, special, dp, x, state) + s[-1])
            # 返回
            return dp[x][y]
    
        def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
            n = len(price)
            # 下面相当于也是一个二维列表, 并且由于第二维是字典所以初始化的速度是很快的
            dp = [dict() for i in range(len(special) + 1)]
            # 初始化状态
            state = 0
            # 逆序遍历need, 将need数组中的每一个数字映射为4位的二进制值, 所以每一次需要乘以16也即左移4位
            for i in range(n - 1, -1, -1):
                state = state * 16 + needs[i]
            return self.dfs(price, special, dp, len(special), state)