You are given weights and values of N items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. Note that we have only one quantity of each item.
In other words, given two integer arrays val[0..N-1] and wt[0..N-1] which represent values and weights associated with N items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item or dont pick it (0-1 property).
Example 1:
Input:
N = 3
W = 4
values[] = {1,2,3}
weight[] = {4,5,1}
Output: 3
Example 2:
Input:
N = 3
W = 3
values[] = {1,2,3}
weight[] = {4,5,6}
Output: 0
Your Task:
Complete the function knapSack() which takes maximum capacity W, weight array wt[], value array val[], and the number of items n as a parameter and returns the maximum possible value you can get.
Expected Time Complexity: O(N*W).
Expected Auxiliary Space: O(N*W)
Constraints:
1 ≤ N ≤ 1000
1 ≤ W ≤ 1000
1 ≤ wt[i] ≤ 1000
1 ≤ v[i] ≤ 1000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

    

    #Function to return max value that can be put in knapsack of capacity W.

    def knapSack(self,W, wt, val, n):

       

        # code here

Solutions:
class Solution:

	def knapSack(self, W, wt, val, n):
		dp = [[-1 for m in range(W + 1)] for n in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 0
		for j in range(W + 1):
			dp[0][j] = 0
		for i in range(1, n + 1):
			for j in range(1, W + 1):
				if wt[i - 1] <= j:
					dp[i][j] = max(val[i - 1] + dp[i - 1][j - wt[i - 1]], dp[i - 1][j])
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[n][W]


class Solution:

	def knapSack(self, W, wt, val, n):
		t = [[0] * (W + 1) for _ in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, W + 1):
				if wt[i - 1] <= j:
					t[i][j] = max(val[i - 1] + t[i - 1][j - wt[i - 1]], t[i - 1][j])
				else:
					t[i][j] = t[i - 1][j]
		return t[n][W]


class Solution:

	def knapSack(self, W, wt, val, n):

		def recursive(ind, W):
			for ind in range(n - 1, -1, -1):
				for W in range(W + 1):
					pick = 0
					if wt[ind] <= W:
						pick = val[ind] + dp[ind + 1][W - wt[ind]]
					nonpick = dp[ind + 1][W]
					dp[ind][W] = max(pick, nonpick)
			return dp[ind][W]
		dp = [[0 for i in range(W + 1)] for j in range(n + 1)]
		return recursive(0, W)


class Solution:

	def knapSack(self, W, wt, val, n):
		table = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, W + 1):
				if j >= wt[i - 1]:
					x = val[i - 1] + table[i - 1][j - wt[i - 1]]
					y = table[i - 1][j]
					table[i][j] = max(x, y)
				else:
					table[i][j] = table[i - 1][j]
		return table[-1][-1]


class Solution:

	def knapSack(self, W, wt, val, n):
		dp = [[-1 for _ in range(W + 1)] for _ in range(n)]
		for i in range(W + 1):
			if wt[0] <= i:
				dp[0][i] = val[0]
			else:
				dp[0][i] = 0
		for i in range(1, n):
			for j in range(W + 1):
				np = 0 + dp[i - 1][j]
				p = -1000000000.0
				if wt[i] <= j:
					p = val[i] + dp[i - 1][j - wt[i]]
				dp[i][j] = max(p, np)
		return dp[n - 1][W]


class Solution:

	def knapSack(self, W, wt, val, n):
		dp = [[-1 for _ in range(W + 1)] for _ in range(n)]

		def f(n, W, wt, val, dp):
			if n == 0:
				if wt[0] <= W:
					return val[0]
				return 0
			if dp[n][W] != -1:
				return dp[n][W]
			np = 0 + f(n - 1, W, wt, val, dp)
			p = -1000000000.0
			if wt[n] <= W:
				p = val[n] + f(n - 1, W - wt[n], wt, val, dp)
			dp[n][W] = max(p, np)
			return dp[n][W]
		return f(n - 1, W, wt, val, dp)


