|
| 1 | +# Time: O(n * 2^n) |
| 2 | +# Space: O(n) |
| 3 | + |
| 4 | +# In LeetCode Store, there are some kinds of items to sell. Each item has a price. |
| 5 | +# |
| 6 | +# However, there are some special offers, and a special offer consists of one or |
| 7 | +# more different kinds of items with a sale price. |
| 8 | +# |
| 9 | +# You are given the each item's price, a set of special offers, |
| 10 | +# and the number we need to buy for each item. The job is to output the lowest price you have to pay |
| 11 | +# for exactly certain items as given, where you could make optimal use of the special offers. |
| 12 | +# |
| 13 | +# Each special offer is represented in the form of an array, |
| 14 | +# the last number represents the price you need to pay for this special offer, |
| 15 | +# other numbers represents how many specific items you could get if you buy this offer. |
| 16 | +# |
| 17 | +# You could use any of special offers as many times as you want. |
| 18 | +# |
| 19 | +# Example 1: |
| 20 | +# Input: [2,5], [[3,0,5],[1,2,10]], [3,2] |
| 21 | +# Output: 14 |
| 22 | +# Explanation: |
| 23 | +# There are two kinds of items, A and B. Their prices are $2 and $5 respectively. |
| 24 | +# In special offer 1, you can pay $5 for 3A and 0B |
| 25 | +# In special offer 2, you can pay $10 for 1A and 2B. |
| 26 | +# You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A. |
| 27 | +# Example 2: |
| 28 | +# Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1] |
| 29 | +# Output: 11 |
| 30 | +# Explanation: |
| 31 | +# The price of A is $2, and $3 for B, $4 for C. |
| 32 | +# You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C. |
| 33 | +# 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. |
| 34 | +# You cannot add more items, though only $9 for 2A ,2B and 1C. |
| 35 | +# Note: |
| 36 | +# There are at most 6 kinds of items, 100 special offers. |
| 37 | +# For each item, you need to buy at most 6 of them. |
| 38 | +# You are not allowed to buy more items than you want, even if that would lower the overall price. |
| 39 | + |
| 40 | +class Solution(object): |
| 41 | + def shoppingOffers(self, price, special, needs): |
| 42 | + """ |
| 43 | + :type price: List[int] |
| 44 | + :type special: List[List[int]] |
| 45 | + :type needs: List[int] |
| 46 | + :rtype: int |
| 47 | + """ |
| 48 | + def shoppingOffersHelper(price, special, needs, i): |
| 49 | + if i == len(special): |
| 50 | + return sum(map(lambda x, y: x*y, price, needs)) |
| 51 | + result = shoppingOffersHelper(price, special, needs, i+1) |
| 52 | + for j in xrange(len(needs)): |
| 53 | + needs[j] -= special[i][j] |
| 54 | + if all(need >= 0 for need in needs): |
| 55 | + result = min(result, special[i][-1] + shoppingOffersHelper(price, special, needs, i)) |
| 56 | + for j in xrange(len(needs)): |
| 57 | + needs[j] += special[i][j] |
| 58 | + return result |
| 59 | + |
| 60 | + return shoppingOffersHelper(price, special, needs, 0) |
0 commit comments