Chọn đồ tối ưu bằng quy hoạch động ba lô

Lan chuẩn bị một túi cứu trợ chịu được 7 kg. Ba món có trọng lượng và giá trị lần lượt là (2, 3), (3, 4) và (4, 5). Mỗi món chỉ có một chiếc. Chọn món nào để tổng giá trị lớn nhất mà túi không quá nặng?

Mỗi món tạo ra hai lựa chọn có ràng buộc chung

Bài toán ba lô (knapsack problem) mô hình hóa việc chọn đồ dưới một giới hạn tài nguyên. Trọng lượng có thể là tiền, thời gian hoặc dung lượng. Giá trị biểu thị lợi ích cần tối đa hóa.

Với ba lô 0/1 (0/1 knapsack), mỗi món được chọn nhiều nhất một lần. Gọi n là số món và W là sức chứa. Món thứ i có trọng lượng dương w[i] và giá trị không âm v[i]. Tập rỗng được phép chọn. Tổng trọng lượng chỉ cần không vượt quá W, không bắt buộc bằng W.

Một cách thử là duyệt mọi tập món. Với ba món, có tám tập. Với 30 món, có hơn một tỷ tập. Quy hoạch động lưu kết quả của các bài toán nhỏ hơn để tránh tính lại.

Ví dụ sau duyệt các tập của ba món để kiểm chứng đáp án trước khi xây dựng bảng:

items = [(2, 3), (3, 4), (4, 5)]
best = 0
for mask in range(1 << len(items)):
    weight = value = 0
    for i, (w, v) in enumerate(items):
        if mask & (1 << i):
            weight += w
            value += v
    if weight <= 7:
        best = max(best, value)
print(best)

9

Kết quả là 9. Hai món nặng 3 và 4 vừa đủ sức chứa. Duyệt tập con tốn O(n * 2^n) thời gian và phù hợp để kiểm tra ví dụ nhỏ, không phù hợp khi n lớn.

Bảng hai chiều ghi lời giải tốt nhất cho từng tiền tố

Định nghĩa trạng thái (state) dp[i][c] là giá trị lớn nhất khi chỉ xét i món đầu và có sức chứa tối đa c. Chỉ số i đếm số món, còn món đang xét nằm tại chỉ số i - 1 trong danh sách.

Khi chưa xét món nào, dp[0][c] = 0 vì chỉ có thể chọn tập rỗng. Trọng lượng mỗi món dương nên dp[i][0] = 0. Những giá trị này phụ thuộc giả thiết: nếu đề bắt buộc chọn đúng trọng lượng, các trạng thái không đạt được không thể khởi tạo bằng 0.

Với món (w, v), nếu bỏ món thì giá trị là dp[i - 1][c]. Nếu w <= c và lấy món, phần còn lại có sức chứa c - w và chỉ được dùng các món trước. Giá trị khi đó là dp[i - 1][c - w] + v. Lấy giá trị lớn hơn trong hai lựa chọn hợp lệ.

Lập luận đúng dựa trên việc mọi tập hợp lệ hoặc chứa món hiện tại, hoặc không chứa nó. Hai nhóm này không bỏ sót cách chọn nào. Trong mỗi nhóm, lời giải tốt nhất của các món trước đã được lưu ở hàng trước.

Hình dưới ghi từng hàng của ví dụ. Cột từ trái sang phải ứng với sức chứa 0 đến 7.

Tại hàng cuối, cột 7, bỏ món 4 kg cho 7 điểm. Lấy món đó cho dp[2][3] + 5 = 9 điểm. Chương trình sau tự tính bảng thay vì nhập sẵn các ô:

items = [(2, 3), (3, 4), (4, 5)]
W = 7
dp = [[0] * (W + 1) for _ in range(len(items) + 1)]
for i, (w, v) in enumerate(items, 1):
    for c in range(W + 1):
        dp[i][c] = dp[i - 1][c]
        if w <= c:
            dp[i][c] = max(dp[i][c], dp[i - 1][c - w] + v)
for row in dp:
    print(*row)

0 0 0 0 0 0 0 0
0 0 3 3 3 3 3 3
0 0 3 4 4 7 7 7
0 0 3 4 5 7 8 9

Mỗi ô thực hiện số phép tính cố định. Có (n + 1) * (W + 1) ô, nên thời gian và bộ nhớ là O(nW). Chẳng hạn n = 100, W = 2000 tạo khoảng 200 nghìn ô. Bộ nhớ Python còn bao gồm chi phí của từng danh sách và số, nên phải xét giới hạn thật của máy chấm.