class Solution:

	def knapSack(self, capacity, weights, profits, n):
		dp = [[0 for j in range(capacity + 1)] for i in range(len(profits) + 1)]
		for i in range(1, n + 1):
			(cur_weight, cur_profit) = (weights[i - 1], profits[i - 1])
			for cap in range(1, capacity + 1):
				if cur_weight > cap:
					dp[i][cap] = dp[i - 1][cap]
				else:
					dp[i][cap] = max(dp[i - 1][cap], cur_profit + dp[i - 1][cap - cur_weight])
		return dp[n][capacity]


class Solution:

	def knapSack(self, capacity, weights, profits, n):
		memo = {}
		return self.knapSack1(capacity, weights, profits, n, memo)

	def knapSack1(self, capacity, weights, profits, i, memo):
		if i == 0 or capacity == 0:
			return 0
		cur_weight = weights[i - 1]
		cur_profit = profits[i - 1]
		if (i, capacity) in memo:
			return memo[i, capacity]
		if cur_weight > capacity:
			res = self.knapSack1(capacity, weights, profits, i - 1, memo)
		else:
			res = max(self.knapSack1(capacity, weights, profits, i - 1, memo), cur_profit + self.knapSack1(capacity - cur_weight, weights, profits, i - 1, memo))
		memo[i, capacity] = res
		return res


class Solution:

	def knapSack(self, W, wt, val, n):
		t = [[0 for x in range(W + 1)] for x in range(n + 1)]
		for i in range(n + 1):
			for j in range(W + 1):
				if i == 0 or j == 0:
					t[i][j] = 0
				elif wt[i - 1] <= j:
					t[i][j] = max(val[i - 1] + t[i - 1][j - wt[i - 1]], t[i - 1][j])
				else:
					t[i][j] = t[i - 1][j]
		return t[n][W]


class Solution:

	def knapSack(self, W, wt, val, n):
		dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
		for i in range(n + 1):
			for j in range(W + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif wt[i - 1] > j:
					dp[i][j] = dp[i - 1][j]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wt[i - 1]] + val[i - 1])
		return dp[n][W]


class Solution:

	def knapSack(self, W, wt, val, n):
		K = [[0 for x in range(W + 1)] for x in range(n + 1)]
		for i in range(n + 1):
			for w in range(W + 1):
				if i == 0 or w == 0:
					K[i][w] = 0
				elif wt[i - 1] <= w:
					K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
				else:
					K[i][w] = K[i - 1][w]
		return K[n][W]


class Solution:

	def knapSack(self, maxWeight, wt, val, n):
		n = len(wt)
		dp = [[0 for i in range(maxWeight + 1)] for j in range(n)]
		prev = [0 for i in range(maxWeight + 1)]
		for W in range(wt[0], maxWeight + 1):
			prev[W] = val[0]
		for ind in range(1, n):
			for W in range(maxWeight, -1, -1):
				not_pick = prev[W]
				pick = float('-inf')
				if wt[ind] <= W:
					pick = val[ind] + prev[W - wt[ind]]
				prev[W] = max(pick, not_pick)
		return prev[maxWeight]


class Solution:

	def knapSack(self, W, wt, val, n):
		prev = [0] * (W + 1)
		for i in range(wt[0], W + 1):
			prev[i] = val[0]
		for ind in range(1, n):
			for cap in range(W, -1, -1):
				notTaken = 0 + prev[cap]
				taken = float('-inf')
				if wt[ind] <= cap:
					taken = val[ind] + prev[cap - wt[ind]]
				prev[cap] = max(notTaken, taken)
		return prev[W]


class Solution:

	def knapSack(self, TW, wt, val, n):
		dp = [0] * (TW + 1)
		for k in range(wt[0], TW + 1):
			dp[k] = val[0]
		for i in range(1, n):
			for W in range(TW, -1, -1):
				not_pick = dp[W]
				pick = 0
				if wt[i] <= W:
					pick = val[i] + dp[W - wt[i]]
				dp[W] = max(not_pick, pick)
		return dp[TW]


