#638

Shopping Offers

specialist · 880 · lc medium +31 · verified · 52.3% accepted · 1,627 likes · top 42%

Description

You want to purchase exactly needs[i] units of item i. Each item costs price[i], and there are bundle deals in special where special[i] lists quantities of each item and a discounted total price. Bundles may be used repeatedly, but you cannot purchase more of any item than needed. Return the minimum total cost to satisfy all your needs exactly.

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.

Code

1

2

3

class Solution:
    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:

class Solution:
    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int: