website/content.en/ChapterFour/0600~0699/0638.Shopping-Offers.md
In LeetCode Store, there are some kinds of items to sell. Each item has a price.
However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.
You are given the each item's price, a set of special offers, and the number we need to buy for each item. The job is to output the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers.
Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer.
You could use any of special offers as many times as you want.
Example 1:
Input: [2,5], [[3,0,5],[1,2,10]], [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: [2,3,4], [[1,1,0,4],[2,2,1,9]], [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.
Note:
In the LeetCode store， there are many items for sale。However， there are also some special offers， each special offer bundles a group of items at a discounted price。
Now given the price of each item， the list of items contained in each special offer， and the shopping list of items to buy。Please output the minimum cost to exactly complete the shopping list。Each special offer is described by a set of data in an array， the last number represents the price of the special offer， and the other numbers respectively indicate the quantities of the other types of items included。Any special offer can be purchased an unlimited number of times。
Example 1:
Input: [2,5], [[3,0,5],[1,2,10]], [3,2]
Output: 14
Explanation:
There are two types of items， A and B， with prices of ¥2 and ¥5 respectively。
Special offer 1， you can buy 3A and 0B for ¥5。
Special offer 2， you can buy 1A and 2B for ¥10。
You need to buy 3 A and 2 B， so you paid ¥10 to buy 1A and 2B（special offer 2）， and ¥4 to buy 2A。
Example 2:
Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
Output: 11
Explanation:
The prices of A，B，C are ¥2，¥3，¥4 respectively.
You can buy 1A and 1B for ¥4， or buy 2A，2B and 1C for ¥9。
You need to buy 1A，2B and 1C， so you paid ¥4 to buy 1A and 1B（special offer 1）， plus ¥3 to buy 1B， ¥4 to buy 1C。
You cannot buy items beyond the shopping list， even though buying special offer 2 is cheaper。
Note:
shopping(price, special, needs)， where price and special are the unit prices of the items and the bundled special offers described in the problem， and needs is the current required quantity of each type of item。For each item， there can be 3 purchase rules， first， choose the first discount in the special offers to buy， second， do not choose the current special offer discount， choose the next discount to buy， third， do not use discounts， buy directly。This corresponds to the 3 DFS directions。See the code for details。If a special offer discount is chosen， then recurse to the next level， need needs to correspondingly subtract the quantities in the special offer， and the final amount is accumulated。After all cases have been traversed， the minimum cost can be returned。need and price conditions， whether the special offer can be used。This includes 2 cases， one is that the current item has already met the number on the list， so there is no need to buy more； another case is that it has already exceeded the list quantity， then this case needs to return immediately， the current purchase method does not meet the problem requirements。func shoppingOffers(price []int, special [][]int, needs []int) int {
res := -1
dfsShoppingOffers(price, special, needs, 0, &res)
return res
}
func dfsShoppingOffers(price []int, special [][]int, needs []int, pay int, res *int) {
noNeeds := true
// Pruning
for _, need := range needs {
if need < 0 {
return
}
if need != 0 {
noNeeds = false
}
}
if len(special) == 0 || noNeeds {
for i, p := range price {
pay += (p * needs[i])
}
if pay < *res || *res == -1 {
*res = pay
}
return
}
newNeeds := make([]int, len(needs))
copy(newNeeds, needs)
for i, n := range newNeeds {
newNeeds[i] = n - special[0][i]
}
dfsShoppingOffers(price, special, newNeeds, pay+special[0][len(price)], res)
dfsShoppingOffers(price, special[1:], newNeeds, pay+special[0][len(price)], res)
dfsShoppingOffers(price, special[1:], needs, pay, res)
}