这是一个经典的背包 DP。 第一次用 Python 写集合背包，具体解法见代码注释。 然后值得关注的一点在于，如果 python 读取到文件末尾，如果用以下方式输入会得到一个 Non-zero Exit Code 的错误码：

while True:
    buf = raw_input()
    if not buf: break
    ...

因此还是采用 for line in sys.stdin 的方式来输入好了。

# -*- coding: utf8 -*-

# 3487791 2013-12-08 23:58:19 Accepted 3631 Python 1130 4744 呆滞的慢板

"""
经典背包问题
经典背包变种，问题在于背包空间超大，因此要注意以下两点：
1. 背包需要用集合存放;
2. 由于空间太大，最坏情况可能有 2^30 个状态，因此需要进行折半;

折半的方法是，分别做两个 2^(n/2) 的背包，做完之后，枚举一个二分另一个。
"""

import sys

def binary_search(v, k):
    l = 0
    r = len(v)
    while l < r-1:
        m = l + r >> 1
        if v[m] <= k: l = m
        else: r = m
    return v[l]

lines = list(sys.stdin)

for i in range(0,len(lines),2):

    (n, m) = map(int, lines[i].split())
    vals = list(map(int, lines[i+1].split()))

    s = {0}
    for v in vals[0:n//2]:
        s |= {a+v for a in s if a+v <= m}
    k1 = sorted(s)

    s = {0}
    for v in vals[n//2:]:
        s |= {a+v for a in s if a+v <= m}

    ans = 0
    for x in s:
        if x <= m:
            ans = max(ans, x + binary_search(k1, m-x))

    print(ans)

【转载请附】愿以此功德，回向 >>

原文链接：http://www.huangwenchao.com.cn/2013/12/zoj3631.html【zoj 3631 – Watashi’s BG】