Chọn các số để đạt tổng mong muốn

Minh có bốn thẻ ghi 2, 3, 3 và 7 điểm. Bạn muốn đổi quà cần đúng 8 điểm, mỗi thẻ chỉ được dùng một lần. Chọn hai thẻ 2 và 3 chưa đủ; chọn 3 và 3 cũng chưa đủ. Minh cần một cách kiểm tra mọi lựa chọn mà không bỏ sót hoặc dùng lại thẻ.

Tổng tạo được là câu hỏi về những thẻ đã xét

Tổng tập con (subset sum) hỏi liệu một số phần tử được chọn có tổng bằng giá trị yêu cầu hay không. Mỗi vị trí là một thẻ riêng, kể cả khi hai thẻ ghi cùng một số. Đề có thể cho phép không chọn thẻ nào: lựa chọn đó gọi là tập rỗng (empty set) và có tổng bằng 0.

Với bốn thẻ của Minh, chương trình nhỏ sau kiểm tra một lựa chọn cụ thể. Thẻ thứ hai và thứ ba cùng mang số 3 nhưng là hai thẻ khác nhau.

cards = [2, 3, 3, 7]
chosen = [cards[0], cards[1], cards[2]]
print(chosen)
print(sum(chosen))
print(sum(chosen) == 8)

[2, 3, 3]
8
True

Có nhiều lựa chọn có thể thử. Tuy nhiên, với 40 thẻ, mỗi thẻ có hai quyết định nên có 2**40 lựa chọn, hơn một nghìn tỉ. Khi tổng cần tìm tương đối nhỏ, ta lưu kết quả theo tổng thay vì lưu từng lựa chọn.

Gọi reachable[i][s] là việc có thể tạo tổng s bằng một số trong i thẻ đầu tiên. Trạng thái cần chỉ rõ cả tập thẻ được phép dùng lẫn tổng đang xét. Khi chưa xét thẻ nào, chỉ tổng 0 tạo được. Do đó reachable[0][0] là True, còn các tổng dương là False.

Xét thẻ mới có giá trị x. Một cách tạo tổng s hoặc không lấy thẻ này, hoặc lấy nó. Trong trường hợp lấy, các thẻ trước phải tạo được s - x. Hai trường hợp bao phủ mọi lựa chọn và không đòi hỏi thẻ mới xuất hiện hai lần. Với s >= x, trạng thái mới là phép hoặc giữa hai trạng thái cũ tương ứng. Nếu s < x, chỉ có nhánh không lấy.

Hình dưới mô tả các tổng từ 0 đến 9 khi lần lượt xét các thẻ 3, 4, 5. Ô có giá trị 1 thể hiện tổng đã tạo được.

Chẳng hạn tổng 7 xuất hiện sau thẻ 4 vì tổng 3 đã có ở hàng trước. Tổng 9 xuất hiện sau thẻ 5 vì tổng 4 đã có trước đó. Không có tổng 6 vì không được chọn thẻ 3 hai lần.

Hãy đọc một ô như một câu hỏi có giới hạn rõ ràng. Sau thẻ 4, ô 7 hỏi hai thẻ đầu có tạo được 7 hay không. Nhánh lấy thẻ 4 nhìn vào tổng 3 ở hàng trước và tìm thấy thẻ 3. Ngược lại, ô 6 nhìn vào tổng 2 ở hàng trước, vốn chưa tạo được. Nhánh không lấy cũng không có tổng 6, nên ô đó vẫn sai. Hai nhánh bao phủ mọi lựa chọn, thay vì chỉ thử một cách có vẻ hợp lý.

Một tổng có thể có nhiều tập thẻ tạo ra. Bảng đúng sai chỉ lưu việc có ít nhất một tập, không lưu số lượng. Khi đề hỏi số cách, trạng thái và phép gộp phải thay đổi.

Ta có thể giữ bảng hai chiều để nhìn rõ các hàng. Chương trình dưới in các tổng có thể tạo sau mỗi lượt, không cần đoán kết quả bằng tay.

cards = [3, 4, 5]
target = 9
rows = [[False] * (target + 1) for _ in range(len(cards) + 1)]
rows[0][0] = True
for i, x in enumerate(cards, 1):
    for s in range(target + 1):
        rows[i][s] = rows[i - 1][s]
        if s >= x:
            rows[i][s] = rows[i][s] or rows[i - 1][s - x]
