Bài toán cái túi — 0/1 Knapsack, Unbounded và tối ưu không gian

TL;DR: Bài toán cái túi (knapsack) hỏi: chọn tập items sao cho tổng weight không vượt W và tổng value lớn nhất. Với 0/1 knapsack (mỗi item dùng tối đa 1 lần), DP 2D dp[i][w] = giá trị tốt nhất khi xét i items đầu, sức chứa w. Transition: chọn hoặc không chọn item thứ i. Tối ưu 1D bằng cách duyệt w từ W xuống 0. Greedy (chọn theo value/weight ratio) sai với 0/1 knapsack — counter-example đơn giản bác bỏ.

Một công ty logistics phải chọn đơn hàng nào để xếp vào chuyến xe tải 1.000 kg cuối ngày. Mỗi đơn hàng có trọng lượng và lợi nhuận riêng. Mục tiêu: tối đa hoá lợi nhuận mà không vượt tải trọng. Không thể chia nhỏ đơn hàng — mỗi đơn hoặc lấy hết hoặc bỏ qua. Đây chính xác là cấu trúc của 0/1 Knapsack.

Bài toán xuất hiện ở khắp nơi: danh mục đầu tư (chọn dự án với ngân sách cố định), bộ nhớ cache (quyết định object nào giữ trong RAM), scheduling (chọn task nào làm trong giờ làm việc). Hiểu Knapsack là hiểu nguyên mẫu của một lớp bài toán tối ưu rời rạc.

1. Analogy — Packer thông minh so với packer tham lam

Hãy tưởng tượng hai nhân viên xếp hàng vào kho:

• Packer tham lam luôn chọn món hàng có tỷ lệ value/weight cao nhất. Nghe có lý, nhưng hay bị kẹt: chọn món đắt-nặng-vừa rồi không còn chỗ cho hai món nhẹ-rẻ mà tổng cộng lại còn lời hơn.
• Packer DP tư duy khác: "Nếu còn w kg, và tôi đang xem xét item thứ i, thì lựa chọn tối ưu là gì?" Mỗi quyết định nhỏ được lưu lại, dùng để xây dựng quyết định lớn hơn.

2. Phát biểu bài toán và ký hiệu

Cho n items, mỗi item i có:

• weight[i]: trọng lượng (số nguyên dương)
• value[i]: giá trị (số nguyên dương)

Và sức chứa tối đa W. Tìm tập con items có tổng weight không vượt W và tổng value lớn nhất.

0/1 knapsack: mỗi item dùng tối đa 1 lần (lấy hoặc bỏ). Unbounded knapsack: mỗi item có thể dùng nhiều lần tùy ý.

3. Cơ chế — DP 2D cho 0/1 Knapsack

3.1 Định nghĩa subproblem

dp[i][w] = giá trị tối đa có thể đạt được khi xét i items đầu tiên (items 1..i), với sức chứa còn lại là w.

Base case:

• dp[0][w] = 0 với mọi w — chưa xét item nào, value = 0
• dp[i][0] = 0 với mọi i — sức chứa 0, không thể lấy gì

Recurrence (transition):

Với mỗi item i và sức chứa w:

• Nếu weight[i] > w: không thể lấy item i → dp[i][w] = dp[i-1][w]
• Nếu weight[i] <= w: có thể lấy hoặc không lấy item i
  • Không lấy: dp[i-1][w]
  • Lấy: value[i] + dp[i-1][w - weight[i]]
  • Chọn max: dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w - weight[i]])

Knapsack_2D(weight[], value[], n, W):
    dp[0..n][0..W] <- 0    -- khởi tạo tất cả bằng 0

    for i <- 1 đến n:
        for w <- 0 đến W:
            dp[i][w] <- dp[i-1][w]    -- mặc định: không lấy item i
            if weight[i] <= w:
                dp[i][w] <- max(dp[i][w],
                                value[i] + dp[i-1][w - weight[i]])
                -- so sánh: lấy vs không lấy item i

    return dp[n][W]    -- đáp án cuối cùng

Time: O(n × W)  Space: O(n × W)

3.2 Trace ví dụ — 4 items, W = 5

Bảng dp[i][w] (i = item 0-4, w = 0-5):

      w=0  w=1  w=2  w=3  w=4  w=5
i=0:   0    0    0    0    0    0
i=1:   0    1    1    1    1    1     (item1: w=1,v=1)
i=2:   0    1    6    7    7    7     (item2: w=2,v=6)
i=3:   0    1    6   10   11   16    (item3: w=3,v=10)
i=4:   0    1   16   17   22   26    (item4: w=2,v=16)

Đáp án: dp[4][5] = 26 — lấy item 3 (w=3,v=10) + item 4 (w=2,v=16) = 26. Sức chứa dùng: 5/5.

Thử ngẫmcông ty logistics ở đầu bài đổi luật — cho phép xếp một phần đơn hàng (chia nhỏ được). Bảng dp[i][w] vừa trace ở trên còn áp dụng đúng không?

4. Tối ưu không gian — 2D xuống 1D

Nhận xét: dp[i][w] chỉ phụ thuộc vào hàng dp[i-1][...]. Không cần giữ toàn bộ bảng 2D — chỉ cần 1 mảng 1D, cập nhật tại chỗ.

Trick quan trọng: duyệt w từ W xuống 0 (ngược chiều). Điều này đảm bảo khi cập nhật dp[w], giá trị dp[w - weight[i]] vẫn là của hàng i-1 (chưa bị ghi đè bởi item i trong vòng lặp hiện tại).

