Wiki › Thuật toán › Quy hoạch động (DP) › Knapsack trên cây

Knapsack trên cây

huunguyen Updated Tháng sáu 1, 2026

Knapsack trên cây (Tree Knapsack) là bài toán chọn một 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, chứa gốc, hoặc nếu chọn con thì phải chọn cha — đồng thời tối ưu một đại lượng (tổng giá trị lớn nhất với ngân sách $\leq W$ , hoặc chọn đúng $k$ đỉnh). Bằng cách gộp (merge) lời giải của các cây con như một bài knapsack, ta giải được trong $O (N W)$ (hoặc $O (N K)$ ) thay vì xét $2^{N}$ tập con — một cải thiện từ mũ xuống đa thức.

Ý tưởng / Trực giác

Điểm mấu chốt: với cây, mọi quyết định ở cây con $v$ độc lập với phần còn lại của cây, ngoại trừ thông qua đúng một con số — đã dùng bao nhiêu trọng số (hoặc đã chọn bao nhiêu đỉnh). Vì vậy ta có thể tóm tắt toàn bộ cây con $u$ bằng một mảng:

$d p [u] [j] = giá trị tốt nhất khi dùng đúng j đơn vị "ngân sách" trong cây con gốc u$

Khi đứng ở đỉnh $u$ và lần lượt xử lý các con $v_{1}, v_{2}, \dots$ , mỗi con đã có sẵn mảng $d p [v_{i}]$ . Gộp một con mới vào chính là phép knapsack hai mảng: nếu phần đã gộp dùng $j$ ngân sách và con mới dùng $k$ , kết quả dùng $j + k$ :

$d p [u] [j + k] \leftarrow max (d p [u] [j + k], d p [u] [j] + d p [v] [k])$

Vì sao đúng? Một tập đỉnh được chọn trong cây con $u$ phân hoạch duy nhất theo: phần thuộc các con đã xử lý trước, và phần thuộc con $v$ đang xét. Hai phần này không chia sẻ đỉnh nào (cây con khác nhau rời nhau), nên giá trị cộng được và ngân sách cộng được — đúng cấu trúc của knapsack. Ràng buộc cấu trúc (liên thông / chọn con kéo theo cha) được mã hóa vào cách khởi tạo $d p [u]$ và cận dưới của vòng lặp chứ không phải vào phép merge.

Vì sao tổng độ phức tạp chỉ $O (N W)$ chứ không phải $O (N^{2} W)$ ? Đây là kết quả không hiển nhiên. Nếu trong vòng lặp merge ta giới hạn $j$ theo kích thước cây con đã gộp ( $s z [u]$ ) và $k$ theo kích thước cây con $v$ ( $s z [v]$ ), thì mỗi cặp đỉnh $(a, b)$ chỉ bị "ghép" với nhau đúng một lần — tại tổ tiên chung thấp nhất (LCA) của $a$ và $b$ , đúng thời điểm hai cây con chứa $a$ và $b$ được gộp. Số cặp đỉnh là $O (N^{2})$ , nhân với chi phí $W$ trên mỗi đơn vị, ra $O (N W)$ (khi $W \approx N$ thì là $O (N^{2})$ ). Bắt buộc phải dùng min(sz[u], W) và min(sz[v], ...) làm cận, nếu không sẽ tụt xuống $O (N^{2} W)$ .

Ví dụ chạy tay

Xét bài Dạng 2 (Dependency Knapsack): chọn con thì phải chọn cha; ngân sách $W = 3$ . Cây và dữ liệu (trọng số $w$ , giá trị $v a l$ ):

            (1) w=1 val=2
           /            \
       (2) w=1         (3) w=2
        val=3           val=4
        /
    (4) w=2
     val=5

Định nghĩa $d p [u] [j]$ = giá trị lớn nhất dùng đúng $j$ ngân sách trong cây con $u$ , trong đó nếu chọn bất kỳ đỉnh nào của cây con thì phải chọn $u$ . Khởi tạo: $d p [u] [0] = 0$ (không chọn gì), $d p [u] [w_{u}] = v a l_{u}$ (chỉ chọn $u$ ). Ô trống = $- \infty$ (không đạt được).

Lá 4 ( $w = 2, v a l = 5$ ):

j	0	1	2	3
dp[4]	0	·	5	·

Lá 3 ( $w = 2, v a l = 4$ ):

j	0	1	2	3
dp[3]	0	·	4	·

Đỉnh 2 ( $w = 1, v a l = 3$ ): khởi tạo $d p [2] [0] = 0, d p [2] [1] = 3$ , rồi gộp con 4. Con 4 dùng $k \in {0, 2}$ . Duyệt $j$ giảm dần:

$j = 1$ (đã chọn 2): cộng $d p [4] [2] = 5 \Rightarrow d p [2] [3] = 3 + 5 = 8$ (chọn ${2, 4}$ ).
$j = 0$ : chỉ giữ được $d p [2] [0] = 0$ (không chọn gì).

Sau khi gộp con 4, bảng $d p [2]$ :

j	0	1	2	3
dp[2]	0	3	·	8

