哈利波特購書優惠算法：動態規劃求解最低價格完整指南

題目描述

書店對《哈利波特》全套 5 卷（編號 0-4）推出階梯優惠：

規則：同一卷書不重複享受優惠。例如買 2 卷第 1 冊 + 1 卷第 2 冊，只能組成一組「2 不同卷」享 5% 折扣，剩餘第 1 冊原價。目標：給定任意購買清單，計算最低總價。

核心觀察：分組優惠本質

每次結帳實際上是將購買清單拆分為若干「不同卷組合」，每組按其大小享受對應折扣。問題轉化為：如何將多集合拆分為若干子集，使總成本最小。

關鍵洞察：

• 5 卷全套單價最低（6 元），但湊齊 5 卷不一定最優（如 8 卷時：5+3 = 52.4 元，4+4 = 51.2 元）。
• 只有 8 卷是特例（4+4 優於 5+3），其餘情況優先組 5 卷再處理餘數通常最優。

動態規劃通用解法（推薦）

狀態定義：dp[mask] 表示某種庫存狀態下的最小花費。因只有 5 種書，用 5 位二進位表示每種書剩餘數量（為簡化，實際可用計數陣列 + 記憶化搜索）。

更直觀的記憶化遞歸：

public class HarryPotterPricing {
    private static final int PRICE = 800; // 分為單位，避免浮點誤差
    private static final int[] DISC = {0, 0, 5, 10, 20, 25}; // 索引=組大小
    private Map<String, Integer> memo = new HashMap<>();

    public int minPrice(int[] books) { // books[i] = 第i卷購買數量
        return dfs(books);
    }

    private int dfs(int[] books) {
        String key = Arrays.toString(books);
        if (memo.containsKey(key)) return memo.get(key);

        // 終止條件：全買完
        boolean allZero = true;
        for (int c : books) if (c > 0) { allZero = false; break; }
        if (allZero) return 0;

        int best = Integer.MAX_VALUE;
        // 嘗試組成大小為 1~5 的組合
        for (int k = 1; k <= 5; k++) {
            // 找出所有可行的 k 不同卷組合（回溯生成）
            List<int[]> combos = genCombos(books, k, new int[k], 0, 0);
            for (int[] combo : combos) {
                // 扣減庫存
                int[] next = books.clone();
                for (int idx : combo) next[idx]--;
                // 當前組價格 + 遞歸餘下
                int cost = k * PRICE * (100 - DISC[k]) / 100 + dfs(next);
                best = Math.min(best, cost);
            }
        }
        memo.put(key, best);
        return best;
    }

    // 生成所有可行的 k 不同卷組合（索引遞增保證不重複）
    private List<int[]> genCombos(int[] books, int k, int[] cur, int start, int depth) {
        List<int[]> res = new ArrayList<>();
        if (depth == k) { res.add(cur.clone()); return res; }
        for (int i = start; i < 5; i++) {
            if (books[i] > 0) {
                cur[depth] = i;
                res.addAll(genCombos(books, k, cur, i + 1, depth + 1));
            }
        }
        return res;
    }
}

貪心 + 特例修正（面試快速寫法）

若面試要求 O(1) 空間、簡潔代碼，可用「優先組 5 卷，餘數處理」+ 8 卷特例：

public int minPriceGreedy(int totalBooks) { // 假設每卷至少 1 本，或傳入計數陣列
    // 此處演示總冊數版，實際需按各卷數量分配
    // 完整版見上方 DP
}

注意：貪心僅在「每卷數量相近」時成立；通用情況必須用 DP/記憶化搜索。

測試用例驗證

複雜度分析

• 狀態數：每卷最多 N 本，狀態上界 (N+1)⁵。實際 N 較小（如 ≤50）完全可接受。
• 轉移：每狀態嘗試 k=1..5，組合數 C(5,k) ≤ 10，極小。
• 時間：O(狀態數 × 31) ≈ 線性於總冊數。
• 空間：O(狀態數) 記憶化表。

擴展思考

1. 不同書籍不同定價：DP 狀態增加價格維度，或將價格歸一化後同邏輯。
2. 優惠規則變動：只需修改 DISC 陣列，核心邏輯不變。
3. 大規模 SKU：狀態空間爆炸時，改用最小費用最大流或整數規劃求解器。

此題是「多集合分割優化」的經典入門，掌握狀態壓縮 + 記憶化搜索模板，可解決大量類似組合優惠定價問題。