C++ DFS AC solution


  • 0
    F
        int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        int n = price.size();
        
        int num_offer = special.size();
        
        int ans = 0;
        for(int i = 0 ; i < n; i++){
            ans += needs[i] * price[i];
        }
        search(price, special, needs, 0, num_offer, ans, 0);
        return ans;            
    }
    
    void search(vector<int>& price, vector<vector<int>> & special, vector<int>& needs, int idx, int n, int& ans, int pre){
        int maxi_num = numeric_limits<int>::max();
        if(idx >= special.size()) return;
        for(int i = 0; i < needs.size(); i++){ // maxi_num is maximum number of idx_th offer we can use
            if(special[idx][i] == 0) continue;
            maxi_num = min(maxi_num, needs[i] / special[idx][i]);
        }
        
        search(price, special, needs, idx + 1, n, ans, pre); // do not use offer idx;
        
        for(int i = 1; i <= maxi_num; i++){
            vector<int> need = needs;
            int cur = special[idx].back() * i + pre;
            int current = cur;
            for(int j = 0; j < need.size(); j++){ // use i offers
                need[j] -= special[idx][j] * i;
                cur += need[j] * price[j];
            }
            search(price, special, need, idx + 1, n, ans, current);
            
            ans = min(ans, cur);
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.