Gốc 1 ( $w = 1, v a l = 2$ ): khởi tạo $d p [1] [0] = 0, d p [1] [1] = 2$ . Cận merge ở đây là $j \geq w_{1} = 1$ (muốn chọn con thì phải đã chọn 1).

Gộp con 2 (dùng $k \in {0, 1, 3}$ với giá trị $0, 3, 8$ ), duyệt $j$ từ cao xuống, chỉ $j \geq 1$ :

$j = 1$ : $k = 0 \Rightarrow d p [1] [1] = 2$ ; $k = 1 \Rightarrow d p [1] [2] = 2 + 3 = 5$ ; $k = 3$ vượt ( $1 + 3 = 4 > 3$ ), bỏ.

Sau khi gộp con 2:

j	0	1	2	3
dp[1]	0	2	5	·

Gộp tiếp con 3 ( $k \in {0, 2}$ , giá trị $0, 4$ ), vẫn $j \geq 1$ :

$j = 2$ : $k = 0 \Rightarrow$ giữ $5$ ; $k = 2$ → $2 + 2 = 4 > 3$ , bỏ.
$j = 1$ : $k = 0 \Rightarrow 2$ ; $k = 2 \Rightarrow d p [1] [3] = 2 + 4 = 6$ .

Bảng cuối:

j	0	1	2	3
dp[1]	0	2	5	6

Đáp số $= {max}_{j} d p [1] [j] = 6$ , đạt khi chọn ${1, 3}$ (trọng số $1 + 2 = 3$ , giá trị $2 + 4 = 6$ ). So với ${1, 2}$ giá trị $5$ hay ${1, 2, 4}$ trọng số $4 > W$ — phương án ${1, 3}$ thắng.

Cài đặt

Dạng 1 — Chọn cây con liên thông chứa gốc

Bài toán: chọn tập đỉnh liên thông chứa gốc, 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 dùng đúng $j$ trọng số, bắt buộc chọn $u$ .

#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, dùng j trọng số trong subtree u (u BẮT BUỘC chọn)
int sz[MAXN];         // tổng trọng số subtree u đã gộp -> dùng làm cận vòng lặp

void dfs(int u, int par) {
    dp[u][w[u]] = val[u];   // trạng thái cơ sở: chỉ chọn mình u
    sz[u] = w[u];

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

        // Gộp dp[v] vào dp[u]. Duyệt j GIẢM DẦN để mỗi con chỉ dùng 1 lần
        // (giống 0/1 knapsack). Cận j >= w[u] vì luôn phải có u trong tập.
        for (int j = min(sz[u], W); j >= w[u]; j--) {
            // k <= W - j để không vượt ngân sách; k <= sz[v] để giữ O(NW)
            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];   // cập nhật cận SAU khi gộp xong con 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));   // -1 = trạng thái không đạt được
    dfs(1, 0);

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

Dạng 2 — Dependency Knapsack (chọn con kéo theo cha)

Khác Dạng 1 ở chỗ cho phép không chọn cả cây con ( $d p [u] [0] = 0$ ), nhưng hễ chọn đỉnh nào trong cây con thì cha của nó (và do đệ quy, cả $u$ ) phải có mặt.

void dfs(int u, int par) {
    dp[u][0] = 0;          // không chọn gì trong subtree u
    dp[u][w[u]] = val[u];  // chọn u (mở đường cho việc chọn các con)
    sz[u] = w[u];

    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);
        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];
    }
}

Mẹo cài bài "chọn dự án phụ thuộc / chọn phòng trong tòa nhà": thêm gốc ảo 0 với $w_{0} = 0, v a l_{0} = 0$ nối tới mọi gốc thực, chạy dfs(0, -1), đáp số $= {max}_{j \leq W} d p [0] [j]$ .

Dạng 3 — Chọn đúng $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, tối đa hóa tổng khoảng cách giữa mọi cặp. Mẹo phân rã theo cạnh: một cạnh $(x, y, w)$ đóng góp vào khoảng cách của một cặp khi và chỉ khi cặp đó nằm hai phía của cạnh. Nếu cây con phía dưới cạnh có $j$ đỉnh được chọn và phía trên có $k - j$ đỉnh, cạnh được đếm $j \cdot (k - j)$ lần:

