【python】ALGO-1004 无聊的逗 - 背包问题解法

话不多说，直接看代码吧。

# 状态搜索题
# 0-1背包问题
# n 样物品
# 背包容量为 sum//2
# 每样物品的重量和价值的数值一样
def canPart(nums):
    n = len(nums)
    if n < 2:
        return 0

    sumA = sum(nums)
    target = sumA //2

    # 建立背包
    dp = [[0] * (target+1) for i in range(n+1)]

    for i in range(nums[0], target+1):
        dp[0][i] = nums[0]
    for i in range(1, n+1):
        for j in range(1, target+1):
            if j < nums[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j- nums[i-1]] + nums[i-1])
    # print(dp[n][target])
    return dp[n][target]
        
    
def boringDou(n, nums):
    nums.sort()
    sumA = sum(nums)
    ans = 0
    if sumA%2 == 0:
        ans = canPart(nums)
    i=0
    while i < len(nums):
        sumA = sum(nums)
        if((sumA - nums[i]) % 2 == 0):
            nums.pop(i)
            ans = max(canPart(nums), ans)
            i = 0
            continue
        i += 1
    # print(" ans = %d" %ans)
    print(ans)
    return

n = int(input())
inp = input().split()
nums = []
for i in inp:
    nums.append(int(i))
boringDou(n, nums)