Subset Sum Problem

Q: Subset Sum liên quan thế nào đến Partition Equal Subset Sum và bài toán ba lô 0/1?

Partition Equal Subset Sum là Subset Sum với target = total / 2 , sau khi kiểm tra tổng có phải số chẵn hay không. Subset Sum là bài toán ba lô 0/1, trong đó mỗi giá trị cũng chính là trọng lượng của nó và ba lô phải được lấp đầy chính xác, vì vậy bảng lưu các giá trị đúng hoặc sai thay vì các giá trị tốt nhất.

Q: Làm thế nào để tìm các giá trị tạo thành mục tiêu?

Giữ nguyên toàn bộ bảng và bắt đầu tại made[n][target] . Đi lên từng hàng một: nếu made[i-1][s] là true, thì không cần dùng nums[i-1] ; nếu không, hãy ghi lại số đó và trừ nó khỏi s . Bạn dừng lại khi tổng bằng 0 và đã chọn được một cách hợp lệ.

Trung bìnhQuy hoạch động

+10

nums chứa các số nguyên dương, còn target là một số nguyên dương. Bạn có thể chọn một số giá trị, mỗi vị trí chỉ chọn tối đa một lần, sao cho tổng của chúng bằng chính xác target không? Trả về true nếu có thể, và false nếu không có cách chọn nào phù hợp.

Hàm

isSubsetSum(nums: integer-array, target: integer) → boolean

numsinteger-array: các giá trị dương bạn có thể chọn
targetinteger: tổng chính xác mà các giá trị được chọn phải đạt tới
Trả vềboolean: true khi một số giá trị cộng lại đúng bằng target, false nếu không

Ràng buộc

1 ≤ nums.length ≤ 200
1 ≤ nums[i] ≤ 10⁴
1 ≤ target ≤ 10⁴

Ví dụ

Đầu vào: nums = [8, 3, 11, 5, 7]target = 15
Đầu ra: true
Giải thích: 8 + 7 = 15, nên đáp án là true. Lựa chọn 3 + 5 + 7 cũng đúng; chỉ cần một lựa chọn là đủ.

Đầu vào: nums = [6, 9, 12, 15]target = 20
Đầu ra: false
Giải thích: Mọi giá trị đều là bội số của 3, vì vậy tổng của chúng cũng là bội số của 3. 20 không phải là bội số của 3, nên đáp án là false.

Đầu vào: nums = [4, 1, 2]target = 8
Đầu ra: false
Giải thích: Cả ba giá trị cộng lại là 4 + 1 + 2 = 7, nhỏ hơn 8, nên không thể chọn được giá trị nào đạt đến đó và đáp án là false.

Câu hỏi mở rộng

Hai giá trị bằng nhau ở các vị trí khác nhau được tính là hai lựa chọn riêng biệt. Có bao nhiêu lựa chọn đạt đến target?

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 giá trị tương ứng với một lựa chọn có hoặc không, nên 200 giá trị tạo ra 2^200 lựa chọn. Tuy nhiên, chỉ cần quan tâm đến các tổng không vượt quá target ≤ 10^4. Hãy ghi lại những tổng có thể tạo thành từ các giá trị đã xét: mỗi giá trị mới dịch chuyển bản ghi đó theo độ lớn của nó, và bài toán tìm kiếm trở thành một bảng gồm n × target giá trị đúng hoặc sai.

Lấy hoặc bỏ qua từng giá trị

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

Ý tưởng

canMake(i, remaining) hỏi liệu các giá trị từ vị trí i trở đi có thể tạo thành đúng remaining hay không. Chọn nums[i] nếu phù hợp, khi đó phần còn lại là remaining-nums[i]; nếu không được thì bỏ qua nó. Mỗi lựa chọn tạo thành một đường đi, vì vậy quá trình tìm kiếm sẽ tìm thấy một lựa chọn nếu có.

