Partition Equal Subset Sum

Q: Tại sao bài toán chia mảng thành hai tập con có tổng bằng nhau lại là bài toán cái túi 0/1?

Bạn lấp đầy ba lô có sức chứa target = total / 2 chính xác, mỗi giá trị chỉ dùng tối đa một lần. Chọn hoặc không chọn một giá trị là lựa chọn 0/1, và kích thước của mỗi giá trị chính là giá trị đó. Bảng các tổng có thể đạt được giúp giải bài toán trong thời gian O(n × target).

Q: Độ phức tạp thời gian của bài toán chia tập hợp thành hai tập con có tổng bằng nhau là bao nhiêu?

Thời gian O(n × target), trong đó target bằng một nửa tổng, và bộ nhớ O(target) với một hàng: khoảng 2 × 10^6 bước cho 200 giá trị, mỗi giá trị tối đa là 100. Giới hạn tăng theo kích thước của các giá trị, nên đây là thuật toán giả đa thức; bài toán tổng quát là NP-complete.

Trung bìnhQuy hoạch động

+10

Bạn nhận được một mảng nums gồm các số nguyên dương. Hãy xác định xem bạn có thể chia các giá trị thành hai nhóm có tổng bằng nhau hay không. Mỗi giá trị chỉ thuộc đúng một nhóm, và một nhóm có thể nhận các giá trị ở bất kỳ vị trí nào. Trả về true nếu có thể chia như vậy, nếu không thì trả về false.

Hàm

canPartition(nums: integer-array) → boolean

numsinteger-array: các giá trị dương để chia thành hai nhóm
Trả vềboolean: true nếu các giá trị có thể chia thành hai nhóm có tổng bằng nhau, false nếu không thể

Ràng buộc

1 ≤ nums.length ≤ 200
1 ≤ nums[i] ≤ 100

Ví dụ

Đầu vào: nums = [6, 1, 4, 9, 2]
Đầu ra: true
Giải thích: Tổng là 22, nên mỗi nhóm cần có 11. Các nhóm 9 + 2 và 6 + 1 + 4 đều có tổng bằng 11, vậy đáp án là true.

Đầu vào: nums = [4, 7, 2, 9, 6]
Đầu ra: false
Giải thích: Tổng cộng là 28, nên mỗi nhóm cần có 14. Nhóm đang có 9 cần thêm 5, nhưng không tổ hợp nào từ 4, 7, 2 và 6 tạo thành 5, nên đáp án là false dù tổng là số chẵn.

Đầu vào: nums = [1, 2, 3, 5]
Đầu ra: false
Giải thích: Tổng là 11. Hai số nguyên bằng nhau luôn có tổng là một số chẵn, vì vậy tổng lẻ không thể được chia đều và đáp án là false.

Câu hỏi mở rộng

Khi không thể chia đều, bạn có thể trả về độ chênh lệch nhỏ nhất có thể giữa tổng của hai nhóm không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Mỗi nhóm phải chứa một nửa tổng số phần tử, nên câu hỏi trở thành: có tập con nào của nums có tổng bằng target = total / 2 không? Thử mọi tập con tốn 2^n phép tính. Tuy nhiên, các tổng khá nhỏ, tối đa là 200 × 100 / 2 = 10^4, nên bảng quy hoạch động ba lô 0/1 lưu các tổng có thể đạt được sẽ trả lời câu hỏi này trong O(n × target) bước.

Thử mọi tập con bằng đệ quy

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Nếu tổng là số lẻ thì không thể chia thành hai phần bằng nhau. Nếu không, hãy chọn các giá trị cho nhóm đầu tiên đến khi tổng của chúng bằng target; các giá trị còn lại tự tạo thành nửa kia. Hàm hỗ trợ reach(i, remaining) quyết định lần lượt từng giá trị: lấy nums[i] hoặc bỏ qua nó.

Mỗi tập hợp con tương ứng với một đường đi qua các lựa chọn, vì vậy quá trình tìm kiếm không thể bỏ sót cách chia nào. Với đầu vào không thể chia thành hai phần bằng nhau, quá trình này phải duyệt qua gần như mọi đường đi, tối đa là 2^n: khoảng 10^12 với n = 40 và 1.6 × 10^60 với n = 200.

