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

HDU 1011 Starship Troopers：樹形 DP 背包問題

編輯：關於C++

HDU 1011 Starship Troopers 詳解

題目：地下基地為樹狀結構（入口為根節點 1），N (≤100) 個房間，每房間有 bug 數與「含腦概率」 val。每兵可殺 20 隻 bug。共 M (≤100) 兵。從根出發，經過房間必須留足夠兵力殺光該房間 bug（bug=0 也需 1 兵），剩餘兵力可繼續下探。士兵不回頭。選擇一組房間（含根到該房間的路徑上所有房間），使總兵力 ≤ M 且 總概率和最大。輸出最大概率和。

核心模型：樹上分組背包（依賴背包）

每個節點 u 有「代價」 cost[u] = ceil(bug[u]/20.0)（至少 1）、「價值」 val[u]。
選擇節點 u 的前提是：其父節點已被選擇（因為必須經過父節點才能到達）。這是典型的樹形依賴背包：父節點是子節點的「前置條件」。

狀態定義

dp[u][j]：在以 u 為根的子樹中，花費恰好 j 個兵力（含 u 自身代價），能獲得的最大概率和。
若不選 u，則其子樹全不可選（dp[u][*] = 0 或 -INF）。但因根必須選，最終答案在 dp[1][1..M] 中取最大值。

狀態轉移：合併子樹

DFS 後序遍歷。初始化：
for j = cost[u] .. M: dp[u][j] = val[u]（只選自己）。
對每個子節點 v：

for j = M down to cost[u]:          // 逆序防止重複使用
    for k = 1; k + cost[u] <= j; ++k: // 分配 k 兵力給子樹 v
        dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]);

關鍵細節：
- k 從 1 開始，因為若分配 0 兵力給 v，等價於不選 v（已在 dp[u][j-k] 中體現）。
- j 逆序是 01 背包標準技巧，保證每個子樹只被合併一次。
- cost[u] 計算：(bug[u] + 19) / 20，bug=0 時為 1。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
int n, m;
int bug[MAXN], val[MAXN];
int cost[MAXN];
vector g[MAXN];
int dp[MAXN][MAXN];

void dfs(int u, int fa) {
    // 初始化：只選 u
    for (int j = cost[u]; j <= m; ++j) dp[u][j] = val[u];
    // 合併子樹
    for (int v : g[u]) {
        if (v == fa) continue;
        dfs(v, u);
        for (int j = m; j >= cost[u]; --j) {
            for (int k = 1; k + cost[u] <= j; ++k) {
                dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> n >> m) {
        if (n == -1 && m == -1) break;
        for (int i = 1; i <= n; ++i) {
            cin >> bug[i] >> val[i];
            cost[i] = (bug[i] + 19) / 20; // 至少 1
            g[i].clear();
        }
        for (int i = 0; i < n-1; ++i) {
            int u, v; cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        memset(dp, 0, sizeof(dp));
        dfs(1, 0);
        int ans = 0;
        for (int j = 1; j <= m; ++j) ans = max(ans, dp[1][j]);
        cout << ans << '\n';
    }
    return 0;
}