for i, row in enumerate(rows):
    print(i, [s for s, ok in enumerate(row) if ok])

0 [0]
1 [0, 3]
2 [0, 3, 4, 7]
3 [0, 3, 4, 5, 7, 8, 9]

Mỗi hàng có target + 1 ô. Với n thẻ, bảng dùng O(n * target) bộ nhớ và xét O(n * target) trạng thái. Đối với 100 thẻ và đích 2 000, có khoảng 200 000 lần xét, chưa kể khởi tạo. Bảng này thuận tiện khi cần giữ lịch sử, nhưng chỉ hàng ngay trước cần cho quyết định tiếp theo.

Duyệt tổng giảm để mỗi thẻ chỉ xuất hiện một lần

Ta thay hai hàng bằng một danh sách dp. Trước khi xử lý thẻ x, dp[s] cho biết tổng s có tạo được bằng các thẻ đã xét hay chưa. Sau lượt đó, dp[s] phải phản ánh cả lựa chọn lấy và không lấy x.

Hãy xét riêng thẻ có giá trị 3. Khi cập nhật tổng 6, ta cần giá trị cũ của dp[3], trước khi thẻ 3 được dùng. Nếu duyệt từ 9 xuống 3, ô 6 được xét trước ô 3. Vì thế ô nguồn chưa bị lượt hiện tại thay đổi.

Ngược lại, duyệt tăng sẽ bật ô 3 trước. Khi tới ô 6, chương trình nhìn thấy ô 3 vừa bật và vô tình dùng chính thẻ đó thêm lần nữa. Đoạn dưới chạy cả hai hướng trên cùng một thẻ để so sánh.

target = 6
x = 3
descending = [False] * (target + 1)
ascending = [False] * (target + 1)
descending[0] = ascending[0] = True
for s in range(target, x - 1, -1):
    descending[s] = descending[s] or descending[s - x]
for s in range(x, target + 1):
    ascending[s] = ascending[s] or ascending[s - x]
print("giảm:", descending[6])
print("tăng:", ascending[6])

giảm: False
tăng: True

Hướng tăng phù hợp với một số bài được phép dùng lại phần tử, nhưng trả lời câu hỏi khác. Ở đây, sau mỗi lượt, bất biến là dp[s] đúng khi và chỉ khi một tập các thẻ đã xét có tổng s. Ban đầu bất biến đúng với tập rỗng. Mỗi lần cập nhật giữ phương án không lấy và thêm chính xác các phương án lấy một thẻ mới. Suy ra nó vẫn đúng sau mọi lượt.

Chương trình đầy đủ sau đọc số thẻ và tổng cần đạt. Giả sử mọi giá trị không âm, nên một tổng đã vượt đích không thể giảm về đích bằng các thẻ còn lại.

4 8
2 3 3 7

n, target = map(int, input().split())
cards = list(map(int, input().split()))
dp = [False] * (target + 1)
dp[0] = True
for x in cards:
    for s in range(target, x - 1, -1):
        dp[s] = dp[s] or dp[s - x]
print("YES" if dp[target] else "NO")

YES

Với n = 100 và target = 2 000, tối đa khoảng 200 000 lượt cập nhật. Bộ nhớ của mảng là O(target) và thời gian là O(n * target). Kích thước của số đích ảnh hưởng trực tiếp tới thời gian, không chỉ số chữ số của nó. Vì vậy, đây là thuật toán giả đa thức (pseudo-polynomial).

Một thẻ lớn hơn đích không được chọn trong lời giải với dữ liệu không âm. Vòng range tương ứng rỗng nên không sửa bảng. Nếu đích bằng 0, tập rỗng cho câu trả lời có, kể cả khi mọi thẻ đều dương. Nếu đề đòi chọn ít nhất một thẻ, phải lưu thêm thông tin khác; không thể dùng dp[0] một mình để phân biệt.

Đếm tập con theo vị trí thay vì chỉ ghi có hay không

Nếu cần biết có bao nhiêu cách, thay trạng thái đúng sai bằng count[s]: số tập chỉ số đã xét có tổng s. Khởi tạo count[0] = 1 vì có đúng một cách chọn từ không thẻ: tập rỗng. Các ô còn lại bắt đầu bằng 0.

