638. Shopping Offers

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:

1. There are at most 6 kinds of items, 100 special offers.

2. For each item, you need to buy at most 6 of them.

3. You are not allowed to buy more items than you want, even if that would lower the overall price.

把需求量和各自的價額直接相乘內積就是所有品項直接透過單一零售價購買的價格，這是一個比較的baseline，因為有可能special offer反而比直接單一購買來得貴。利用DFS backtracking，如果一組offer的總金額小於baseline，那麼就可以參考拿來使用，needs先減去這組offer能買到的數量，再繼續DFS下去。DFS會得到一個金額加上當前這個offer的價格可以和當前的cost比較。每個offer比完之後再把減去得數量加上needs，因為還要變為原來的數量拿去給下一個offer操作比較。

bool operator> (const vector<int>& a, const vector<int>& b) {
    for (int i = 0; i < a.size(); ++i) {
        if (a[i] < b[i]) return false;
    }
    return true;
}
void operator+= (vector<int>& a, const vector<int>& b) {
    for (int i = 0; i < a.size(); ++i) {
        a[i] += b[i];
    }
}
void operator-= (vector<int>& a, const vector<int>& b) {
    for (int i = 0; i < a.size(); ++i) {
        a[i] -= b[i];
    }
}
// Top-Down DFS Backtracking with self-defined operators
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
    int cost = inner_product(needs.begin(), needs.end(), price.begin(), 0);
    for (vector<int>& spe : special) {
        if (spe.back() > cost) continue;
        if (needs > spe) {
            needs -= spe;
            cost = min(cost, spe.back() + shoppingOffers(price, special, needs));
            needs += spe;
        }
    }
    return cost;
}

這個方法用了2個optimization，一個是利用hashmap做到memoization避免重複計算，但C++ unodered_map的key不能是vector<int>，所以我把needs serialize成string變成一個string key。另一個是用pos紀錄現在在使用哪一個special offer，避免回頭重複計算先前已經用完的offer，當然offer可以重複使用，所以每個helper DFS在parse parameters時，用的是當前的i而不是i + 1。

bool isValid(const vector<int>& offer, const vector<int>& needs) {
    for (int i = 0; i < needs.size(); ++i) {
        if (offer[i] > needs[i]) return false;
    }
    return true;
}
void useOffer(const vector<int>& offer, vector<int>& needs) {
    for (int i = 0; i < needs.size(); ++i) {
        needs[i] -= offer[i];
    }
}
void unuseOffer(const vector<int>& offer, vector<int>& needs) {
    for (int i = 0; i < needs.size(); ++i) {
        needs[i] += offer[i];
    }
}
string mapKey(const vector<int>& vec) {
    string res;
    int n = vec.size();
    for (int i = 0; i < n; ++i) {
        res += to_string(vec[i]) + ((i != n - 1) ? "_" : "");
    }
    return res;
}
int helper(vector<int>& price, vector<vector<int>>& special, vector<int>& needs, int pos, unordered_map<string, int>& memo) {
    if (price.size() == 0 || needs.size() == 0) return 0;
    string strKey = mapKey(needs);
    if (memo.count(strKey)) return memo[strKey];
    int res = inner_product(needs.begin(), needs.end(), price.begin(), 0);
    for (int i = pos; i < special.size(); ++i) {
        if (!isValid(special[i], needs)) continue;
        useOffer(special[i], needs);
        res = min(res, special[i].back() + helper(price, special, needs, i, memo));
        unuseOffer(special[i], needs);
    }
    memo[strKey] = res;
    return res;
}
// Top-Down DP with Memoization
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
    unordered_map<string, int> memo;
    return helper(price, special, needs, 0, memo);
}