HDU 3033 I love sneakers!：分組背包變體（每組至少選一）

HDU 3033 是分組背包的變體：k 個品牌（組），每組至少選一雙鞋，總預算 m，最大化收藏價值。若無法滿足至少選一約束，輸出 Impossible。

問題建模

• n 雙鞋，屬於 k 個品牌之一
• 每雙鞋：品牌 b、價格 cost、價值 val
• 每個品牌至少選一雙，可選多雙
• 總花費 ≤ m
• 最大化總價值

狀態定義

dp[i][j]：考慮前 i 個品牌，花費 j 的最大價值（-1 表示不可達）

狀態轉移（關鍵：兩類來源）

處理第 i 品牌的第 t 雙鞋（價格 c、價值 v）：

1. 從上一組轉移（本組第一雙）：dp[i][j] = max(dp[i][j], dp[i-1][j-c] + v)
2. 從本組轉移（本組第二雙及以後）：dp[i][j] = max(dp[i][j], dp[i][j-c] + v)

這完美體現了「至少一雙」：第一雙必須從上一組來，後續可從本組疊加。

完整 AC 代碼

#include 
#include 
using namespace std;

#define MAX 11000

struct Shoe { int cost, val; };
Shoe shoes[11][MAX];
int dp[11][MAX], len[11];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    while (cin >> n >> m >> k) {
        memset(len, 0, sizeof(len));
        memset(dp, -1, sizeof(dp));

        for (int i = 1; i <= n; i++) {
            int b, c, v;
            cin >> b >> c >> v;
            shoes[b][++len[b]] = {c, v};
        }

        dp[0][0] = 0;
        int groups = 0;

        for (int i = 1; i <= k; i++) {
            if (len[i] == 0) break;  // 某品牌無鞋，不可能
            groups++;

            for (int t = 1; t <= len[i]; t++) {
                int c = shoes[i][t].cost;
                int v = shoes[i][t].val;
                for (int j = m; j >= c; j--) {
                    // 從上一組轉移（第一雙）
                    if (dp[groups-1][j-c] != -1)
                        dp[groups][j] = max(dp[groups][j], dp[groups-1][j-c] + v);
                    // 從本組轉移（第二雙+）
                    if (dp[groups][j-c] != -1)
                        dp[groups][j] = max(dp[groups][j], dp[groups][j-c] + v);
                }
            }
        }

        if (groups != k) { cout << "Impossible\n"; continue; }

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

        if (ans == -1) cout << "Impossible\n";
        else cout << ans << "\n";
    }
    return 0;
}

關鍵點解析

測試樣例

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

3 10000 2
1 2 3
1 3 4
1 5 6

5 10000 3
1 1000 3
1 1000 4
2 100000 4
3 1000 3
3 1000 4

Output:
249
Impossible
Impossible

變體對比總結

結語

HDU 3033 通過「雙重轉移來源」優雅地解決了「至少選一」約束。這一技巧可推廣到：分組最少選 k 件、分組選擇數量範圍 [L, R] 等變體。核心思想：將約束分解為「第一件」與「後續件」的不同狀態來源。掌握此模式，分組背包變體不再懼怕。