Chương trình Python bài toán Subset Sum (tổng tập con)

Trong bài viết này, chúng ta sẽ tìm hiểu giải pháp cho bài toán sau:

Đề bài – Cho tập số nguyên không âm trong mảng, và giá trị sum, cần xác định có tồn tại tập con có tổng bằng sum cho trước không.

Hãy quan sát giải pháp trong triển khai dưới đây:

# Cách đơn giản (naive/recursive)

Ví dụ 1

def SubsetSum(set, n, sum):
    # Base Cases
    if (sum == 0):
        return True
    if (n == 0 and sum != 0):
        return False
    # bỏ qua nếu phần tử cuối > sum
    if (set[n - 1] > sum):
        return SubsetSum(set, n - 1, sum)
    # kiểm tra 2 trường hợp: có hoặc không có phần tử cuối
    return SubsetSum(set, n-1, sum) or SubsetSum(set, n-1, sum-set[n-1])

# main
set = [2, 14, 6, 22, 4, 8]
sum = 10
n = len(set)
if (SubsetSum(set, n, sum) == True):
    print("Tìm thấy tập con có tổng cho trước")
else:
    print("Không có tập con có tổng cho trước")

Kết quả

Tìm thấy tập con có tổng cho trước

# Cách quy hoạch động (dynamic programming)

Ví dụ 2

# Quy hoạch động
def isSubsetSum(set, n, sum):
    # bảng DP
    dp = [[False for x in range(sum + 1)] for x in range(n + 1)]
    # sum = 0 luôn True
    for i in range(n + 1):
        dp[i][0] = True
    # điền bảng
    for i in range(1, n + 1):
        for j in range(1, sum + 1):
            if set[i-1] > j:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i-1][j] or dp[i-1][j-set[i-1]]
    return dp[n][sum]

# main
set = [2, 14, 6, 22, 4, 8]
sum = 10
n = len(set)
if (isSubsetSum(set, n, sum)):
    print("Tìm thấy tập con có tổng cho trước")
else:
    print("Không có tập con có tổng cho trước")

Kết quả

Tìm thấy tập con có tổng cho trước

Kết luận

Trong bài này, chúng ta đã học cách làm chương trình Python cho bài toán Subset Sum.