https://www.v2ex.com/t/326136

laowang.py

l = [509, 838, 924, 650, 604, 793, 564, 651,
     697, 649, 747, 787, 701, 605, 644]


def by_dp():
    dp = [0] * 5001
    i = 0
    while i < len(l):
        w = 5000
        while w >= l[i]:
            n_w = dp[w - l[i]] + l[i]
            if n_w <= w:
                dp[w] = max(n_w, dp[w])
            w -= 1
        i += 1

    return(dp[-1])


def powerset(l):
    'get powerset'
    if len(l) == 1:
        return [l, []]
    sub = powerset(l[1:])
    return [[l[0]] + r for r in sub] + sub


def by_powerset():
    'find max sum in powerset'
    return max(
        filter(
            lambda x: sum(x) <= 5000,
            powerset(l)
        ),
        key=sum
    )

print(by_powerset())
print(by_dp())