class Solution:

	def dfs(self, i, W, wt, val, dp):
		if i == 0:
			if wt[0] <= W:
				return val[0]
			return 0
		if dp[i][W] != -1:
			return dp[i][W]
		not_pick = self.dfs(i - 1, W, wt, val, dp)
		pick = 0
		if wt[i] <= W:
			pick = val[i] + self.dfs(i - 1, W - wt[i], wt, val, dp)
		dp[i][W] = max(not_pick, pick)
		return dp[i][W]

	def knapSack(self, W, wt, val, n):
		dp = [[-1 for j in range(W + 1)] for i in range(n)]
		return self.dfs(n - 1, W, wt, val, dp)


class Solution:

	def knapSack(self, TW, wt, val, n):
		prev = [0] * (TW + 1)
		for i in range(1, n + 1):
			cur = [0] * (TW + 1)
			for W in range(TW + 1):
				not_pick = prev[W]
				pick = 0
				if wt[i - 1] <= W:
					pick = val[i - 1] + prev[W - wt[i - 1]]
				cur[W] = max(not_pick, pick)
			prev = cur
		return prev[W]


class Solution:

	def knapSack(self, wt, W, val, n):

		def answer(i, wt):
			if wt <= 0 or i == -1:
				return 0
			if dp[i][wt] != -1:
				return dp[i][wt]
			if W[i] > wt:
				dp[i][wt] = answer(i - 1, wt)
				return dp[i][wt]
			take = answer(i - 1, wt - W[i]) + val[i]
			nottake = answer(i - 1, wt)
			dp[i][wt] = max(take, nottake)
			return dp[i][wt]
		dp = [[-1 for i in range(wt + 1)] for j in range(n)]
		return answer(n - 1, wt)


class Solution:

	def knapSack(self, W, wt, val, n):
		return self.solve(W, wt, val, n)

	def solve(self, cap, wt, val, n):
		curr = [0] * (cap + 1)
		for w in range(wt[0], cap + 1):
			if wt[0] <= cap:
				curr[w] = val[0]
			else:
				curr[w] = 0
		for ind in range(1, n):
			for w in range(cap, -1, -1):
				inc = 0
				if wt[ind] <= w:
					inc = val[ind] + curr[w - wt[ind]]
				exc = 0 + curr[w]
				curr[w] = max(inc, exc)
		return curr[cap]


from functools import lru_cache

class Solution:

	def knapSack(self, W, wt, val, n):
		dp = [[0] * (W + 1) for _ in range(n + 1)]
		for i in range(n + 1):
			for j in range(W + 1):
				if i == 0 or j == 0:
					continue
				elif wt[i - 1] > j:
					dp[i][j] = dp[i - 1][j]
				else:
					dp[i][j] = max(val[i - 1] + dp[i - 1][j - wt[i - 1]], dp[i - 1][j])
		return dp[n][W]


from functools import lru_cache

class Solution:

	def knapSack(self, W, wt, val, n):

		@lru_cache(None)
		def recursion(index, weight):
			if index < 0 or weight <= 0:
				return 0
			if wt[index] > weight:
				return recursion(index - 1, weight)
			else:
				return max(val[index] + recursion(index - 1, weight - wt[index]), recursion(index - 1, weight))
		return recursion(n - 1, W)


class Solution:

	def knapSack(self, W, wt, val, n):
		dp = [[-1 for j in range(W + 1)] for i in range(n)]
		return self.solve(W, wt, val, n - 1, dp)

	def solve(self, W, wt, val, ind, dp):
		if ind == 0:
			if wt[0] <= W:
				return val[0]
			else:
				return 0
		if dp[ind][W] != -1:
			return dp[ind][W]
		incl = 0
		if wt[ind] <= W:
			incl = val[ind] + self.solve(W - wt[ind], wt, val, ind - 1, dp)
		excl = 0 + self.solve(W, wt, val, ind - 1, dp)
		dp[ind][W] = max(incl, excl)
		return dp[ind][W]


