POJ 1170 Shopping Offers：狀態壓縮 DP 解背包變種

POJ 1170 Shopping Offers - 狀態壓縮 DP 轉完全背包

本題核心是將「購買指定數量商品，可使用優惠套餐」轉化為多維度完全背包問題。關鍵在於用 6 進制狀態壓縮表示購買狀態。

狀態設計

最多 5 種商品，每種最多買 5 件 → 每維基數為 6。狀態 S = c₀ + c₁×6 + c₂×6² + c₃×6³ + c₄×6⁴，其中 cᵢ 為第 i 種商品購買數量。目標狀態由需求數量決定。

轉移方程

將每種單品與優惠套餐統一視為「物品」：

• 單品：價格 = 單價，狀態增量 = 對應維度 +1
• 優惠套餐：價格 = 套餐價，狀態增量 = 套餐包含的各商品數量組合

完全背包轉移：dp[newState] = min(dp[newState], dp[oldState] + price)

核心代碼

const int MAXS = 6*6*6*6*6; // 7776 狀態
int dp[MAXS], sixPow[6] = {1,6,36,216,1296,7776};

void CompletePack() {
    fill(dp, dp+MAXS, INF);
    dp[0] = 0;
    for (int s = 0; s < targetState; ++s) {
        if (dp[s] == INF) continue;
        for (int j = 0; j < totalItems; ++j) {
            int ns = s + items[j].state;
            if (ns > targetState) continue;
            dp[ns] = min(dp[ns], dp[s] + items[j].price);
        }
    }
    cout << dp[targetState] << endl;
}

關鍵技巧

1. 狀態編碼：6 進制確保每維獨立，避免進位干擾
2. ID 映射：商品編號 1~999 映射到 0~4 索引
3. 優惠套餐處理：讀取套餐內容直接合成狀態增量

複雜度

狀態數 7776，物品數 ≤ 104，時間 O(狀態數 × 物品數) ≈ 8×10⁵，極快。