Có thể đọc bảng theo từng quyết định. Sau món đầu, mọi cột từ 2 trở lên đều đạt 3 điểm. Khi thêm món 3 kg, ô sức chứa 5 kết hợp nguồn ở cột 2 với món mới và đạt 7. Cột 4 chỉ đạt 4 vì hai món đầu cùng nặng 5. Sang món cuối, cột 6 lấy giá trị 3 từ cột 2 của hàng trước rồi cộng 5, thành 8.

Ở mỗi bước, sức chứa trong tên trạng thái là giới hạn cho phép, không phải lượng đã dùng. Chẳng hạn ô sức chứa 6 của hàng hai có giá trị 7 dù hai món chỉ nặng tổng cộng 5. Còn ô sức chứa 1 có giá trị 0 vì không món nào vừa. Điểm khác biệt này quyết định cách khởi tạo và cách đọc kết quả.

Một sai sót Python dễ gặp là tạo bảng bằng phép nhân danh sách lồng nhau. Khi đó nhiều hàng trỏ tới cùng danh sách. Ví dụ sau thay một ô và quan sát hàng còn lại:

bad = [[0] * 3] * 2
bad[1][1] = 5
print(bad[0])
good = [[0] * 3 for _ in range(2)]
good[1][1] = 5
print(good[0])

[0, 5, 0]
[0, 0, 0]

Trong bảng bad, hàng đầu cũng đổi theo hàng sau. Cách dùng biểu thức danh sách tạo từng hàng riêng, nên mỗi ô cập nhật đúng vị trí. Đây là lý do chương trình hai chiều dùng vòng lặp tạo hàng.

Truy vết bảng để tìm một tập món tối ưu

Giá trị tối ưu không cho biết cần mang món nào. Với bảng hai chiều, bắt đầu ở dp[n][W] rồi đi ngược qua các hàng. Nếu dp[i][c] bằng dp[i - 1][c], có một phương án tối ưu bỏ món i. Nếu khác, món đó phải được lấy; ghi lại nó và giảm c đi trọng lượng của món.

Khi hai lựa chọn bằng nhau, quy tắc trên ưu tiên bỏ món. Cách này vẫn cho một lời giải tối ưu, nhưng không hứa số món ít nhất hoặc thứ tự từ điển nhỏ nhất. Muốn thêm tiêu chí phụ, trạng thái và cách xử lý hòa cần phản ánh tiêu chí ấy.

items = [(2, 3), (3, 4), (4, 5)]
W = 7
dp = [[0] * (W + 1) for _ in range(len(items) + 1)]
for i, (w, v) in enumerate(items, 1):
    for c in range(W + 1):
        dp[i][c] = dp[i - 1][c]
        if c >= w:
            dp[i][c] = max(dp[i][c], dp[i - 1][c - w] + v)
chosen = []
c = W
for i in range(len(items), 0, -1):
    if dp[i][c] != dp[i - 1][c]:
        chosen.append(i)
        c -= items[i - 1][0]
chosen.reverse()
print(dp[-1][W])
print(*chosen)

9
2 3

Chương trình in giá trị 9 và số thứ tự hai món được chọn. Mỗi lần đi ngược bỏ qua đúng một hàng, nên truy vết tốn O(n) thời gian sau khi đã có bảng. Chỉ giữ một hàng sẽ tiết kiệm bộ nhớ, nhưng không còn đủ thông tin để dùng cách truy vết này trực tiếp.

Duyệt sức chứa giảm để mỗi món chỉ được dùng một lần

Hàng mới chỉ cần hàng trước, vì vậy ta thay cả bảng bằng dp[c]. Trước khi xét một món, mảng này chứa lời giải với các món cũ. Khi cập nhật từ sức chứa lớn xuống nhỏ, dp[c - w] chưa bị món hiện tại thay đổi. Nó vẫn đại diện cho hàng trước.

Khi tính ô 4, ô nguồn 2 vẫn bằng 0. Nếu duyệt tăng, ô 2 đã thành 3 và ô 4 sẽ thành 6. Kết quả 6 tương ứng dùng cùng món hai lần, trái với 0/1. Đoạn sau cho thấy hai chiều tạo kết quả khác nhau:

w, v, W = 2, 3, 4
down = [0] * (W + 1)
up = [0] * (W + 1)
for c in range(W, w - 1, -1):
    down[c] = max(down[c], down[c - w] + v)
for c in range(w, W + 1):
    up[c] = max(up[c], up[c - w] + v)
print(down[W], up[W])

3 6

range(W, w - 1, -1) có cả w vì điểm dừng không được lấy. Với món nặng hơn sức chứa, vòng lặp rỗng và món được bỏ qua. Bộ nhớ giảm xuống O(W); thời gian vẫn là O(nW).