Knapsack_1D(weight[], value[], n, W):
    dp[0..W] <- 0    -- mảng 1D, khởi tạo 0

    for i <- 1 đến n:
        for w <- W xuống weight[i]:    -- QUAN TRỌNG: duyệt ngược
            dp[w] <- max(dp[w],
                         value[i] + dp[w - weight[i]])
            -- dp[w]: không lấy item i (giá trị từ vòng lặp trước)
            -- value[i] + dp[w-weight[i]]: lấy item i

    return dp[W]

Time: O(n × W)  Space: O(W)

Chạy thử trên chính bảng ở mục 3.2 thì "vô tình lấy nhiều lần" hiện ra thành một con số. Hàng trước khi xét item 4 là [0, 1, 6, 10, 11, 16]. Duyệt xuôi: tới lượt tính dp[4], ô dp[2] đã bị chính item 4 ghi đè thành 16, nên dp[4] = 16 + 16 = 32 — tức 4 kg toàn item 4, mà item 4 chỉ nặng 2 kg. Duyệt ngược: dp[4] được tính trước dp[2], nên dp[2] còn nguyên giá trị 6 của hàng i−1, và dp[4] = 16 + 6 = 22. Cùng dữ liệu, đổi mỗi hướng duyệt.

Thử ngẫmnếu code review của bạn thấy vòng lặp w duyệt xuôi từ 0 lên W trong một hàm gắn nhãn "0/1 knapsack", bug đó gây hậu quả gì trên input thực tế?

5. Greedy sai — counter-example

Greedy cho 0/1 knapsack: chọn items theo thứ tự value/weight giảm dần cho đến khi túi đầy.

Counter-example W = 10:

Greedy chọn A (ratio 2.0, weight 6), còn 4 kg — B và C đều nặng 5 kg, không vào được. Kết quả: value = 12.

DP tối ưu: bỏ qua A, lấy B + C (5 + 5 = 10 kg = W). Kết quả: value = 20.

Greedy cho 12, DP cho 20 — greedy kém hơn 40%. Greedy bị lừa bởi item A "tốt nhất" nhưng chiếm quá nhiều chỗ, chặn kết hợp tốt hơn.

6. Unbounded Knapsack

Mỗi item có thể được lấy nhiều lần tùy ý. Transition thay đổi:

UnboundedKnapsack(weight[], value[], n, W):
    dp[0..W] <- 0

    for w <- 1 đến W:
        for i <- 1 đến n:
            if weight[i] <= w:
                dp[w] <- max(dp[w],
                             value[i] + dp[w - weight[i]])
                -- dp[w - weight[i]]: lấy item i lần này,
                -- nhưng dp[...] đã được tính với w tăng dần
                -- => item i có thể được lấy lần tiếp theo

    return dp[W]

Time: O(n × W)  Space: O(W)

Khác biệt cốt lõi: với 0/1 knapsack, duyệt w từ W xuống để tránh dùng item nhiều lần. Với unbounded, duyệt w từ 1 lên để cho phép dùng item nhiều lần — dp[w - weight[i]] đã bao gồm giá trị lấy item i trước đó.

Ứng dụng unbounded: Coin change (số lần dùng mỗi mệnh giá không giới hạn — xem liên hệ bên dưới), rod cutting (cắt thanh kim loại thành các đoạn dài bất kỳ), word break (dùng từ trong từ điển nhiều lần).

Thử ngẫmrod cutting cho phép cắt một thanh thành các đoạn dài tuỳ ý, dùng lại cùng độ dài nhiều lần. Vì sao đây là unbounded chứ không phải 0/1 knapsack?

7. Liên hệ các bài khác

• DP Framework: Knapsack là ví dụ kinh điển của DP — bài này bổ sung concrete implementation sau khi bạn đọc framework tổng quát về subproblem, transition, base case.
• Greedy — tham lam có chứng minh: Bài tiếp theo giải thích vì sao greedy đúng với Fractional Knapsack và Interval Scheduling, và cách chứng minh bằng exchange argument — đối chiếu trực tiếp với counter-example ở bài này.
• Coin Change — unbounded variant: Bài toán đếm số đồng xu tối thiểu để ra đúng số tiền là unbounded knapsack với value = 1 cho mọi coin — cùng template dp[w] = min(dp[w], 1 + dp[w - coin[i]]), chỉ đổi từ max sang min và thêm 1 thay vì value[i].
• Hàng đợi ưu tiên: Greedy cho fractional knapsack dùng priority queue sort theo ratio — hiểu heap giúp implement greedy variant hiệu quả O(n log n).

8. Deep Dive

9. Tóm tắt

• 0/1 Knapsack: dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w - weight[i]]) — xét từng item, với từng sức chứa, chọn max giữa lấy và không lấy.
• Tối ưu 1D: duyệt w từ W xuống 0 trong vòng lặp item — đảm bảo mỗi item chỉ được dùng một lần.
• Unbounded: duyệt w từ 1 lên W — dp[w - weight[i]] đã bao gồm giá trị từ lần lấy trước của item i.
• Greedy sai với 0/1: counter-example W=10, items {(6,12),(5,10),(5,10)} — greedy cho 12, DP cho 20. Greedy đúng với fractional knapsack (items chia được).
• Complexity: O(n × W) time, O(W) space sau tối ưu 1D. Pseudo-polynomial — không polynomial theo kích thước input thực.

10. Tự kiểm tra

Bài tiếp theo: Greedy — tham lam có chứng minh