Khi xét thẻ x, mỗi cách cũ tạo s - x sinh một cách mới tạo s bằng cách thêm thẻ đó. Các cách không lấy thẻ đã có trong count[s]. Vì vậy ta cộng count[s - x] vào count[s] và vẫn duyệt giảm.

cards = [2, 3, 3, 7]
target = 8
count = [0] * (target + 1)
count[0] = 1
for x in cards:
    for s in range(target, x - 1, -1):
        count[s] += count[s - x]
print(count[target])
print(count[3])

1
2

Hai thẻ 3 tạo hai cách chọn tổng 3 vì vị trí khác nhau. Với tổng 8, hai thẻ 3 đều cần thiết cùng thẻ 2. Nếu đề xem các thẻ bằng nhau là không phân biệt, quy tắc đếm này không còn phù hợp; phải đổi định nghĩa cách chọn trước khi viết chuyển trạng thái.

Số cách có thể lớn đến 2**n. Nếu đề yêu cầu lấy phần dư theo một mô-đun, hãy lấy dư sau mỗi phép cộng. Đáp số khi đó là phần dư, không phải số cách đầy đủ. Đừng dùng số dư bằng 0 để kết luận không tồn tại: số cách thật có thể là bội của mô-đun.

Giá trị 0 cần được xét kỹ. Với mỗi tập cũ, ta có hai lựa chọn khác nhau: lấy hoặc bỏ thẻ 0. Cả hai giữ nguyên tổng nên số cách tăng gấp đôi. Duyệt giảm vẫn đúng vì mỗi ô chỉ được cập nhật một lần trong lượt của thẻ 0.

cards = [0, 0, 2]
target = 2
count = [0] * (target + 1)
count[0] = 1
for x in cards:
    for s in range(target, x - 1, -1):
        count[s] += count[s - x]
    print(x, count)

0 [2, 0, 0]
0 [4, 0, 0]
2 [4, 0, 4]

Hai thẻ 0 là hai vị trí độc lập. Sau khi xét chúng, có bốn cách chọn tổng 0. Khi thêm thẻ 2, cả bốn cách ấy đều mở rộng thành cách có tổng 2. Với trạng thái đúng sai, thẻ 0 không tạo tổng mới, nhưng trong bài đếm nó làm thay đổi đáp án.

Đổi bài toán gán dấu thành đếm một tập con

Giả sử mỗi thẻ không âm phải mang dấu cộng hoặc trừ và tổng cần đạt là T. Gọi tổng tất cả thẻ là total và tổng các thẻ mang dấu cộng là P. Các thẻ còn lại có tổng total - P, nên tổng có dấu bằng P - (total - P) = 2 * P - total. Vì vậy P = (total + T) // 2.

Trước khi đếm, kiểm tra abs(T) <= total và total + T chẵn. Nếu một điều kiện không thỏa thì không có cách nào. Mỗi tập chỉ số mang dấu cộng tương ứng với đúng một cách gán dấu. Thẻ 0 vẫn có hai dấu, nên phép đếm phải nhân đôi số cách khi xét nó.

cards = [0, 2, 3]
target = -1
total = sum(cards)
if abs(target) > total or (total + target) % 2:
    print(0)
else:
    goal = (total + target) // 2
    count = [0] * (goal + 1)
    count[0] = 1
    for x in cards:
        for s in range(goal, x - 1, -1):
            count[s] += count[s - x]
    print(count[goal])

2

Với 80 thẻ và tổng không quá 4 000, đích đếm tối đa 4 000. Chi phí tối đa là O(n * total) thời gian và O(total) bộ nhớ. Nếu đề yêu cầu phần dư, lấy dư trong từng lượt cộng.

Phân hoạch hai nhóm bằng cách chọn một phía

Giả sử cần chia mọi thẻ không âm vào hai nhóm. Gọi tổng tất cả thẻ là total và tổng nhóm thứ nhất là s. Nhóm còn lại có tổng total - s, nên độ lệch là abs(total - 2 * s). Một tập con xác định nhóm thứ nhất, còn mọi thẻ chưa chọn thuộc nhóm kia.

