区画割ナップサック問題をPythonで解く

def partition_problem(nums, n):
    def knapsack(nums, n, total):
        dp = [0] * (total + 1)
        for i in range(n):
            for j in range(total, nums[i] - 1, -1):
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
        return dp[total]

    total = sum(nums)
    if total % 2 != 0:
        return False
    total //= 2
    return knapsack(nums, n, total) == total

nums = [1, 5, 11, 5]
n = len(nums)
if partition_problem(nums, n):
    print("Can be divided into two subsets of equal sum")
else:
    print("Can't be divided into two subsets of equal sum")