Description

你需要买n个商品，商品i需要的数目为needsi，单价为pricei。同时有m个打包优惠，每个优惠speciali均为一个长度n+1的数组，其中前n个元素对应商品i的数目，最后一个元素对应打包优惠价格。求最低买入价格。

Constraints

  • 1≤n≤6
  • 0≤pricei≤10
  • 0≤needsi≤10
  • 1≤m≤100
  • 0≤specialij≤50

Solution

每4个bit可表示一个商品数目的状态（24>10），因此状压DP维护dp[S]即可。

dp[]内的分布可能是稀疏的，因此使用哈希表来维护。

Code

class Solution {
public:
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        int S = 0;
        for(int i = 0, j = 0; i < needs.size(); j = ++i<<2) {
            S |= needs[i] << j;
        }
        unordered_map<int, int> dp;
        auto DP = [&](auto &&DP, int s) {
            if(dp.count(s)) return dp[s];
            int best = 0;
            for(int i = 0, j = 0; i < price.size(); j = ++i<<2) {
                int needi = s >> j & 0b1111;
                best += price[i] * needi;
            }

            for(const auto &sp : special) {
                int s2 = 0;
                bool overflow = false;
                for(int i = 0, j = 0; i < sp.size() - 1; j = ++i<<2) {
                    int needi = s >> j & 0b1111;
                    if(sp[i] > needi) {
                        overflow = true;
                        break;
                    }
                    s2 |= needi-sp[i] << j;
                }
                if(!overflow) {
                    best = min(best, sp.back() + DP(DP, s2));
                }
            }
            return dp[s] = best;
        };
        return DP(DP, S);
    }
};

LeetCode-638 Shopping Offers