class Solution:

	def knapSack(self, W, wt, val, n):
		dp = [0 for j in range(W + 1)]
		for w in range(wt[0], W + 1):
			dp[w] = val[0]
		for i in range(1, n):
			for w in range(W, -1, -1):
				take = float('-inf')
				if w >= wt[i]:
					take = val[i] + dp[w - wt[i]]
				notake = 0 + dp[w]
				dp[w] = max(take, notake)
		return dp[W]

	def rec(self, ind, W, wt, val, dp):
		if ind == 0:
			if W - wt[ind] >= 0:
				return val[ind]
			return 0
		if dp[ind][W] != -1:
			return dp[ind][W]
		take = float('-inf')
		if wt[ind] <= W:
			take = val[ind] + self.rec(ind - 1, W - wt[ind], wt, val, dp)
		noTake = 0 + self.rec(ind - 1, W, wt, val, dp)
		dp[ind][W] = max(take, noTake)
		return max(take, noTake)


class Solution:

	def knapSack(self, W, wt, val, n):
		totalVal = 0
		totalWt = 0
		for v in wt:
			totalWt += v
		dp = [[-1 for j in range(W + 1)] for i in range(n + 1)]
		return self.rec(n - 1, W, wt, val, dp)

	def rec(self, ind, W, wt, val, dp):
		if ind == 0:
			if W - wt[ind] >= 0:
				return val[ind]
			return 0
		if dp[ind][W] != -1:
			return dp[ind][W]
		take = float('-inf')
		if wt[ind] <= W:
			take = val[ind] + self.rec(ind - 1, W - wt[ind], wt, val, dp)
		noTake = 0 + self.rec(ind - 1, W, wt, val, dp)
		dp[ind][W] = max(take, noTake)
		return max(take, noTake)


class Solution:

	def knapSack(self, W, wt, val, n):
		dp = {}

		def knap01(w, i):
			if (w, i) in dp:
				return dp[w, i]
			if i == n:
				return 0
			x = 0
			if wt[i] <= w:
				x = knap01(w - wt[i], i + 1) + val[i]
			y = knap01(w, i + 1)
			dp[w, i] = max(x, y)
			return max(x, y)
		return knap01(W, 0)


class Solution:

	def knapSack(self, W, wt, val, n):
		dp = [[0] * n for _ in range(0, W + 1)]
		for i in range(W + 1):
			for j in range(n):
				if j == 0:
					with_item_j = val[0] if wt[0] <= i else 0
				else:
					with_item_j = dp[i - wt[j]][j - 1] + val[j] if wt[j] <= i else 0
				without_j = dp[i][j - 1] if j > 0 else 0
				dp[i][j] = max(with_item_j, without_j)
		return dp[W][n - 1]


class Solution:

	def knapSack(self, W, wt, val, n):
		memo = {}

		def impl(capacity, i):
			memo_key = str(capacity) + ':' + str(i)
			if memo.get(memo_key) is not None:
				return memo.get(memo_key)
			if i == 0:
				result = val[0] if wt[0] <= capacity else 0
			else:
				max_with = impl(capacity - wt[i], i - 1) + val[i] if wt[i] <= capacity else 0
				max_without = impl(capacity, i - 1)
				result = max(max_without, max_with)
			memo[memo_key] = result
			return result
		return impl(W, n - 1)


class Solution:

	def knapSack(self, W, wt, val, n):
		capacity = W
		values = val
		weights = wt
		dp = [[0 for x in range(capacity + 1)] for y in range(len(values) + 1)]
		for i in range(1, len(values) + 1):
			for j in range(1, capacity + 1):
				if weights[i - 1] <= j:
					dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[len(values)][capacity]


