Description

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

Constraints

  • \(1 \le n \le 6\)
  • \(0 \le price_i \le 10\)
  • \(0 \le needs_i \le 10\)
  • \(1 \le m \le 100\)
  • \(0 \le special_{ij} \le 50\)

Solution

每4个bit可表示一个商品数目的状态(\(2^4 \gt 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