对半枚举 + 二分搜索

如果直接枚举的话, 最多有2^46种(如果不考虑W的话)
如果对半枚举, 每一半最多2^23=8388608. 可以接受.
分成了left和right集合.
将right进行排序.
对于left的每个元素, 用二分搜索找到right中可以配对的最大元素.

与教材里面的方法不太一样, 不同点在于不是使用dfs进行枚举, 而是通过set进行枚举, 好处是不需要担心生成重复的元素.

时间复杂度

O(2^(n/2) * log(2^(n/2)))

Python 代码

from bisect import bisect_right

W, N = map(int, input().split())
left = set([0])
for i in range(N//2):
    e = int(input())
    for s in list(left):
        tmp = s + e
        if tmp not in left and tmp <= W:
            left.add(tmp)

right = set([0])
for i in range(N - N//2):
    e = int(input())
    for s in list(right):
        tmp = s + e
        if tmp not in right and tmp <= W:
            right.add(tmp)            
right = sorted(right)

ans = 0
for a in left:
    tmp = W - a
    idx = bisect_right(right, tmp) - 1
    if idx >= 0:
        b = right[idx]
        ans = max(ans, a + b)
print(ans)