class Solution:

	def knapSack(self, W, wt, val, n):
		dp = [[-1 for i in range(W + 1)] for i in range(n)]
		ans = self.knap(W, wt, val, n - 1, dp)
		if ans != -10 ** 8:
			return ans
		else:
			return 0

	def knap(self, W, wt, val, n, dp):
		if dp[n][W] != -1:
			return dp[n][W]
		if n == 0:
			if W == 0:
				return 0
			if W >= wt[0]:
				return val[0]
			return 0
		notpick = self.knap(W, wt, val, n - 1, dp)
		pick = -10 ** 8
		if wt[n] <= W:
			pick = val[n] + self.knap(W - wt[n], wt, val, n - 1, dp)
		dp[n][W] = max(pick, notpick)
		return dp[n][W]


class Solution:

	def knapSack(self, W, wt, val, n):
		import sys
		sys.setrecursionlimit(10 ** 9 + 7)
		dp = [[0 for j in range(W + 1)] for i in range(n)]
		for j in range(wt[0], W + 1):
			dp[0][j] = val[0]
		for i in range(1, n):
			for j in range(0, W + 1):
				pick = 0
				npick = 0 + dp[i - 1][j]
				if wt[i] <= j:
					pick = val[i] + dp[i - 1][j - wt[i]]
				dp[i][j] = max(pick, npick)
		return dp[n - 1][W]

	def solve(self, i, j, wt, val, dp):
		if i == 0:
			if wt[i] <= j:
				dp[i][j] = val[i]
				return val[i]
			else:
				dp[i][j] = val[i]
				return 0
		if dp[i][j] != -1:
			return dp[i][j]
		npick = 0 + self.solve(i - 1, j, wt, val, dp)
		pick = 0
		if wt[i] <= j:
			pick = val[i] + self.solve(i - 1, j - wt[i], wt, val, dp)
		dp[i][j] = max(pick, npick)
		return dp[i][j]


class Solution:

	def knapSack(self, W, wt, val, n):
		dp = [0 for i in range(W + 1)]
		for i in range(1, n + 1):
			for w in range(W, 0, -1):
				if wt[i - 1] <= w:
					dp[w] = max(dp[w], dp[w - wt[i - 1]] + val[i - 1])
		return dp[W]


class Solution:

	def knapSack(self, W, wt, val, N):
		dp = [[0] * (W + 1) for _ in range(N)]
		for i in range(N):
			for j in range(W + 1):
				cap = j
				cwt = wt[i]
				cvl = val[i]
				if i == 0:
					if cwt <= cap:
						dp[i][j] = cvl
					else:
						dp[i][j] = 0
				elif cwt <= cap:
					c1 = cvl + dp[i - 1][cap - cwt]
					c2 = 0 + dp[i - 1][cap]
					dp[i][j] = max(c1, c2)
				else:
					dp[i][j] = dp[i - 1][cap]
		return dp[N - 1][W]


class Solution:

	def knapSack(self, W, wt, val, N):
		dp = {}

		def solve(n, cap):
			if n == 0 or cap == 0:
				return 0
			elif (n, cap) in dp:
				return dp[n, cap]
			else:
				cwt = wt[n - 1]
				cv = val[n - 1]
				if cwt <= cap:
					c1 = cv + solve(n - 1, cap - cwt)
					c2 = solve(n - 1, cap)
					c = max(c1, c2)
				else:
					c = solve(n - 1, cap)
				dp[n, cap] = c
				return c
		return solve(N, W)


class Solution:

	def knapSack(self, capacity, wt, val, n):
		dp = [0 for _ in range(capacity + 1)]
		prev = [0 for _ in range(capacity + 1)]
		for i in range(n):
			for j in range(1, capacity + 1):
				if wt[i] <= j:
					dp[j] = max(val[i] + prev[j - wt[i]], prev[j])
				else:
					dp[j] = prev[j]
			prev = dp[:]
		return dp[-1]


class Solution:

	def knapSack(self, W, wt, val, n):

		def f(n, w, wt, val, dp):
			if n == 0:
				if wt[0] <= w:
					return val[0]
				return 0
			if dp[n][w] != -1:
				return dp[n][w]
			noteTake = f(n - 1, w, wt, val, dp) + 0
			take = -1000000000.0
			if w >= wt[n]:
				take = f(n - 1, w - wt[n], wt, val, dp) + val[n]
			dp[n][w] = max(noteTake, take)
			return dp[n][w]
		dp = [[-1] * (W + 1) for i in range(n)]
		return f(n - 1, W, wt, val, dp)