Thuật toán

Cộng các phần tử trong nums. Nếu tổng là số lẻ, trả về false.
Đặt target bằng một nửa tổng.
Viết reach(i, remaining): trả về true khi remaining bằng 0, và trả về false khi i vượt quá giá trị cuối cùng hoặc remaining nhỏ hơn 0.
Nếu không, trả về reach(i+1, remaining-nums[i]) hoặc reach(i+1, remaining): lấy giá trị đó hoặc bỏ qua nó.
Trả về reach(0, target).

def canPartition(nums):
    total = sum(nums)
    if total % 2 == 1:
        return False

    # Can some of the values from index i on add up to exactly remaining?
    def reach(i, remaining):
        if remaining == 0:
            return True
        if i == len(nums) or remaining < 0:
            return False
        # Put nums[i] in the first group, or leave it for the second one
        return reach(i + 1, remaining - nums[i]) or reach(i + 1, remaining)

    return reach(0, total // 2)

Điền vào bảng theo giá trị và tổng

Ý tưởng

reach(i, remaining) chỉ phụ thuộc vào hai con số, nên có nhiều nhất (n+1) × (target+1) câu hỏi khác nhau, khoảng 201 × 10001 ≈ 2 × 10^6. Trả lời mỗi câu hỏi một lần trong một bảng: can[i][s] cho biết liệu một số giá trị đầu tiên trong i giá trị có cộng lại bằng s hay không. Hàng 0 là false, ngoại trừ can[0][0].

Giá trị num = nums[i-1] hoặc không được chọn, khi đó các giá trị trước đó đã đạt tổng s, hoặc được chọn, khi đó chúng đạt tổng s-num. Mỗi hàng chỉ đọc hàng phía trên, nên mỗi giá trị được dùng nhiều nhất một lần. Trong ví dụ đầu tiên, các tổng có thể đạt được tăng từ {0} lên {0, 6}, {0, 1, 6, 7}, rồi thành {0, 1, 4, 5, 6, 7, 10, 11}: 6 + 1 + 4 đạt 11.

Thuật toán

Trả về false nếu tổng là số lẻ và đặt target bằng một nửa tổng đó.
Tạo một bảng có n+1 hàng và target+1 cột, tất cả đều là false, rồi đặt can[0][0] thành true.
Với mỗi hàng i từ 1 đến n, lấy num = nums[i-1].
Với mỗi tổng s từ 0 đến target, đặt can[i][s] thành can[i-1][s] hoặc, khi s ≥ num, can[i-1][s-num].
Trả về can[n][target].

def canPartition(nums):
    total = sum(nums)
    if total % 2 == 1:
        return False
    target = total // 2
    n = len(nums)

    # can[i][s] is True when some of the first i values add up to s
    can = [[False] * (target + 1) for _ in range(n + 1)]
    can[0][0] = True
    for i in range(1, n + 1):
        num = nums[i - 1]
        for s in range(target + 1):
            # Leave num out, or put it in and reach s - num with the values before it
            can[i][s] = can[i - 1][s] or (s >= num and can[i - 1][s - num])
    return can[n][target]

Một hàng phép cộng, điền từ trên xuống

Ý tưởng

Mỗi hàng chỉ đọc hàng bên trên, vì vậy hãy giữ một hàng reach và cập nhật ngay tại chỗ. Thứ tự cập nhật rất quan trọng. Duyệt s theo chiều tăng dần sẽ đọc các tổng mà giá trị này vừa bật: trong ví dụ đầu tiên, số 1 sẽ đánh dấu tổng 1, rồi đọc tổng đó để đánh dấu 2, rồi 3, như thể bạn có nhiều số 1.

Duyệt s theo chiều giảm dần từ target đến num. Khi đó, s-num là chỉ số mà giá trị này chưa chạm đến, nên reach[s-num] vẫn bằng can[i-1][s-num]. Bạn có thể dừng khi reach[target] là true, vì các giá trị về sau không bao giờ loại bỏ một tổng. Thời gian vẫn là O(n × target) và bộ nhớ giảm còn target + 1 giá trị boolean.

Thuật toán

Trả về false nếu tổng là số lẻ và đặt target bằng một nửa tổng đó.
Tạo reach với target + 1 phần tử, tất cả đều là false ngoại trừ reach[0].
Với mỗi giá trị num, duyệt s từ target giảm dần đến num và đặt reach[s] thành true khi reach[s-num] là true.
Sau mỗi giá trị, trả về true nếu reach[target] là true.
Nếu vòng lặp kết thúc, trả về reach[target], giá trị này là false.

def canPartition(nums):
    total = sum(nums)
    if total % 2 == 1:
        return False
    target = total // 2

    # reach[s] is True when some of the values seen so far add up to s
    reach = [False] * (target + 1)
    reach[0] = True
    for num in nums:
        # Walk the sums downward so num is used at most once
        for s in range(target, num - 1, -1):
            if reach[s - num]:
                reach[s] = True
        if reach[target]:
            return True
    return reach[target]

Lỗi thường gặp và trường hợp biên

Cộng dồn tổng tăng dần trong phiên bản một hàng. Với [3, 9] và mục tiêu 6, số 3 đánh dấu tổng 3 rồi đến tổng 6, và bạn trả lời đúng.
Bỏ qua bước kiểm tra số lẻ. Với [1, 2], tổng 3 được làm tròn xuống thành mục tiêu 1, giá trị 1 đạt mục tiêu đó, và bạn trả lời đúng.
Cộng mỗi giá trị vào nhóm có tổng nhỏ hơn. Với [3, 3, 2, 2, 2], cách này cho tổng 7 so với 5, trong khi 3 + 3 = 2 + 2 + 2.
Không bỏ qua giá trị lớn hơn mục tiêu, như trong [2, 2, 2, 10]. Trong R, một phạm vi như (num+1):(target+1) sẽ đếm ngược rồi làm vòng lặp bị gián đoạn.
Đọc tổng s tại chỉ số s trong Lua hoặc R, trong khi nó nằm ở s + 1.

Câu hỏi thường gặp3

Tại sao bài toán chia mảng thành hai tập con có tổng bằng nhau lại là bài toán cái túi 0/1?

Bạn lấp đầy ba lô có sức chứa target = total / 2 chính xác, mỗi giá trị chỉ dùng tối đa một lần. Chọn hoặc không chọn một giá trị là lựa chọn 0/1, và kích thước của mỗi giá trị chính là giá trị đó. Bảng các tổng có thể đạt được giúp giải bài toán trong thời gian O(n × target).

Độ phức tạp thời gian của bài toán chia tập hợp thành hai tập con có tổng bằng nhau là bao nhiêu?

Thời gian O(n × target), trong đó target bằng một nửa tổng, và bộ nhớ O(target) với một hàng: khoảng 2 × 10^6 bước cho 200 giá trị, mỗi giá trị tối đa là 100. Giới hạn tăng theo kích thước của các giá trị, nên đây là thuật toán giả đa thức; bài toán tổng quát là NP-complete.

Có thể giải bài toán phân hoạch thành hai tập con có tổng bằng nhau bằng bitset không?

Có. Hãy lưu các tổng có thể đạt được dưới dạng các bit của một số lớn, bắt đầu với bit 0 được bật. Với mỗi giá trị, bits |= bits << num cộng giá trị đó vào mọi tổng có thể đạt được cùng lúc, và đáp án là bit target. Đây là cùng một bảng, với 64 tổng trong mỗi từ máy (machine word).

def canPartition(nums):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [6, 1, 4, 9, 2]

Đầu ra mong đợi

true

Partition Equal Subset Sum

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Thử mọi tập con bằng đệ quy

Điền vào bảng theo giá trị và tổng

Một hàng phép cộng, điền từ trên xuống

Lỗi thường gặp và trường hợp biên

Câu hỏi thường gặp3

Bài tập tương tự