Bit manipulation and memoized DFS


  • 0
    C

    Since number of each item is <= 6 and there are at most 6 kind of items, 3 * 6 = 18 bits should be enough.

    class Solution {
    public:
        const int INF = 1000000000;
        int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
            // 4MB memory
            vector<int> state(1 << 3 * price.size(), 1000000000); 
            state[0] = 0;
            vector<pair<int, int>> costs;
            int mask = 1;
            for (int i = 0; i < price.size(); i++) {
                state[mask] = price[i];
                costs.push_back({mask, price[i]});
                mask <<= 3;
            }
            for (int i = 0; i < special.size(); ++i) {
                int tmp = 0;
                int offset = 0;
                int total = 0;
                for (int j = 0; j < price.size(); ++j) {
                    tmp += (special[i][j] << offset);
                    total += price[j] * special[i][j];
                    offset += 3;
                }
                // Promos are not necessarily cheaper
                state[tmp] = min(special[i].back(), total);
                costs.push_back({tmp, special[i].back()});
            }
            int target = 0;
            int offset = 0;
            for (int i = 0; i < needs.size(); i++) {
                target += (needs[i] << offset);
                offset += 3;
            }
            return helper(costs, state, target);
        }
    private:
        int helper(vector<pair<int, int>>& costs, vector<int>& state, int target) {
            if (state[target] != 1000000000) {
                return state[target];
            }
            for (auto p: costs) {
                int s = p.first;
                bool valid = true;
                int cur = target;
                while (cur || s) {
                    if ((cur & 7) < (s & 7)) {
                        valid = false;
                        break;
                    }
                    cur >>= 3;
                    s >>= 3;
                }
                if (!valid)
                    continue;
                state[target] = min(state[target], helper(costs, state, target - p.first) + p.second);
            }
            return state[target];
        }
    };
    

Log in to reply
 

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