638.Shopping Offers

发表于 | 分类于

题目详见：https://leetcode.com/problems/shopping-offers/

思路：递归+回溯。以必须购买的物品及其数量为目标，每次递归时，有两种情况：一为达到目标的最大花费即所有物品按原价购买，将该花费作为上限；二是购买special offers，花费为special offers的price+购买剩余物品的最少花费，此时，要考虑买到的物品是否符合要求，买到的物品数量不得超出目标数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        int minpay=0;
        for(int i=0;i<needs.size();i++){
            minpay+=price[i]*needs[i];
        }
        for(auto s:special){
            bool can=true;
            for(int i=0;i<needs.size();i++){
                if(needs[i]<s[i]){
                    can=false;
                    break;
                }
            }
            if(can){
                for(int i=0;i<needs.size();i++)
                    needs[i]-=s[i];
                minpay=min(minpay,s[needs.size()]+shoppingOffers(price,special,needs));
                for(int i=0;i<needs.size();i++)
                    needs[i]+=s[i];
            }
        }
        return minpay;
    }
};