class Solution:

	def knapSack(self, W, wt, val, n):
		dp = {}

		def helper(ind, weight):
			if ind == n:
				return 0
			if (ind, weight) in dp:
				return dp[ind, weight]
			take = float('-inf')
			not_take = helper(ind + 1, weight)
			if weight - wt[ind] >= 0:
				take = val[ind] + helper(ind + 1, weight - wt[ind])
			dp[ind, weight] = max(take, not_take)
			return dp[ind, weight]
		return helper(0, W)


class Solution:

	def knapSack(self, W, wt, val, n):
		dp = [[0] * (W + 1) for _ in range(n + 1)]
		for r in range(1, n + 1):
			for c in range(1, W + 1):
				if wt[r - 1] <= c:
					dp[r][c] = max(dp[r - 1][c - wt[r - 1]] + val[r - 1], dp[r - 1][c])
				else:
					dp[r][c] = max(dp[r - 1][c], dp[r][c - 1])
		return dp[-1][-1]


class Solution:

	def KnapSack(self, W, wt, val, n):
		key = (W, n)
		if n == 0 or W == 0:
			return 0
		if key in self.di:
			return self.di[key]
		if wt[n - 1] <= W:
			self.di[key] = max(val[n - 1] + self.KnapSack(W - wt[n - 1], wt, val, n - 1), self.KnapSack(W, wt, val, n - 1))
			return self.di[key]
		else:
			self.di[key] = self.KnapSack(W, wt, val, n - 1)
			return self.di[key]

	def knapSack(self, W, wt, val, n):
		self.di = {}
		return self.KnapSack(W, wt, val, n)


class Solution:

	def knapSack(self, W, wt, val, n):
		dp = {}

		def solve(n, cap):
			if n == 0 or cap == 0:
				return 0
			elif (n, cap) in dp:
				return dp[n, cap]
			else:
				cw = wt[n - 1]
				cval = val[n - 1]
				if cw <= cap:
					c1 = cval + solve(n - 1, cap - cw)
					c2 = solve(n - 1, cap)
					c = max(c1, c2)
				else:
					c = solve(n - 1, cap)
				dp[n, cap] = c
				return c
		return solve(n, W)


from itertools import accumulate

class Solution:

	def knapSack(self, W, wt, val, n):
		if min(wt) > W:
			return 0
		N = n
		F = [[0] * (W + 1) for _ in range(n + 1)]
		for n in range(1, N + 1):
			for w in range(1, W + 1):
				if w < wt[n - 1]:
					F[n][w] = F[n - 1][w]
				else:
					F[n][w] = max(F[n - 1][w], F[n - 1][w - wt[n - 1]] + val[n - 1])
		return F[-1][-1]
		return


class Solution:

	def knapSack(self, W, wt, val, n):

		def f(ind, W, N, w, v):
			if ind == 0:
				if w[0] <= W:
					return v[0]
				return 0
			if dp[ind][W] != 0:
				return dp[ind][W]
			pick = -int(1000000000.0)
			if w[ind] <= W:
				pick = v[ind] + f(ind - 1, W - w[ind], N, w, v)
			notpick = f(ind - 1, W, N, w, v)
			dp[ind][W] = max(pick, notpick)
			return dp[ind][W]
		dp = [[0 for i in range(W + 1)] for j in range(n)]
		return f(n - 1, W, n, wt, val)


class Solution:

	def knapSack(self, W, wt, val, n):
		dp = [[0 for i in range(W + 1)] for j in range(n)]
		for i in range(wt[0], W + 1):
			dp[0][i] = val[0]
		for ind in range(1, n):
			for cap in range(W + 1):
				not_taken = 0 + dp[ind - 1][cap]
				taken = -sys.maxsize
				if wt[ind] <= cap:
					taken = val[ind] + dp[ind - 1][cap - wt[ind]]
				dp[ind][cap] = max(not_taken, taken)
		return dp[n - 1][W]