Chương trình hoàn chỉnh sau đọc số món, sức chứa và từng cặp trọng lượng, giá trị. Nó in giá trị tối ưu, không in danh sách món.

3 7
2 3
3 4
4 5

n, W = map(int, input().split())
dp = [0] * (W + 1)
for _ in range(n):
    w, v = map(int, input().split())
    for c in range(W, w - 1, -1):
        dp[c] = max(dp[c], dp[c - w] + v)
print(dp[W])

9

Với W = 0 hoặc mọi món quá nặng, các vòng cập nhật không thay đổi kết quả 0. Hai món cùng trọng lượng và giá trị vẫn là hai món riêng, nên có thể lấy cả hai nếu đủ chỗ.

Nếu bài yêu cầu trọng lượng đúng bằng W, cần đổi ý nghĩa trạng thái. Một sức chứa chưa ghép được không thể nhận giá trị 0 như thể tập rỗng đã đạt trọng lượng đó. Với giá trị không âm, có thể dùng -1 đánh dấu trạng thái không đạt. Chỉ dp[0] nhận 0 ban đầu, và chỉ chuyển từ ô nguồn khác -1.

W = 4
items = [(3, 8)]
dp = [-1] * (W + 1)
dp[0] = 0
for w, v in items:
    for c in range(W, w - 1, -1):
        if dp[c - w] != -1:
            dp[c] = max(dp[c], dp[c - w] + v)
print(*dp)
print(dp[W])

0 -1 -1 8 -1
-1

Ô 3 có giá trị 8, nhưng ô 4 vẫn không đạt được. Nếu khởi tạo mọi ô bằng 0, ô 1 bị coi là nguồn hợp lệ và chương trình nhầm rằng có thể đạt trọng lượng 4. Dấu -1 chỉ an toàn khi điểm hợp lệ không âm. Với điểm âm, hãy dùng giá trị đánh dấu nhỏ hơn mọi kết quả hợp lệ hoặc một dấu hiệu riêng.

Duyệt tăng khi mỗi loại món có thể dùng nhiều lần

Ba lô không giới hạn (unbounded knapsack) có các loại món thay vì các món chỉ xuất hiện một lần. Với mỗi loại, ta có thể chọn bao nhiêu bản sao cũng được. Trọng lượng phải dương: nếu trọng lượng bằng 0 và giá trị dương, đáp án không bị chặn.

Giữ định nghĩa dp[c] là giá trị tốt nhất với sức chứa tối đa c. Khi đang xét một loại, duyệt c tăng từ w đến W. Nguồn dp[c - w] có thể đã chứa loại hiện tại, vì vậy thêm một bản sao là hợp lệ.

W = 7
items = [(2, 3), (3, 4)]
dp = [0] * (W + 1)
for w, v in items:
    for c in range(w, W + 1):
        dp[c] = max(dp[c], dp[c - w] + v)
print(*dp)
print(dp[W])

0 0 3 4 6 7 9 10
10

Ở sức chứa 7, hai bản sao loại 2 kg và một bản sao loại 3 kg đạt 10 điểm. Các lời giải dùng loại hiện tại ít nhất một lần đều thu được bằng cách bỏ một bản sao cuối. Phần còn lại nằm ở sức chứa nhỏ hơn và đã được tính. So sánh với phương án không thêm loại này bao phủ các khả năng.

Thời gian là O(nW) và bộ nhớ là O(W). Với 50 loại và W = 1000, có tối đa 50 nghìn lần cập nhật. Đảo chiều về giảm sẽ giới hạn mỗi loại còn một bản sao.

Tỷ lệ giá trị trên trọng lượng không đủ để chọn món 0/1

Chọn tỷ lệ cao nhất trước nghe hợp lý, nhưng một món tốt cục bộ có thể chiếm chỗ của một cặp tốt hơn. Xét sức chứa 10 và ba món (6, 12), (5, 9), (5, 9). Tỷ lệ lần lượt là 2, 1,8 và 1,8. Chọn món đầu tiên để lại 4 kg và được 12 điểm. Chọn hai món còn lại được 18 điểm.

items = [(6, 12), (5, 9), (5, 9)]
W = 10
remaining = W
greedy = 0
for w, v in sorted(items, key=lambda item: item[1] / item[0], reverse=True):
    if w <= remaining:
        remaining -= w
        greedy += v
dp = [0] * (W + 1)
for w, v in items:
    for c in range(W, w - 1, -1):
        dp[c] = max(dp[c], dp[c - w] + v)
print(greedy, dp[W])

12 18

Đoạn mã cho thấy phương pháp tỷ lệ chỉ đạt 12, còn bảng đạt 18. Quy tắc tỷ lệ có vai trò trong bài toán chia nhỏ đồ vật, nhưng đề 0/1 không cho phép chia món. Vì thế không được chuyển kết luận từ bài toán kia sang đây.

