Knapsack trên cây

Wiki › Thuật toán › Quy hoạch động (DP)

huunguyen · Last updated 8, Tháng 4, 2026, 16:43

Knapsack trên cây (Tree Knapsack) là bài toán chọn tập đỉnh từ cây sao cho thỏa ràng buộc cấu trúc (thường là liên thông hoặc bao gồm gốc), tổng trọng số $\leq W$ , và tổng giá trị lớn nhất.

Dạng 1: Chọn subtree có gốc cố định — $O (N W)$

Bài toán: Chọn tập đỉnh chứa gốc, liên thông, tổng trọng số $\leq W$ , giá trị lớn nhất.

Trạng thái: $d p [u] [j]$ = giá trị lớn nhất khi chọn đúng $j$ đơn vị trọng số từ cây con gốc $u$ (bắt buộc chọn $u$ ).

Merge từng con: Khi xử lý con $v$ của $u$ , gộp $d p [v]$ vào $d p [u]$ như knapsack thông thường:

d p [u] [j + k] = max (d p [u] [j + k], d p [u] [j] + d p [v] [k])

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

const int MAXN = 305;
int n, W;
int w[MAXN], val[MAXN];
vector<int> adj[MAXN];
int dp[MAXN][MAXN];   // dp[u][j] = max value, chọn j kg từ subtree u (u bắt buộc chọn)
int sz[MAXN];         // tổng trọng số cây con (dùng để giới hạn vòng lặp)

void dfs(int u, int par) {
    dp[u][w[u]] = val[u];   // chỉ chọn u
    sz[u] = w[u];

    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);

        // Merge dp[v] vào dp[u], duyệt ngược để tránh dùng v hai lần
        for (int j = min(sz[u], W); j >= w[u]; j--) {
            for (int k = min(sz[v], W - j); k >= 0; k--) {
                if (dp[u][j] >= 0 && dp[v][k] >= 0)
                    dp[u][j + k] = max(dp[u][j + k], dp[u][j] + dp[v][k]);
            }
        }
        sz[u] += sz[v];
    }
}

int main() {
    cin >> n >> W;
    for (int i = 1; i <= n; i++) cin >> w[i] >> val[i];
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    memset(dp, -1, sizeof(dp));
    dfs(1, 0);

    int ans = 0;
    for (int j = 0; j <= W; j++)
        ans = max(ans, dp[1][j]);
    cout << ans << "\n";
}

Tại sao $O (N W)$ ? Mỗi cặp đỉnh $(u, v)$ chỉ bị so sánh đúng một lần tại LCA của chúng — tổng số phép so sánh là $O (N W)$ .

Dạng 2: Chọn tập đỉnh có ràng buộc cha-con (Dependency Knapsack)

Bài toán: Nếu chọn đỉnh $v$ thì bắt buộc chọn cha của $v$ . Tổng trọng số $\leq W$ , giá trị lớn nhất.

void dfs(int u, int par) {
    // Không chọn u: dp[u][0] = 0
    dp[u][0] = 0;
    // Chọn u: bắt đầu từ dp[u][w[u]] = val[u]
    dp[u][w[u]] = val[u];
    sz[u] = w[u];

    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);

        // Merge: với mỗi j (đã tính u và các con trước), thêm con v
        for (int j = min(sz[u], W); j >= 0; j--) {
            if (dp[u][j] < 0) continue;
            for (int k = min(sz[v], W - j); k >= 0; k--) {
                if (dp[v][k] < 0) continue;
                dp[u][j + k] = max(dp[u][j + k], dp[u][j] + dp[v][k]);
            }
        }
        sz[u] += sz[v];
    }
}

Ví dụ kinh điển: Chọn phòng trong tòa nhà

N

phòng, mỗi phòng có chi phí

c_{i}

và giá trị

v_{i}

. Phòng

i

chỉ có thể chọn nếu phòng cha

p_{i}

được chọn (phòng 0 là gốc, luôn chọn miễn phí). Ngân sách

W

// Thêm root ảo 0: w[0] = 0, val[0] = 0, nối với tất cả gốc thực
// Chạy dfs(0, -1)
// Kết quả: max(dp[0][j]) với j <= W

## Dạng 3: Chọn

k

đỉnh tối đa hóa tổng khoảng cách đôi —

O (N K)

