您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

HDU 3033 I love sneakers! 分組背包問題詳解（每組至少選一件）

編輯：C++ 入門

題目大意

給定 k 種鞋子，共 n 雙，每雙鞋子有花費和價值。你有 m 元錢，要求每種鞋子至少買一雙，求能獲得的最大價值總和。若無法滿足條件則輸出 "Impossible"。

核心思路：分組背包變體

這是一道經典的分組背包問題，但與傳統「每組最多選一件」不同，本題要求每組至少選一件，且組內物品可任意選取（0/1 選擇）。

傳統分組背包回顧

傳統分組背包（每組至多選一件）的狀態轉移為：

for 每組 k:
    for v = V down to 0:
        for 組內每個物品 i:
            f[v] = max(f[v], f[v - cost[i]] + val[i])

本題關鍵改動

為了確保每組至少選一件，需將第二、三層循環交換，使組內物品進行 0/1 背包處理：

for 每組 i:
    for 組內每個物品 j:
        for v = m down to cost:
            // 兩種轉移來源：同組已選其他物品、或上一組狀態
            dp[i][v] = max(dp[i][v], 
                           dp[i][v - cost] + val,   // 同組累加
                           dp[i-1][v - cost] + val) // 首次從上組轉移

狀態定義與初始化

dp[i][j]：前 i 組花費 j 元獲得的最大價值
初始化所有 dp[i][j] = -1（表示非法狀態）
dp[0][0..m] = 0：虛擬第 0 組合法，便於第一組計算

完整代碼實現

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

struct Node { int cost, val; } item[12][110];
int dp[12][10010];
int num[12];
int n, m, k;

void solve() {
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i <= m; i++) dp[0][i] = 0; // 第0組初始化

    for (int i = 1; i <= k; i++) {
        for (int j = 0; j < num[i]; j++) {
            for (int v = m; v >= item[i][j].cost; v--) {
                if (dp[i][v - item[i][j].cost] != -1)
                    dp[i][v] = max(dp[i][v], dp[i][v - item[i][j].cost] + item[i][j].val);
                if (dp[i-1][v - item[i][j].cost] != -1)
                    dp[i][v] = max(dp[i][v], dp[i-1][v - item[i][j].cost] + item[i][j].val);
            }
        }
    }
}

int main() {
    while (~scanf("%d%d%d", &n, &m, &k)) {
        memset(num, 0, sizeof(num));
        for (int i = 0; i < n; i++) {
            int g, c, v;
            scanf("%d%d%d", &g, &c, &v);
            item[g][num[g]].cost = c;
            item[g][num[g]].val = v;
            num[g]++;
        }
        solve();
        if (dp[k][m] < 0) printf("Impossible\n");
        else printf("%d\n", dp[k][m]);
    }
    return 0;
}