HDU 3033 I love sneakers!：分組背包變體的最小費用最大價值求解

題目大意

XX 去買鞋，共有 K 個品牌，給出 N 雙鞋，每雙屬於某品牌、有價格 cost、收藏價值 val。XX 要求每個品牌至少買 1 雙 (若該品牌有鞋)。總預算 M。求滿足條件下的最大總價值，無解輸出 Impossible。

建模：必選分組背包

每個品牌 = 一組。組內物品 = 該品牌的各雙鞋。約束：每組至少選 1 個。這是「分組背包」的必選變體。

狀態定義與轉移

dp[i][j] = 前 i 個品牌 (組) 恰好花費 j 元獲得的最大價值
         = -1 表示不可達

第 i 組轉移：

• 選第 k 雙鞋作為本組第一雙：從 dp[i-1][j-cost] 轉移
• 選第 k 雙鞋作為本組額外第 2,3... 雙：從 dp[i][j-cost] 轉移 (已包含本組至少 1 雙)

合併：

for each shoe k in brand i:
    for j = M down to cost[k]:
        // 作為第一雙
        if dp[i-1][j-cost] != -1
            dp[i][j] = max(dp[i][j], dp[i-1][j-cost] + val);
        // 作為額外雙
        if dp[i][j-cost] != -1
            dp[i][j] = max(dp[i][j], dp[i][j-cost] + val);

逆序 j 保證 0-1 特性 (同一雙鞋不重複買)。
同時從 dp[i-1] 和 dp[i] 轉移，自然實現「至少 1 雙，可多買」。

完整 AC 代碼

#include 
#include 
#include 
using namespace std;

#define MAX_K 11
#define MAX_M 11000
#define MAX_N 11000

struct Shoe { int cost, val; };
Shoe shoes[MAX_K][MAX_N];
int len[MAX_K];          // 每個品牌鞋的數量
int dp[MAX_K][MAX_M];

int main()
{
    int n, m, k;
    while (scanf("%d%d%d", &n, &m, &k) == 3) {
        memset(len, 0, sizeof(len));
        memset(dp, -1, sizeof(dp));

        for (int i = 1; i <= n; i++) {
            int brand, cost, val;
            scanf("%d%d%d", &brand, &cost, &val);
            len[brand]++;
            shoes[brand][len[brand]] = {cost, val};
        }

        int groupsDone = 0;
        dp[0][0] = 0;

        for (int i = 1; i <= k; i++) {
            if (len[i] == 0) continue; // 該品牌無鞋，跳過 (不計入必選組數)
            groupsDone++;

            for (int j = 1; j <= len[i]; j++) {
                int c = shoes[i][j].cost;
                int v = shoes[i][j].val;
                for (int s = m; s >= c; s--) {
                    // 作為本組第一雙
                    if (dp[groupsDone-1][s-c] != -1)
                        dp[groupsDone][s] = max(dp[groupsDone][s], dp[groupsDone-1][s-c] + v);
                    // 作為本組額外雙
                    if (dp[groupsDone][s-c] != -1)
                        dp[groupsDone][s] = max(dp[groupsDone][s], dp[groupsDone][s-c] + v);
                }
            }
        }

        int ans = -1;
        for (int s = 0; s <= m; s++)
            ans = max(ans, dp[groupsDone][s]);

        if (groupsDone == k && ans != -1)
            printf("%d\n", ans);
        else
            printf("Impossible\n");
    }
    return 0;
}

關鍵點解析

1. 品牌可能無鞋：輸入 N 雙鞋分佈在 K 品牌中，某品牌可能為 0。此時該品牌不納入必選組計數 (代碼中 groupsDone 只遞增非空品牌)。
2. 雙重轉移來源：dp[i-1] (第一雙) + dp[i] (額外雙) 是「至少 1」的精髓。若只有 dp[i-1] → 最多 1 雙；若只有 dp[i] → 至少 1 雙但無法啟動 (無基礎狀態)。
3. 逆序容量循環：s = m down to cost 防止同一雙鞋在同一組內被重複選取 (0-1 特性)。
4. 最終答案取 max over s≤M：不必恰好花光預算，求 ≤ M 的最大值。
5. 輸出條件：必須 groupsDone == k (所有有鞋品牌都買了) 且 ans != -1 (預算內可行)。

測試用例驗證

輸入:
5 10000 3
1 4 6
2 5 7
3 4 99
1 55 77
2 44 66

輸出: 249  (品牌1買4+55=59價值83, 品牌2買5+44=49價值73, 品牌3買4價值99, 總價108, 總值249)

複雜度

• 時間：O(K × M × 平均每組物品數) ≈ 10 × 10000 × 1000 = 10⁸ (邊界緊，但實際數據較小通常能過)
• 空間：O(K × M) = 11 × 11000 ≈ 1.2e5 int ≈ 0.5 MB

優化提示：若 M 更大，可改用一維 dp[M+1] 滾動數組，但必選組邏輯需小心處理「第一雙」來源 (需保留上一組副本)。

總結

HDU 3033 將「分組背包」推廣到「必選分組背包 + 組內 0-1 多選」。核心技巧是雙重轉移來源：dp[i-1] 啟動本組第一項，dp[i] 疊加本組後續項。這一模式廣泛適用於：「每類資源至少配置 1 份，可追加投資」的預算分配、廣告投放、技能點分配等實戰問題。