Bài toán: Chọn đúng $k$ đỉnh trên cây có trọng số cạnh, sao cho tổng khoảng cách giữa mọi cặp đỉnh được chọn là lớn nhất.

Ý tưởng phân rã theo cạnh:

\sum_{cặp (u, v)} dist (u, v) = \sum_{cạnh e = (x, y, w)} w \cdot (số đỉnh bên trái) \cdot (số đỉnh bên phải)

Khi merge con $v$ (chọn $j$ đỉnh từ subtree $v$ ) vào $u$ , cạnh $(u, v, w)$ nằm trên đường đi của tất cả cặp có một đầu trong subtree $v$ và một đầu ngoài. Có $j$ đỉnh bên trong và $k - j$ đỉnh bên ngoài → đóng góp $j \cdot (k - j) \cdot w$ .

Trạng thái: $d p [u] [i]$ = tổng khoảng cách đôi lớn nhất khi chọn đúng $i$ đỉnh từ subtree $u$ .

Transition:

d p [u] [i] = {max}_{j} (d p [u] [i - j] + d p [v] [j] + j \cdot (k - j) \cdot w)

const int MAXN = 2005;
vector<pair<int,long long>> adj[MAXN];
long long dp[MAXN][MAXN];   // dp[u][i] = max tổng dist đôi, chọn i đỉnh từ subtree u
int sz[MAXN];
int n, k;

void dfs(int u, int par) {
    sz[u] = 1;
    fill(dp[u], dp[u] + k + 1, -1);
    dp[u][0] = dp[u][1] = 0;   // 0 hoặc 1 đỉnh: không có cặp → tổng = 0

    for (auto [v, w] : adj[u]) {
        if (v == par) continue;
        dfs(v, u);

        // Merge: duyệt ngược để tránh dùng lại
        for (int i = min(k, sz[u] + sz[v]); i >= 0; i--) {
            for (int j = min(i, sz[v]); j >= 0; j--) {
                if (dp[u][i-j] == -1 || dp[v][j] == -1) continue;
                // Cạnh (u,v,w) đóng góp j*(k-j)*w vào tổng khoảng cách đôi
                dp[u][i] = max(dp[u][i],
                    dp[u][i-j] + dp[v][j] + (long long)j * (k - j) * w);
            }
        }
        sz[u] += sz[v];
    }
}

// Gọi dfs(root, 0), kết quả: dp[root][k]

Lưu ý: dp[u][0] = dp[u][1] = 0 vì chọn 0 hoặc 1 đỉnh thì không có cặp nào → tổng khoảng cách = 0. Kết quả là dp[1][k] (chọn đúng $k$ đỉnh từ toàn cây gốc 1).

Bài tập minh họa: Sinh Vật Huyền Bí (creatures) — Chọn đúng $k$ đỉnh trên cây có trọng số cạnh để tổng khoảng cách đôi lớn nhất.

Tối ưu với DFS order

Chuyển cây về mảng DFS order, sau đó chạy knapsack thông thường theo thứ tự DFS. Đây là cách cài đặt thay thế, dễ debug hơn:

// Flatten cây: tin[u] = thứ tự vào DFS, tout[u] = thứ tự ra
// Ràng buộc: nếu chọn u thì chọn các đỉnh trong [tin[u], tout[u]]
// → knapsack với "nhóm" phụ thuộc nhau theo thứ tự DFS

Độ phức tạp

Dạng	Độ phức tạp	Ghi chú
Subtree có gốc	$O (N W)$	Thông dụng nhất
Dependency knapsack	$O (N W)$	Gộp cả không chọn node
Chọn $k$ đỉnh max tổng dist	$O (N K)$	Phân rã theo cạnh
Chọn $k$ đỉnh, small-to-large	$O (N \log^{2} N)$	Khi $W = k$ nhỏ

Khi nào dùng Tree Knapsack?

Chọn tập đỉnh trên cây với ràng buộc "nếu chọn con thì phải chọn cha".
Bài toán phân bổ ngân sách theo cấu trúc cây (phòng ban, dự án phụ thuộc).
$N, W \leq 300$ : dùng $O (N W)$ thẳng.
$N \leq 10^{5}$ , $W = k$ nhỏ: dùng DSU on Tree hoặc DFS order + knapsack.

Bình luận

Không có bình luận tại thời điểm này.