638. Shopping Offers #

Problem #

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:

There are at most 6 kinds of items, 100 special offers.
For each item, you need to buy at most 6 of them.
You are not allowed to buy more items than you want, even if that would lower the overall price.

Problem Summary #

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:

At most 6 types of items， 100 special offers。
For each type of item， you need to buy at most 6。
You cannot buy items beyond the shopping list， even if it is cheaper。

Solution Approach #

Given 3 arrays， the meanings represented by the 3 arrays are the prices of the items for sale， multiple special offers and the quantity of each item in the special offer and the total price， and the quantity of each item that needs to be purchased on the shopping list。Ask for the minimum cost required to buy all items on the shopping list。
This problem can be solved by brute force with DFS， or with DP。The author first uses DFS to answer this problem。Let the current searched state be 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。
The pruning case that needs attention in this problem： whether it is necessary to buy a special offer。The problem requires that items exceeding the quantity on the list cannot be purchased， even if the price is cheap， it is not allowed。For example， you can buy n special offers A， but the final item quantity exceeds the items on the list， this purchase method is not allowed。So it is necessary to first judge in the current recursion， for those satisfying the 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。

Code #

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)
}