You are viewing a single comment's thread. Return to all comments →
Passed
def solution(arr,k): dp=[] length=len(arr) for i in range(length+1): dp.append([0]*(k+1)) for i in range(length+1): dp[i][0]=1 for i in range(1,length+1): for j in range(1,k+1): if j<arr[i-1]: dp[i][j]=dp[i-1][j] elif dp[i-1][j]==1 or dp[i][j-arr[i-1]]==1: dp[i][j]=1 for i in range(k,-1,-1): if dp[-1][i]==1: return i t=int(input()) for i in range(t): a,k=map(int,input().split()) arr=list(map(int,input().split())) print(int(solution(arr,k)))
Seems like cookies are disabled on this browser, please enable them to open this website
Knapsack
You are viewing a single comment's thread. Return to all comments →
Passed