Nếu cần hai nhóm bằng nhau, total phải chẵn và có thể tạo tổng total // 2. Điều kiện chẵn là cần nhưng chưa đủ. Chẳng hạn tổng 10 là chẵn, nhưng các thẻ 2 và 8 không tạo được 5.

for cards in ([2, 8], [1, 2, 3, 6]):
    total = sum(cards)
    half = total // 2
    dp = [False] * (half + 1)
    dp[0] = True
    for x in cards:
        for s in range(half, x - 1, -1):
            dp[s] = dp[s] or dp[s - x]
    print(cards, total % 2 == 0 and dp[half])

[2, 8] False
[1, 2, 3, 6] True

Khi cần độ lệch nhỏ nhất, chỉ cần xét các tổng không vượt quá một nửa. Nếu một lựa chọn có tổng lớn hơn một nửa, phần bù của nó có tổng nhỏ hơn một nửa và cùng độ lệch. Trong nửa dưới, tổng càng lớn thì total - 2 * s càng nhỏ. Vì vậy ta tìm tổng tạo được lớn nhất không vượt quá total // 2.

4
2 3 3 7

n = int(input())
cards = list(map(int, input().split()))
total = sum(cards)
half = total // 2
dp = [False] * (half + 1)
dp[0] = True
for x in cards:
    for s in range(half, x - 1, -1):
        dp[s] = dp[s] or dp[s - x]
best = max(s for s in range(half + 1) if dp[s])
print(total - 2 * best)

1

Với dữ liệu này, tổng là 15 và nửa dưới dừng ở 7. Có thể tạo 7 bằng một thẻ hoặc bằng 2 + 3 + 3. Do đó độ lệch nhỏ nhất là 1. Nếu đề yêu cầu cả hai nhóm đều không rỗng, cần trạng thái hoặc kiểm tra bổ sung; tập rỗng có thể là đáp án ở công thức hiện tại.

Thời gian là O(n * total), bộ nhớ là O(total), tính theo nửa tổng với hệ số hằng. Ví dụ 80 thẻ có tổng 4 000 cho tối đa khoảng 160 000 lần cập nhật. Ngược lại, một thẻ mang giá trị hàng tỉ khiến mảng theo tổng không thực tế, dù chỉ có vài thẻ.

Dùng số nguyên làm dãy bit

Một dãy bit (bitset) có thể lưu nhiều trạng thái đúng sai trong một số nguyên không âm mask. Bit thứ s bằng 1 khi tổng s đạt được. Ban đầu mask = 1, chỉ bật bit 0. Dịch trái mask << x đưa mỗi bit cũ từ s sang s + x, ứng với việc lấy thẻ x. Phép hoặc giữ cả các tổng cũ và tổng mới: mask |= mask << x.

Vế phải được tính từ mask trước khi gán, nên mỗi thẻ chỉ được thêm một lần trong lượt đó. Thẻ 0 không tạo tổng mới. Dãy bit chỉ lưu khả năng tồn tại, không lưu số cách. Đoạn sau so sánh chính xác các tổng với mảng quen thuộc.

cards = [3, 4, 5]
limit = sum(cards)
mask = 1
dp = [False] * (limit + 1)
dp[0] = True
for x in cards:
    mask |= mask << x
    for s in range(limit, x - 1, -1):
        dp[s] = dp[s] or dp[s - x]
bit_sums = [s for s in range(limit + 1) if (mask >> s) & 1]
array_sums = [s for s in range(limit + 1) if dp[s]]
print(bit_sums)
print(array_sums)
print(bit_sums == array_sums)

[0, 3, 4, 5, 7, 8, 9, 12]
[0, 3, 4, 5, 7, 8, 9, 12]
True

Để tìm tổng lớn nhất không vượt half, giữ các bit từ 0 đến half bằng mask & ((1 << (half + 1)) - 1). Kết quả có ít nhất bit 0, nên bit_length() - 1 cho vị trí bit bật lớn nhất. Dịch và hoặc làm việc theo các khối bit nội bộ, thay cho một vòng Python với từng tổng. Với 1 000 thẻ và tổng tối đa 1 000 000, mỗi lượt xử lý tối đa khoảng một triệu bit. Chi phí và bộ nhớ vẫn tăng theo tổng, nên cần đo trong giới hạn máy chấm.

Khôi phục thẻ đã chọn bằng dấu vết khi tổng xuất hiện

