大礼包 图解题解

大礼包这道题，买齐清单最少花多少钱

每件商品有原价，另有几种大礼包，每个礼包打包几件给一个打包价，可无限次买。清单 needs 写明每件要买几个，求买齐的最低花费，且每件买到手都不能超过清单。price=[2,5]、礼包 [3 个 A 价 5] 和 [1 个 A 加 2 个 B 价 10]、needs=[3,2]，原价单买 16，巧用礼包压到 14。

为什么贪心挑最便宜的礼包会算错

贪心最顺手，每步挑当下最划算的礼包，但会挑反：某礼包眼下最省，买下去却让剩下凑不成别的组合，反倒更贵。想稳妥就把所有买法试一遍，一路分叉；可礼包一多、清单一长买法就成倍翻、试不完，更糟的是同一个『还差多少没买』的局面会被反复重算。

状态设成『还差多少没买』，答案怎么拆

不纠结先买哪个后买哪个，只盯一件事：现在还差多少没买，写成一个还需向量，还要 3 个 A、2 个 B 就记成 [3,2]。任何买法走到某步，只要剩下还需相同，后面怎么买最省就一样，和之前买过什么、什么顺序都无关。

定义 dfs(还需向量) 为从这个局面买齐的最低花费。dfs 就是一个自己调用自己的函数（递归），拿它当键把结果存下来，这就是记忆化搜索（算过的局面存进表，再遇到直接取值）。

礼包买不买，为什么取 min 就对

算 dfs(还需) 从两种来路取小。第一种是原价单买，剩下每件按原价乘还需加起来，是不用礼包的兜底价，先当当前最优；有时所有礼包都不划算，这条退路必须留。

第二种是逐个试礼包，能不能买只看一条：礼包每件要拿的数量都不超过对应还需，有一件超了就超买，题目不许，直接跳过。买得起就扣掉礼包数量得到新还需，花费 = 礼包价 + dfs(新还需)，和当前最优比谁小留谁。能不能买只管超不超买，划不划算交给取小裁。

拿 needs=[3,2] 这组示例手工走一遍

顶层 dfs([3,2])：原价单买是 2×3+5×2=16，先记 16。试礼包1[3 个 A]：A 3≥3、B 2≥0 买得起，扣成 [0,2]，花费 5+dfs([0,2])；dfs([0,2]) 里 A 已是 0、两礼包都要 A 拿不出，只能原价买 2 个 B 得 10，即 5+10=15 比 16 省。

再试礼包2[1 个 A 加 2 个 B]：A 3≥1、B 2≥2 买得起，扣成 [2,0]，花费 10+dfs([2,0])；dfs([2,0]) 里 B 已是 0，礼包2 要 2 个 B 超买、礼包1 要 3 个 A 也不够，只能原价买 2 个 A 得 4，即 10+4=14 比 15 更省。dfs([3,2]) 取小得 14 就是答案。

状态数为什么不会爆，超买和兜底别漏

状态数是关键账：每件还需只能从 0 到清单上限，各件（还需+1）连乘即上限，『不能超买』死死压住它，本例只走出 [3,2]、[0,2]、[2,0] 三个。每状态遍历礼包各 n 件，记忆化只算一次，时间 O(状态数×礼包数×n)。漏了原价单买这条兜底最要命，所有礼包都不划算时就彻底没退路。漏判超买同样致命：礼包数量超过还需会让还需变负，整个答案跟着错。清单为空花费 0、无礼包时全按原价单买，边界都自动对。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def shoppingOffers(
        self, price: List[int], special: List[List[int]], needs: List[int]
    ) -> int:
        @cache
        def dfs(cur: int) -> int:
            ans = sum(p * (cur >> (i * bits) & 0xF) for i, p in enumerate(price))
            for offer in special:
                nxt = cur
                for j in range(len(needs)):
                    if (cur >> (j * bits) & 0xF) < offer[j]:
                        break
                    nxt -= offer[j] << (j * bits)
                else:
                    ans = min(ans, offer[-1] + dfs(nxt))
            return ans

        bits, mask = 4, 0
        for i, need in enumerate(needs):
            mask |= need << i * bits
        return dfs(mask)

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        const int bits = 4;
        int n = needs.size();
        unordered_map<int, int> f;
        int mask = 0;
        for (int i = 0; i < n; ++i) {
            mask |= needs[i] << (i * bits);
        }
        function<int(int)> dfs = [&](int cur) {
            if (f.find(cur) != f.end()) {
                return f[cur];
            }
            int ans = 0;
            for (int i = 0; i < n; ++i) {
                ans += price[i] * ((cur >> (i * bits)) & 0xf);
            }
            for (const auto& offer : special) {
                int nxt = cur;
                bool ok = true;
                for (int j = 0; j < n; ++j) {
                    if (((cur >> (j * bits)) & 0xf) < offer[j]) {
                        ok = false;
                        break;
                    }
                    nxt -= offer[j] << (j * bits);
                }
                if (ok) {
                    ans = min(ans, offer[n] + dfs(nxt));
                }
            }
            f[cur] = ans;
            return ans;
        };
        return dfs(mask);
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private final int bits = 4;
    private int n;
    private List<Integer> price;
    private List<List<Integer>> special;
    private Map<Integer, Integer> f = new HashMap<>();

    public int shoppingOffers(
        List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        n = needs.size();
        this.price = price;
        this.special = special;
        int mask = 0;
        for (int i = 0; i < n; ++i) {
            mask |= needs.get(i) << (i * bits);
        }
        return dfs(mask);
    }

    private int dfs(int cur) {
        if (f.containsKey(cur)) {
            return f.get(cur);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += price.get(i) * (cur >> (i * bits) & 0xf);
        }
        for (List<Integer> offer : special) {
            int nxt = cur;
            boolean ok = true;
            for (int j = 0; j < n; ++j) {
                if ((cur >> (j * bits) & 0xf) < offer.get(j)) {
                    ok = false;
                    break;
                }
                nxt -= offer.get(j) << (j * bits);
            }
            if (ok) {
                ans = Math.min(ans, offer.get(n) + dfs(nxt));
            }
        }
        f.put(cur, ans);
        return ans;
    }
}