JAVA程式設計：大禮包（LeetCode：638）

在LeetCode商店中， 有許多在售的物品。

然而，也有一些大禮包，每個大禮包以優惠的價格捆綁銷售一組物品。

現給定每個物品的價格，每個大禮包包含物品的清單，以及待購物品清單。請輸出确切完成待購清單的最低花費。

每個大禮包的由一個數組中的一組資料描述，最後一個數字代表大禮包的價格，其他數字分别表示内含的其他種類物品的數量。

任意大禮包可無限次購買。

示例 1:

輸入: [2,5], [[3,0,5],[1,2,10]], [3,2]

輸出: 14

解釋: 

有A和B兩種物品，價格分别為¥2和¥5。

大禮包1，你可以以¥5的價格購買3A和0B。

大禮包2， 你可以以¥10的價格購買1A和2B。

你需要購買3個A和2個B， 是以你付了¥10購買了1A和2B（大禮包2），以及¥4購買2A。

示例 2:

輸入: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]

輸出: 11

A，B，C的價格分别為¥2，¥3，¥4.

你可以用¥4購買1A和1B，也可以用¥9購買2A，2B和1C。

你需要買1A，2B和1C，是以你付了¥4買了1A和1B（大禮包1），以及¥3購買1B， ¥4購買1C。

你不可以購買超出待購清單的物品，盡管購買大禮包2更加便宜。

說明:

最多6種物品， 100種大禮包。

每種物品，你最多隻需要購買6個。

你不可以購買超出待購清單的物品，即使更便宜。

思路：

方法一：回溯。設目前搜尋到的狀态為 shopping(price, special, needs)，其中 price 和 special 為題目中所述的物品的單價和捆綁銷售的大禮包，而 needs 為目前需要的每種物品的數量。對于此時的 needs，我們可以考慮全部使用原價購買，總價即為 price 與 needs 對應位置相乘的結果；我們也可以使用大禮包，對于 special 中的某一個大禮包 s，如果 s 中的每種物品數量都不大于 needs 中對應物品數量，那麼我們就可以使用這個大禮包 s。這樣我們會遞歸地搜尋狀态 shopping(price, special, needs')，其中 needs' = needs - s，表示更新過的每種物品的數量。在狀态 shopping(price, special, needs) 搜尋完畢後，會傳回其最小花費。

方法二：記憶化搜尋。我們可以發現，對于搜尋狀态 shopping(price, special, needs)，無論它是從哪個前置狀态遞歸得來的，隻要 needs 的值相同（price 和 special 在遞歸時是不會變的，我們将其放入搜尋狀态僅僅是為了友善使用這些變量），那麼傳回的最小花費也相同。是以我們可以使用一個哈希映射（HashMap）存儲每個 needs 對應的最小花費，當我們遞歸進入一個搜尋狀态時，如果該狀态中的 needs 沒有出現過，那麼我們進行搜尋，并在搜尋結束時将結果存入哈希映射；如果該狀态中的 needs 出現過，那麼我們就省去了搜尋，直接傳回哈希映射中對應的最小花費即可。