Khi không có lựa chọn nào phù hợp, thuật toán sẽ duyệt tất cả. Với 200 bội số của 3, mỗi số tối đa là 300, và mục tiêu là 9998, không lựa chọn nào phù hợp, nhưng bất kỳ 33 giá trị nào cũng có tổng nhỏ hơn mục tiêu: hơn 10^37 đường đi.

Thuật toán

Viết canMake(i, remaining).
remaining bằng 0 nghĩa là đã chọn xong: trả về true. Nếu không còn giá trị nào mà vẫn còn mục tiêu cần đạt, trả về false.
Nếu nums[i] ≤ remaining và canMake(i+1, remaining-nums[i]) là true, trả về true.
Nếu không, trả về canMake(i+1, remaining).
Trả về canMake(0, target).

def isSubsetSum(nums, target):
    n = len(nums)

    # Can some of nums[i], nums[i+1], ... add up to exactly remaining?
    def can_make(i, remaining):
        if remaining == 0:
            return True
        if i == n:
            return False
        if nums[i] <= remaining and can_make(i + 1, remaining - nums[i]):
            return True  # take nums[i]
        return can_make(i + 1, remaining)  # skip it

    return can_make(0, target)

Điền vào bảng các tổng có thể đạt được

Ý tưởng

Đệ quy (recursion) chỉ phụ thuộc vào một vị trí và tổng còn lại từ 0 đến target, và nhiều đường đi dẫn đến cùng một cặp giá trị. Thay vào đó, hãy điền một bảng. made[i][s] là true khi chọn một số trong i giá trị đầu tiên có tổng chính xác bằng s; trường hợp không chọn số nào tạo ra tổng 0. Với num = nums[i-1], tổng s được tạo ra nếu tổng đó đã được tạo ra mà không cần num, tức là made[i-1][s], hoặc nếu num hoàn thành tổng s-num, tức là made[i-1][s-num] khi s ≥ num.

Trong ví dụ đầu tiên, sau số 8, các tổng tạo được là 0 và 8. Số 3 tạo thêm 3 và 11, số 11 chỉ tạo thêm 14, số 5 tạo thêm 5 và 13, còn 8 + 7 đạt được 15. Với các giới hạn đã cho, bảng có 201 × 10001 ô, tương đương khoảng 2 × 10^6 bước.

Thuật toán

Cấp phát made gồm n+1 hàng và target+1 giá trị boolean, tất cả đều là false. Đánh dấu made[0][0] là true cho lựa chọn rỗng.
Hàng i xử lý giá trị num = nums[i-1], với i từ 1 đến n.
Với mỗi tổng s từ 0 đến target, đặt made[i][s] bằng made[i-1][s].
Nếu s ≥ num và made[i-1][s-num] là true, đặt made[i][s] thành true.
Trả về made[n][target].

