0638. Shopping Offers

题目信息

题号:

0638

难度:

Medium

主题:

多种商品、单价、礼包、精确购买需求

原题:

LeetCode 0638

重点:

每种商品需买到恰好 needs 指定数量、礼包可以重复使用、不能购买超过需求的商品、剩余商品可按单价购买

题目重述

有 n 种商品,price[i] 是第 i 种商品的单件价格,needs[i] 是需要购买的数量。每个礼包 special[j] 的前 n 项表示其中各商品数量,最后一项表示礼包总价。

可以按单价购买商品,也可以使用任意礼包任意多次;但最终每种商品的总购买数量必须恰好等于 needs,不能为了降低价格而购买多余商品。返回满足全部需求的最低总费用。商品种类数位于 [1, 6],单价和需求量位于 [0, 10],礼包数量不超过 100。

自建示例

礼包与单买组合最便宜:

输入:price = [3,5],special = [[1,1,6],[2,0,5]],needs = [2,1]
输出:9
解释:购买一次 [1,1,6] 礼包,再单买一件第一种商品,总价 6+3=9;其他合法买法都不更便宜。

需求全部为零:

输入:price = [4,7],special = [[1,1,8]],needs = [0,0]
输出:0
解释:已经满足精确需求,购买任何单品或礼包都会产生多余商品,因此最低费用为 0。