LeetCode 638. 大禮包

在LeetCode商店中， 有許多在售的物品踩窖。
然而，也有一些大禮包晨横，每個大禮包以優(yōu)惠的價格捆綁銷售一組物品洋腮。
現(xiàn)給定每個物品的價格，每個大禮包包含物品的清單手形，以及待購物品清單啥供。請輸出確切完成待購清單的最低花費。
每個大禮包的由一個數(shù)組中的一組數(shù)據(jù)描述库糠，最后一個數(shù)字代表大禮包的價格伙狐，其他數(shù)字分別表示內(nèi)含的其他種類物品的數(shù)量。
任意大禮包可無限次購買瞬欧。

示例 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和2B，也可以用￥9購買2A肿孵，2B和1C唠粥。
你需要買1A，2B和1C停做，所以你付了￥4買了1A和1B（大禮包1）晤愧，以及￥3購買1B， ￥4購買1C蛉腌。
你不可以購買超出待購清單的物品官份，盡管購買大禮包2更加便宜。

說明:

1. 最多6種物品烙丛， 100種大禮包舅巷。
2. 每種物品，你最多只需要購買6個河咽。
3. 你不可以購買超出待購清單的物品钠右，即使更便宜。

我的答案：

class Solution {
public:
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        int cost = 0;
        int buy = 1;
        int minCost = 0;
        for(int i=0; i<needs.size(); i++){
            minCost += (price[i]*needs[i]);
        }
        for(int i=0; i<special.size(); i++){
            buy = 1; //記得初始化忘蟹！
            for(int j=0; j<price.size(); j++){
                if(special[i][j] > needs[j]){
                    buy = 0;
                    break;
                }
            }
            if(buy == 1){
                vector<int> temp_needs;
                for(int j=0; j<price.size(); j++){
                    temp_needs.push_back(needs[j] - special[i][j]);
                }
                cost = special[i][special[i].size()-1] + shoppingOffers(price, special, temp_needs);
                minCost = min(minCost, cost);//cost>minCost飒房，說明不應(yīng)該購買這個禮包，帶本禮包的購買路徑不被記錄
            }
        }
        return minCost;
    }
};