def isSubsetSum(nums, target):
    n = len(nums)
    # made[i][s]: some of the first i values add up to exactly s
    made = [[False] * (target + 1) for _ in range(n + 1)]
    made[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 on top of a sum of s-num
            made[i][s] = made[i - 1][s] or (s >= num and made[i - 1][s - num])
    return made[n][target]

Một hàng phép cộng, được cập nhật từ trên xuống

Ý tưởng

Mỗi hàng chỉ đọc hàng ngay trước nó, nên một mảng (array) made[s] có thể chứa dữ liệu đó. Nếu ghi đè theo chiều tăng dần, một giá trị sẽ tự dùng chính nó: với nums = [5] và mục tiêu là 10, s = 5 chuyển thành true, rồi s = 10 đọc mục mới được ghi, dùng số 5 hai lần.

Thay vào đó, hãy đi từ target giảm dần đến num. Lần đọc tại s-num chạm đến một ô thấp hơn mà quá trình duyệt chưa ghi đè, nên nó thấy hàng có trước num. Một tổng đã tạo được sẽ vẫn tạo được, nên bạn có thể dừng ngay khi made[target] là true. Bộ nhớ giảm xuống còn target + 1 giá trị Boolean.

Thuật toán

Bắt đầu với một mảng gồm target + 1 giá trị boolean, trong đó chỉ có made[0] là true.
Lần lượt lấy các giá trị. Với mỗi num, cho s giảm dần từ target đến num.
Ở mỗi vị trí mà made[s-num] có giá trị true, đánh dấu made[s].
Dừng và trả về true ngay khi đánh dấu made[target].
Nếu dùng hết mọi giá trị trước đó, đáp án là false.

def isSubsetSum(nums, target):
    # made[s]: some of the values seen so far add up to exactly s
    made = [False] * (target + 1)
    made[0] = True
    for num in nums:
        # Downward, so made[s - num] still ignores num
        for s in range(target, num - 1, -1):
            if made[s - num]:
                made[s] = True
        if made[target]:
            return True
    return False

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

Vòng lặp tăng dần trên các tổng sẽ dùng một giá trị hai lần: [3] với mục tiêu 9 cho kết quả true.
Quên đặt made[0] = true. Mọi tổng đều được xây dựng từ lựa chọn rỗng, nên mọi đáp án đều là false.
Chọn các giá trị lớn nhất trước. Với [6, 5, 5] và mục tiêu 10, chọn 6 thì còn lại 4, không thể tạo ra 4, trong khi 5 + 5 = 10.
Giá trị lớn hơn target, như [10000] với mục tiêu 1, không được làm thay đổi điều gì. num...target trong Swift sẽ dừng chương trình, còn (num+1):(target+1) trong R sẽ đếm ngược, vì vậy hãy kiểm tra num ≤ target trước.
Trong Lua và R, mục nhập cho tổng s nằm ở chỉ số s + 1.

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

Độ phức tạp thời gian của bài toán tổng tập con là bao nhiêu?

Bảng cần thời gian O(n × target), khoảng 2 × 10^6 bước cho 200 giá trị và target bằng 10^4, còn dùng một hàng sẽ giảm bộ nhớ xuống O(target). Chi phí phụ thuộc vào độ lớn về mặt số học của target, nên phương pháp này có độ phức tạp giả đa thức và không hữu dụng với target như 10^18. Nói chung, bài toán tổng tập con là NP-complete.

Subset Sum liên quan thế nào đến Partition Equal Subset Sum và bài toán ba lô 0/1?

Partition Equal Subset Sum là Subset Sum với target = total / 2, sau khi kiểm tra tổng có phải số chẵn hay không. Subset Sum là bài toán ba lô 0/1, trong đó mỗi giá trị cũng chính là trọng lượng của nó và ba lô phải được lấp đầy chính xác, vì vậy bảng lưu các giá trị đúng hoặc sai thay vì các giá trị tốt nhất.

Tổng tập con có hoạt động với số âm không?

Ý tưởng này đúng, nhưng đoạn code trên thì không. Khi có số âm, các tổng có thể đạt được nằm trong khoảng từ tổng các số âm đến tổng các số dương, vì vậy hãy dịch chỉ số thêm một lượng bằng tổng thấp nhất rồi điền hàng theo cách tương tự. Không thể bỏ qua một giá trị lớn hơn tổng còn lại nữa.

Làm thế nào để tìm các giá trị tạo thành mục tiêu?

Giữ nguyên toàn bộ bảng và bắt đầu tại made[n][target]. Đi lên từng hàng một: nếu made[i-1][s] là true, thì không cần dùng nums[i-1]; nếu không, hãy ghi lại số đó và trừ nó khỏi s. Bạn dừng lại khi tổng bằng 0 và đã chọn được một cách hợp lệ.

def isSubsetSum(nums, target):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [8, 3, 11, 5, 7]
target = 15

Đầu ra mong đợi

true

Subset Sum Problem

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Lấy hoặc bỏ qua từng giá trị

Điền vào bảng các tổng có thể đạt được

Một hàng phép cộng, được cập nhật 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ặp4

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