def solution(W, wt, val, index, dp):
	if (W, index) in dp:
		return dp[W, index]
	if W == 0 or index >= len(wt):
		return 0
	if W >= wt[index]:
		dp[W, index] = max(val[index] + solution(W - wt[index], wt, val, index + 1, dp), solution(W, wt, val, index + 1, dp))
	else:
		dp[W, index] = solution(W, wt, val, index + 1, dp)
	return dp[W, index]

class Solution:

	def knapSack(self, W, wt, val, n):
		return solution(W, wt, val, 0, {})


import numpy as np

class Solution:

	def rec_sol(self, W, wt, val, n):
		if n == 0:
			return 0
		if W <= 0:
			return 0
		if W - wt[n - 1] < 0:
			return self.rec_sol(W, wt, val, n - 1)
		return max(val[n - 1] + self.rec_sol(W - wt[n - 1], wt, val, n - 1), self.rec_sol(W, wt, val, n - 1))

	def mem_sol(self, W, wt, val, n, dp):
		if n == 0:
			return 0
		if W <= 0:
			return 0
		if dp[n][W] != -1:
			return dp[n][W]
		if W - wt[n - 1] < 0:
			temp = self.mem_sol(W, wt, val, n - 1, dp)
		else:
			temp = max(val[n - 1] + self.mem_sol(W - wt[n - 1], wt, val, n - 1, dp), self.mem_sol(W, wt, val, n - 1, dp))
		dp[n][W] = temp
		return temp

	def dp_sol(self, W, wt, val, n):
		dp = np.zeros((n + 1, W + 1))
		for i in range(1, n + 1):
			for j in range(1, W + 1):
				if j - wt[i - 1] < 0:
					temp = dp[i - 1][j]
				else:
					temp = max(dp[i - 1][j], val[i - 1] + dp[i - 1][j - wt[i - 1]])
				dp[i][j] = temp
		return int(dp[n][W])

	def dp_sol_opt(self, W, wt, val, n):
		dp = np.array([0] * (W + 1))
		for i in range(1, n + 1):
			for j in range(W, 0, -1):
				if j - wt[i - 1] < 0:
					temp = dp[j]
				else:
					temp = max(dp[j], val[i - 1] + dp[j - wt[i - 1]])
				dp[j] = temp
		return int(dp[W])

	def knapSack(self, W, wt, val, n):
		return self.dp_sol_opt(W, wt, val, n)


import numpy as np

class Solution:

	def rec_sol(self, W, wt, val, n):
		if n == 0:
			return 0
		if W <= 0:
			return 0
		if W - wt[n - 1] < 0:
			return self.rec_sol(W, wt, val, n - 1)
		return max(val[n - 1] + self.rec_sol(W - wt[n - 1], wt, val, n - 1), self.rec_sol(W, wt, val, n - 1))

	def mem_sol(self, W, wt, val, n, dp):
		if n == 0:
			return 0
		if W <= 0:
			return 0
		if dp[n][W] != -1:
			return dp[n][W]
		if W - wt[n - 1] < 0:
			temp = self.mem_sol(W, wt, val, n - 1, dp)
		else:
			temp = max(val[n - 1] + self.mem_sol(W - wt[n - 1], wt, val, n - 1, dp), self.mem_sol(W, wt, val, n - 1, dp))
		dp[n][W] = temp
		return temp

	def knapSack(self, W, wt, val, n):
		dp = np.array([[-1] * (W + 1)] * (n + 1))
		return self.mem_sol(W, wt, val, n, dp)


