0638. Shopping Offers ===================== 题目信息 -------- :题号: 0638 :难度: Medium :主题: 多种商品、单价、礼包、精确购买需求 :原题: `LeetCode 0638 `_ :重点: 每种商品需买到恰好 needs 指定数量、礼包可以重复使用、不能购买超过需求的商品、剩余商品可按单价购买 题目重述 -------- 有 ``n`` 种商品,``price[i]`` 是第 ``i`` 种商品的单件价格,``needs[i]`` 是需要购买的数量。每个礼包 ``special[j]`` 的前 ``n`` 项表示其中各商品数量,最后一项表示礼包总价。 可以按单价购买商品,也可以使用任意礼包任意多次;但最终每种商品的总购买数量必须恰好等于 ``needs``,不能为了降低价格而购买多余商品。返回满足全部需求的最低总费用。商品种类数位于 ``[1, 6]``,单价和需求量位于 ``[0, 10]``,礼包数量不超过 ``100``。 自建示例 -------- 礼包与单买组合最便宜: .. code-block:: text 输入:price = [3,5],special = [[1,1,6],[2,0,5]],needs = [2,1] 输出:9 解释:购买一次 [1,1,6] 礼包,再单买一件第一种商品,总价 6+3=9;其他合法买法都不更便宜。 需求全部为零: .. code-block:: text 输入:price = [4,7],special = [[1,1,8]],needs = [0,0] 输出:0 解释:已经满足精确需求,购买任何单品或礼包都会产生多余商品,因此最低费用为 0。