Bottoms UP DP first https://www.hackerrank.com/challenges/unbounded-knapsack

unbounded-knapsack.py

from sys import stdin
import dis
get = iter(map(int,stdin.read().split())).__next__


def knapSack(lis,K,N):
	dp = [[0]*(K+1)]*(N+1)

	for n in range(N+1):
		for k in range(K+1):
			if (k==0):
				dp[n][k] = 0
			elif (n==0):
				dp[n][k] = 0
			elif k>=lis[n-1]:
				dp[n][k] = max(lis[n-1]+dp[n][k-lis[n-1]],dp[n-1][k])
			else:
				dp[n][k] = dp[n-1][k]

	return dp[N][K]


def main():
	t = get()

	for _ in range(t):
		n = get()
		k = get()

		lis = []
		for _ in range(n):
			lis.append(get())

		print (knapSack(lis,k,n))

main()