Khi sức chứa lớn, đổi trục trạng thái theo tổng giá trị

Độ phức tạp O(nW) phụ thuộc giá trị số của W, không chỉ số chữ số dùng để ghi nó. Nếu W = 10^9, một mảng có một tỷ ô không phù hợp. Khi tổng giá trị V nhỏ, có thể đổi câu hỏi: để đạt đúng giá trị x, cần trọng lượng nhỏ nhất là bao nhiêu?

Đặt cost[x] là trọng lượng nhỏ nhất để đạt đúng x bằng các món đã xét. Ban đầu cost[0] = 0; các giá trị khác chưa đạt được, biểu diễn bằng một số lớn hơn mọi tổng trọng lượng hợp lệ. Với mỗi món (w, v), duyệt x giảm rồi cập nhật từ cost[x - v] + w. Kết quả là x lớn nhất có cost[x] <= W.

items = [(8, 3), (6, 4), (5, 2)]
W = 11
V = sum(v for _, v in items)
inf = sum(w for w, _ in items) + 1
cost = [inf] * (V + 1)
cost[0] = 0
for w, v in items:
    for x in range(V, v - 1, -1):
        cost[x] = min(cost[x], cost[x - v] + w)
print(max(x for x in range(V + 1) if cost[x] <= W))

6

Ở đây món thứ hai và ba nặng 11, đạt giá trị 6. Giá trị 7 cần hai món đầu nặng 14, vượt giới hạn. Cập nhật giảm đảm bảo mỗi món chỉ tham gia một lần. Thời gian O(nV) và bộ nhớ O(V); với 100 món và tổng giá trị 1000, tối đa khoảng 100 nghìn lượt cập nhật. Cách này không phù hợp khi cả W và V đều quá lớn.

Để hiểu vì sao trạng thái này đúng, xét một tổng điểm x. Mọi cách đạt x hoặc không dùng món hiện tại, hoặc dùng nó một lần. Trong nhánh lấy, phần còn lại phải đạt đúng x - v. Trọng lượng nhỏ nhất của nhánh đó bằng trọng lượng nhỏ nhất đã biết cộng w. Chọn trọng lượng nhỏ hơn giữa hai nhánh sẽ giữ cách có nhiều chỗ trống nhất cho các món sau.

Giá trị inf trong chương trình lớn hơn tổng trọng lượng của toàn bộ các món. Vì vậy mọi cách chọn thật đều có trọng lượng nhỏ hơn inf. Một nguồn chưa đạt cộng thêm trọng lượng vẫn không tạo ra giá trị nhỏ hơn inf. Khi đọc đáp án, chỉ những ô có trọng lượng không vượt W mới được chọn. Nếu sức chứa có thể lớn hơn inf, cần kiểm tra thêm cost[x] != inf để không nhận nhầm ô chưa đạt. Một cách khác là chọn inf lớn hơn cả W lẫn tổng trọng lượng.

Chương trình dưới đây chọn cách thứ hai. Nó minh họa trường hợp sức chứa lớn hơn tổng trọng lượng, trong khi một số tổng giá trị vẫn không đạt được:

items = [(3, 2), (5, 4)]
W = 100
V = sum(v for _, v in items)
inf = max(W, sum(w for w, _ in items)) + 1
cost = [inf] * (V + 1)
cost[0] = 0
for w, v in items:
    for x in range(V, v - 1, -1):
        cost[x] = min(cost[x], cost[x - v] + w)
print([x for x in range(V + 1) if cost[x] <= W])

[0, 2, 4, 6]

Các điểm đạt được là 0, 2, 4 và 6; những điểm lẻ không thể tạo. Khi W lớn, inf = tổng trọng lượng + 1 đơn thuần vẫn nhỏ hơn W. Nếu không kiểm tra dấu chưa đạt, chương trình sẽ xem cả các ô chưa đạt là hợp lệ. Giới hạn và cách biểu diễn trạng thái phải được thiết kế cùng nhau.

Lỗi thường gặp

Tóm tắt

• Với 0/1, xét bỏ hoặc lấy một món và lấy nguồn từ các món trước.
• Bảng 2D giúp truy vết; mảng 1D tiết kiệm bộ nhớ và cần duyệt giảm.
• Với số bản sao không giới hạn, duyệt tăng để cho phép dùng lại loại hiện tại.
• Nếu tổng giá trị nhỏ hơn nhiều sức chứa, trạng thái theo giá trị có thể phù hợp hơn.

Kiểm tra nhanh

Đọc thêm

• Knapsack Problem — cp-algorithms.
• Vòng lặp và range — tài liệu Python.