0-1背包问题

N,C=[int(each) for each in input().split()]
data=[]
for i in range(N):
    data.append([int(a) for a in input().split()])

################# 0-1 背包##################
dp=[[0 for j in range(C+1)] for i in range(N+1)]
for i in range(1,N+1):
    for j in range(1,C+1):
        if j <data[i-1][0]:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-data[i-1][0]]+data[i-1][1])
x=[0]*N
k=N
while k>=1:
    l=C
    while l>=1:
        if dp[k][l]==dp[k-1][l]:
            x[k-1]=0
        else:
            x[k-1]=1
            l=l-data[k-1][0]
        k=k-1