638. 大礼包 - 力扣（LeetCode）

题解

class Solution {
public:
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        int n = needs.size();
        int mask = 0;   // 状态压缩
        for (int i = 0; i < n; i++)
            mask |= needs[i] << (4 * i);
        unordered_map<int, int> f; // 记忆化搜索
        function<int(int)> dfs = [&](int cur) {
            if (f.contains(cur))
                return f[cur];
            int ans = 0;
            for (int i = 0; i < n; i++) 
                ans += price[i] * ((cur >> (i * 4)) & 0xf); // 先计算如果全部单独购买会花费多少钱
            for (const auto& s : special) { // 遍历每一个礼包
                int next = cur;
                bool ok = true;
                for (int i = 0; i < n; i++) {
                    if (((cur >> (i * 4)) & 0xf) < s[i]) { // 礼包中物品超出需求
                        ok = false;
                        break;
                    }
                    next -= s[i] << (i * 4);
                }
                if (ok) {
                    ans = min(ans, s[n] + dfs(next));   // 购买礼包没满足需求，继续往下搜索，记录最小的花费
                }
            }
            f[cur] = ans; 
            return ans;
        };
        return dfs(mask);
    }
};

思路

状态压缩 + 记忆化搜索

状态压缩：题目中说了一共有6种商品，每个商品需求最多10个，所以使用一个6*4bit的mask就可以保存需求清单（每4个bit保存每个商品的需求数量）。

记忆化搜索：定义了一个unordered_map来记住已经计算过最小花费的“需求清单”。

随后就是进行深度优先搜索：

• 首先假设所有商品都是单独购买（花费最大）
• 再遍历礼包，对于可以满足的（没有超出需求），就继续DFS剩下的“需求清单”（同时由记忆化搜索来剪枝）
• 保存最小的话费作为该“需求清单”的最终花费