class Solution:

	def knapSack(self, W, wt, val, n):
		dp = []
		for i in range(n + 1):
			row = []
			for j in range(W + 1):
				row.append(0)
			dp.append(row)
		for i in range(1, n + 1):
			for j in range(1, W + 1):
				if wt[i - 1] <= j:
					dp[i][j] = max(val[i - 1] + dp[i - 1][j - wt[i - 1]], dp[i - 1][j])
				elif wt[i - 1] > j:
					dp[i][j] = dp[i - 1][j]
		return dp[n][W]


class Solution:
	matrix = [[-1 for j in range(1001)] for i in range(1001)]

	def knapSack(self, W, wt, val, n):
		N = n
		dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
		for i in range(1, N + 1):
			for w in range(1, W + 1):
				if w >= wt[i - 1]:
					dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w])
				else:
					dp[i][w] = dp[i - 1][w]
		return dp[N][W]


class Solution:

	def knapSack(self, W, wt, val, n):
		dp = [[0 for i in range(0, W + 1)] for j in range(0, n)]
		for i in range(wt[0], W + 1):
			dp[0][i] = val[0]
		for i in range(1, n):
			for j in range(1, W + 1):
				include = 0
				if wt[i] <= j:
					include = dp[i - 1][j - wt[i]] + val[i]
				exclude = dp[i - 1][j]
				dp[i][j] = max(include, exclude)
		return dp[n - 1][W]


from functools import lru_cache

class Solution:

	def knapSack(self, W, wt, val, n):

		@lru_cache(None)
		def dp(W, n):
			if W == 0 or n == 0:
				return 0
			if wt[n - 1] > W:
				return dp(W, n - 1)
			return max(val[n - 1] + dp(W - wt[n - 1], n - 1), dp(W, n - 1))
		return dp(W, n)


class Solution:

	def solution(self, ind, wt, W, val, dp):
		if ind == 0:
			if W >= wt[ind]:
				return val[ind]
			else:
				return 0
		if dp[ind][W] != -1:
			return dp[ind][W]
		notTake = 0 + self.solution(ind - 1, wt, W, val, dp)
		take = -1 ** 9
		if W >= wt[ind]:
			take = val[ind] + self.solution(ind - 1, wt, W - wt[ind], val, dp)
		dp[ind][W] = max(take, notTake)
		return dp[ind][W]

	def knapSack(self, W, wt, val, n):
		dp = [[0] * (W + 1) for row in range(n)]
		for j in range(wt[0], W + 1):
			dp[0][j] = val[0]
		for ind in range(1, n):
			for w in range(W + 1):
				notTake = 0 + dp[ind - 1][w]
				take = -1 ** 9
				if w >= wt[ind]:
					take = val[ind] + dp[ind - 1][w - wt[ind]]
				dp[ind][w] = max(take, notTake)
		return dp[n - 1][W]


class Solution:

	def knapSack(self, W, wt, val, n):
		dp = [[0] * n for i in range(W + 1)]
		for i in range(W + 1):
			if i >= wt[0]:
				dp[i][0] = val[0]
		for i in range(1, W + 1):
			for j in range(1, n):
				npk = dp[i][j - 1]
				pk = 0
				if i >= wt[j]:
					pk = dp[i - wt[j]][j - 1] + val[j]
				dp[i][j] = max(npk, pk)
		return dp[W][n - 1]


class Solution:

	def solve(self, W, wt, val, n, dp):
		if n < 0 or W == 0:
			return 0
		if dp[n][W] != -1:
			return dp[n][W]
		inc = 0
		if W >= wt[n]:
			inc = self.solve(W - wt[n], wt, val, n - 1, dp) + val[n]
		exc = self.solve(W, wt, val, n - 1, dp)
		dp[n][W] = max(inc, exc)
		return dp[n][W]

	def knapSack(self, W, wt, val, n):
		if n == 1:
			if wt[0] > W:
				return 0
			return val[0]
		dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
		for i in range(1, n + 1):
			inc = 0
			for j in range(1, W + 1):
				if j >= wt[i - 1]:
					inc = dp[i - 1][j - wt[i - 1]] + val[i - 1]
				exc = dp[i - 1][j]
				dp[i][j] = max(inc, exc)
		return dp[n][W]