Câu trả lời đúng sai không cho biết thẻ nào được chọn. Nếu cần một lời giải cụ thể, khi một tổng s xuất hiện lần đầu, lưu chỉ số thẻ tạo ra nó. Đồng thời lưu tổng trước đó là s - x. Chỉ ghi khi dp[s] đang sai và dp[s - x] đang đúng.

Nhờ duyệt giảm, tổng nguồn thuộc lượt trước và không cần chính thẻ hiện tại. Mỗi liên kết lùi lại một lượt hoặc nhiều hơn. Khi các giá trị đều dương, tổng cũng giảm ở mỗi bước, nên quá trình truy vết dừng ở 0.

cards = [3, 4, 5]
target = 9
dp = [False] * (target + 1)
parent = [None] * (target + 1)
dp[0] = True
for i, x in enumerate(cards):
    for s in range(target, x - 1, -1):
        if not dp[s] and dp[s - x]:
            dp[s] = True
            parent[s] = (s - x, i)
if not dp[target]:
    print("không có")
else:
    chosen = []
    s = target
    while s > 0:
        s, i = parent[s]
        chosen.append(i)
    chosen.reverse()
    print("chỉ số:", chosen)
    print("giá trị:", [cards[i] for i in chosen])

chỉ số: [1, 2]
giá trị: [4, 5]

Chỉ số giúp phân biệt các thẻ trùng giá trị. Khi đích là 0, thuật toán trả về tập rỗng. Thẻ 0 không cần cho một lời giải tồn tại và không tạo liên kết mới theo điều kiện trên. Nếu đề muốn liệt kê mọi cách hoặc tối ưu số thẻ, một dấu vết cho mỗi tổng là chưa đủ.

Số âm cần khoảng trạng thái và lượt riêng

Cắt bảng ở đích dựa vào giả thiết các thẻ không âm. Với thẻ âm, một tổng vượt đích vẫn có thể quay lại sau khi cộng số âm. Ví dụ, để tạo 4 từ 9 và -5, phải giữ tổng trung gian 9. Cập nhật tại chỗ còn có nguy cơ đọc chỉ số âm hoặc dùng lại phần tử do hướng phụ thuộc dấu.

Một cách dễ kiểm chứng là lưu tập các tổng và tạo tập mới ở mỗi lượt. Tập mới gồm tổng cũ và tổng cũ cộng thẻ mới. Vì chỉ đọc từ tập cũ, mỗi thẻ được dùng nhiều nhất một lần.

cards = [9, -5]
reachable = {0}
for x in cards:
    reachable = reachable | {s + x for s in reachable}
    print(sorted(reachable))
print(4 in reachable)

[0, 9]
[-5, 0, 4, 9]
True

Cách này không bảo đảm nhanh khi có nhiều tổng khác nhau. Nếu lo là tổng các số âm và hi là tổng các số dương, mọi tổng nằm trong [lo, hi]. Mảng hai hàng với độ lệch chỉ số cũng làm được, nhưng chi phí phụ thuộc hi - lo + 1. Khi khoảng này quá lớn, cần chọn kỹ thuật khác theo giới hạn đề.

Chẳng hạn khi chỉ có khoảng 30 phần tử nhưng giá trị rất lớn, có thể cân nhắc chia dãy làm hai nửa và ghép các tổng. Số phương án mỗi nửa xấp xỉ 2**15; việc ghép cần thêm cấu trúc tìm kiếm phù hợp. Đừng áp dụng máy móc mảng kích thước bằng tổng khi bộ nhớ không cho phép.

Lỗi thường gặp

Tóm tắt

• Với thẻ không âm dùng một lần, lưu tổng tạo được và cập nhật giảm theo tổng.
• Khởi tạo tổng 0 từ tập rỗng. Đếm số cách thì bắt đầu bằng một cách, không phải một giá trị đúng sai.
• Bài chia nhóm trở thành tìm tổng tập con gần một nửa tổng nhất.
• Chi phí phụ thuộc giới hạn tổng; số âm hoặc yêu cầu tập không rỗng cần mô hình phù hợp.

Kiểm tra nhanh

Đọc thêm

• Quy hoạch động túi đồ 0/1 và thứ tự cập nhật.
• Các kiểu dữ liệu và phép toán trên số nguyên trong Python.