$\sum_{cặp} dist = \sum_{cạnh (x, y, w)} w \cdot j \cdot (k - j)$

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 trong cây con $u$ .

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 trong subtree u
int sz[MAXN], 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;   // chọn 0 hoặc 1 đỉnh: chưa có cặp nào -> tổng = 0

    for (auto [v, w] : adj[u]) {
        if (v == par) continue;
        dfs(v, u);
        for (int i = min(k, sz[u] + sz[v]); i >= 0; i--) {       // tổng đỉnh sau khi gộp
            for (int j = min(i, sz[v]); j >= 0; j--) {           // j đỉnh lấy từ con v
                if (dp[u][i - j] == -1 || dp[v][j] == -1) continue;
                // cạnh (u,v,w) bị j*(k-j) cặp đi qua -> cộng w*j*(k-j)
                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(1, 0); đáp số = dp[1][k]

Lưu ý hệ số $(k - j)$ dùng tổng số đỉnh được chọn trên toàn cây ( $k$ ), không phải số đỉnh đã gộp — vì cạnh được đi qua bởi mọi cặp một-đầu-trong/một-đầu-ngoài, mà "ngoài" tính trên toàn bộ $k$ đỉnh cuối cùng.

Độ phức tạp

Dạng	Thời gian	Bộ nhớ
Cây con liên thông / Dependency	$O (N W)$	$O (N W)$
Chọn $k$ đỉnh max tổng dist	$O (N K)$	$O (N K)$

Thời gian: như đã lý giải ở mục Trực giác — nhờ cận min(sz[u], W) và min(sz[v], …), mỗi cặp đỉnh chỉ được ghép một lần tại LCA của chúng, tổng số phép cộng là $O (N W)$ (hoặc $O (N K)$ ). Không có cận này, độ phức tạp tụt xuống $O (N^{2} W)$ .

Bộ nhớ: mảng dp[N][W+1] chiếm $O (N W)$ . Với $N, W \leq 300$ là $~ 90000$ ô — ổn. Với $N$ lớn ( $10^{5}$ ) mà $W$ cũng lớn thì $O (N W)$ bộ nhớ là không khả thi; khi đó cần ép cây về DFS order rồi knapsack 1 chiều (xem Biến thể).

⚠️ Lỗi thường gặp

Không đặt cận min(sz[u], W) và min(sz[v], …) cho vòng lặp — Đây là lỗi nghiêm trọng nhất. Nếu cho $j, k$ chạy thẳng tới $W$ , độ phức tạp thành $O (N^{2} W)$ và TLE trên $N$ vài nghìn. Luôn giới hạn theo kích thước (tổng trọng số / số đỉnh) cây con đã gộp.
Cập nhật sz[u] sai thời điểm — Phải cộng sz[u] += sz[v] sau khi gộp xong con $v$ . Nếu cộng trước, cận min(sz[u], W) của vòng $j$ sẽ bao gồm cả $v$ , khiến một đỉnh của $v$ bị ghép với chính nó (dùng hai lần).
Duyệt $j$ tăng dần thay vì giảm dần — Như 0/1 knapsack, phải duyệt $j$ giảm dần để mỗi cây con chỉ được tính một lần. Duyệt tăng dần sẽ "tái sử dụng" giá trị vừa cập nhật, cho kết quả vượt mức (như unbounded knapsack).
Tràn số — Với Dạng 3, tích $j \cdot (k - j) \cdot w$ có thể tới $~ 2000^{2} \cdot 10^{6} = 4 \cdot 10^{15}$ , vượt int. Phải dùng long long và ép kiểu (long long)j * (k - j) * w trước khi nhân. Đề creatures ghi rõ "kết quả có thể vượt $2^{31} - 1$ ".
Lẫn lộn trạng thái cơ sở — Dạng 1 buộc chọn gốc nên $d p [u] [0]$ để $- \infty$ và cận $j \geq w_{u}$ ; Dạng 2 cho phép bỏ cả cây con nên $d p [u] [0] = 0$ và cận $j \geq 0$ . Đặt nhầm sẽ vi phạm ràng buộc cấu trúc (cho chọn con mà không chọn cha, hoặc ngược lại).
Phân biệt " $j$ đơn vị trọng số" với " $j$ đỉnh" — Hai họ bài dùng chiều DP khác nhau (theo trọng số $W$ hay theo số đỉnh $k$ ). Trộn lẫn (vd dùng $s z$ là số đỉnh nhưng cận theo $W$ ) gây cận sai và kết quả sai.

Biến thể / Mở rộng

DFS order + knapsack 1 chiều: Làm phẳng cây theo thứ tự DFS (tin[u], tout[u]). Với dependency knapsack, "chọn $u$ thì chọn các đỉnh trong $[t i n [u], t o u t [u]]$ "; có thể chuyển thành knapsack tuyến tính với bước "nếu bỏ $u$ thì nhảy qua cả cây con". Cách này dễ debug và tiết kiệm bộ nhớ hơn bản đệ quy hai chiều.
Liên hệ DP trên cây tổng quát: Kỹ thuật merge-as-knapsack là một trường hợp của DP trên cây. Khi $W = k$ nhỏ và $N$ lớn, có thể kết hợp small-to-large / DSU on tree để giảm hằng số.
Group knapsack: Khi mỗi đỉnh có nhiều "phương án" (vd nhiều mức đầu tư), mỗi cây con sinh ra một nhóm món, bài trở thành knapsack theo nhóm trên cây.

Bài tập luyện

Tiệc trái cây (feast) — (Advanced) Knapsack tuyến tính cơ bản, luyện trực giác "gộp hai trạng thái theo ngân sách" trước khi bê lên cây.
Sinh Vật Huyền Bí (creatures) — (Expert) Tree knapsack đúng nghĩa: chọn đúng $K$ đỉnh trên cây trọng số cạnh, tối đa tổng khoảng cách đôi — áp thẳng Dạng 3 ( $O (N K)$ , phân rã theo cạnh, nhớ long long).