题解 | 最小邮票数

import sys
def dp(total,num,it):
    #dp[i][j]=min(dp[i-1][j],dp[i-1][j-weight[i]]+1)
    weight=list(map(int,next(it).strip('\n').split()))
    dp=[float('inf')]*(total+1)
    dp[0]=0
    for i in range(1,num+1):
        for j in range(total,0,-1):
            if j-weight[i-1]>-1:
                dp[j]=min(dp[j],dp[j-weight[i-1]]+1)
    ans=dp[-1]
    if ans!=float('inf'):
        print(ans)
    else:
        print(0)
if __name__ =='__main__':
    it=iter(sys.stdin)
    while 1:
        try:
            total=int(next(it).strip('\n'))
            num=int(next(it).strip('\n'))
            dp(total,num,it)
        except:
            break

每种邮票只能取一次，转化为01背包问题