638.大礼包

https://leetcode-cn.com/problems/shopping-offers/

一：dfs回溯

用dfs(needs, price)递归，needs为需要的商品，price为目前得出的价格。当needs全部元素为0时递归返回，并用当前price更新最低价。每次递归买入[0...n-1]号礼包（总数为n），并计算判断能否买包，不能买包则剩余的needs全部单买。

最后dfs结束还要与一个包都不买的情况作比较，因为进了dfs至少会买一个包

class Solution:
    def shoppingOffers(self, prices, special, needs) -> int:
        self.res = sys.maxsize	#全局变量记录最低总价
        n = len(special)
        m = len(needs)
        def dfs(needs, price):
            #递归出口
            if sum(needs) == 0:
                self.res = min(self.res, price)
                return
            #回溯法买包
            for i in range(n):
                tmp = list(needs)
                bag = True
                for j in range(m):
                    if tmp[j] - special[i][j] >= 0:
                        tmp[j] = tmp[j] - special[i][j]
                    else:
                        bag = False #有一种物品已满，不能再买包了
                        break
                if bag: #买包
                    dfs(tmp, price + special[i][-1])    #买第i个包
                else:   #单买
                    tmp_price = price
                    # 所有没满的商品全部单买
                    for j in range(m):
                        tmp_price += needs[j] * prices[j]
                    dfs([0]*m, tmp_price)
        dfs(needs, 0)
        # 一个包都不买
        price = 0
        for j in range(m):
            price += needs[j] * prices[j]
        return min(self.res, price)