题解 | 神奇的口袋

import sys
def dp(num,it):
    #dp[i][j]=dp[i-1][j]+dp[i-1][j-weight[i-1]]
    weight=[]
    for _ in range(num):
        item=int(next(it).strip())
        weight.append(item)
    dp=[0]*(41)
    dp[0]=1
    for i in range(1,num+1):
        for j in range(40,0,-1):
            if j-weight[i-1]>=0:
                dp[j]+=dp[j-weight[i-1]]
    print(dp[-1])
if __name__=='__main__':
    it=iter(sys.stdin)
    while 1:
        try:
            num=int(next(it).strip())
            dp(num,it)
        except:
            break

抽象为01背包问题，滚动数组优化，空间n，时间n^2，如果回溯是2^n有超时的风险