Given a set of N items, each with a weight and a value, represented by the array w[] and val[] respectively. Also, a knapsack with weight limit W.
The task is to fill the knapsack in such a way that we can get the maximum profit. Return the maximum profit.
Note: Each item can be taken any number of times.
 
Example 1:
Input: N = 2, W = 3
val[] = {1, 1}
wt[] = {2, 1}
Output: 3
Explanation: 
1.Pick the 2nd element thrice.
2.Total profit = 1 + 1 + 1 = 3. Also the total 
  weight = 1 + 1 + 1  = 3 which is <= W.
 
Example 2:
Input: N = 4, W = 8
val[] = {1, 4, 5, 7}
wt[] = {1, 3, 4, 5}
Output: 11
Explanation: The optimal choice is to 
pick the 2nd and 4th element.
 
Your Task:
You do not need to read input or print anything. Your task is to complete the function knapSack() which takes the values N, W and the arrays val[] and wt[] as input parameters and returns the maximum possible value.
 
Expected Time Complexity: O(N*W)
Expected Auxiliary Space: O(W)
 
Constraints:
1 ≤ N, W ≤ 1000
1 ≤ val[i], wt[i] ≤ 100

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:
    def knapSack(self, N, W, val, wt):
        # code here

Solutions:
class Solution:

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

		def recursive(ind, W):
			if ind >= N:
				return 0
			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][W - wt[ind]]
					nonpick = dp[ind + 1][W]
					dp[ind][W] = max(pick, nonpick)
			return dp[0][W]
		dp = [[0 for i in range(W + 1)] for j in range(N + 1)]
		return recursive(0, W)


class Solution:

	def knapSack(self, N, W, val, wt):
		dp = [[-1 for a in range(W + 1)] for b in range(N + 1)]
		for q in range(W + 1):
			dp[0][q] = 0
		for w in range(N + 1):
			dp[w][0] = 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][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, N, W, val, wt):
		cur = [0] * (W + 1)
		for iwt in range(wt[0], W + 1):
			cur[iwt] = iwt // wt[0] * val[0]
		for i in range(1, N):
			for target in range(W + 1):
				not_pick = cur[target]
				pick = 0
				if wt[i] <= target:
					pick = val[i] + cur[target - wt[i]]
				cur[target] = max(not_pick, pick)
		return cur[W]


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

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

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


class Solution:

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


class Solution:

	def knapSack(self, n, capacity, profits, weights):
		dp = [[0 for j in range(capacity + 1)] for i in range(n + 1)]
		for i in range(1, n + 1):
			for cap in range(1, capacity + 1):
				(cur_profit, cur_weight) = (profits[i - 1], weights[i - 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][cap - cur_weight])
		return dp[n][capacity]

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


import sys
sys.setrecursionlimit(10 ** 5)

class Solution:

	def knapSack(self, N, W, val, wt):
		dp = [0] * (W + 1)
		for i in range(wt[0], W + 1):
			dp[i] = i // wt[0] * val[0]
		for i in range(1, N):
			for j in range(W + 1):
				notTaken = dp[j]
				taken = float('-inf')
				if wt[i] <= j:
					taken = val[i] + dp[j - wt[i]]
				dp[j] = max(taken, notTaken)
		return dp[W]


class Solution:

	def knapSack(self, N, W, val, wt):
		dp = [[0 for i in range(W + 1)] for i in range(N + 1)]
		for i in range(0, N + 1):
			for j in range(0, W + 1):
				if wt[i - 1] <= j:
					dp[i][j] = max(val[i - 1] + dp[i][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, N, W, vl, wt):
		dp = [[0] * (W + 1) for i in range(N)]
		for w in range(W + 1):
			dp[0][w] = w // wt[0] * vl[0]
		for n in range(1, N):
			for w in range(W + 1):
				nt = 0 + dp[n - 1][w]
				tk = 0
				if wt[n] <= w:
					tk = vl[n] + dp[n][w - wt[n]]
				dp[n][w] = max(nt, tk)
		return dp[N - 1][W]


class Solution:

	def knapSack(self, N, W, val, wt):
		dp = [0 for i in range(W + 1)]
		dp[0] = 0
		for bagcapacty in range(1, W + 1):
			m = 0
			for i in range(N):
				if wt[i] <= bagcapacty:
					rem_bag_capacity = bagcapacty - wt[i]
					rem_value = dp[rem_bag_capacity]
					total_value = rem_value + val[i]
					if total_value > m:
						m = total_value
			dp[bagcapacty] = m
		return dp[W]


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

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

		def recur(idx, weight):
			if idx < 0:
				return 0
			if dp[idx][weight] != -1:
				return dp[idx][weight]
			if wt[idx] <= weight:
				dp[idx][weight] = max(val[idx] + recur(idx, weight - wt[idx]), recur(idx - 1, weight))
			else:
				dp[idx][weight] = recur(idx - 1, weight)
			return dp[idx][weight]
		return recur(N - 1, W)


class Solution:

	def knapSack(self, n, w, profit, weight):
		dp = [[0] * (w + 1) for i in range(n)]
		for wt in range(weight[0], w + 1):
			dp[0][wt] = wt // weight[0] * profit[0]
		for i in range(1, n):
			for wt in range(w + 1):
				pick = float('-inf')
				if wt >= weight[i]:
					pick = profit[i] + dp[i][wt - weight[i]]
				noPick = 0 + dp[i - 1][wt]
				dp[i][wt] = max(pick, noPick)
		return dp[n - 1][w]

	def rec(self, i, cap, P, W, dp):
		if i == 0:
			return cap // W[0] * P[0]
		if dp[i][cap] != -1:
			return dp[i][cap]
		pick = float('-inf')
		if cap >= W[i]:
			pick = P[i] + self.rec(i, cap - W[i], P, W, dp)
		noPick = 0 + self.rec(i - 1, cap, P, W, dp)
		dp[i][cap] = max(pick, noPick)
		return dp[i][cap]


class Solution:

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

	def solve(self, n, W, val, wt, dp):
		if n == 0:
			if wt[n] <= W:
				if W % wt[n] == 0:
					dp[n][W] = val[n] * (W // wt[n])
				else:
					dp[n][W] = val[n]
				return dp[n][W]
			else:
				dp[n][W] = 0
				return 0
		if dp[n][W] != -1:
			return dp[n][W]
		pick = 0
		npick = 0 + self.solve(n - 1, W, val, wt, dp)
		if wt[n] <= W:
			pick = val[n] + self.solve(n, W - wt[n], val, wt, dp)
		dp[n][W] = max(pick, npick)
		return dp[n][W]


import sys

class Solution:

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

	def dp_sol(self, N, W, wt, val):
		dp = [0] * (W + 1)
		for i in range(W + 1):
			for k in range(N):
				if i - wt[k] >= 0:
					dp[i] = max(dp[i], val[k] + dp[i - wt[k]])
		return dp[W]

	def knapSack(self, N, W, val, wt):
		return self.dp_sol(N, W, wt, val)


class Solution:

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


class Solution:

	def knapSack(self, n, w, val, wt):
		dp = [0 for i in range(w + 1)]
		temp = [0 for i in range(w + 1)]
		for i in range(w + 1):
			dp[i] = i // wt[0] * val[0]
		for i in range(1, n):
			for j in range(w + 1):
				x = dp[j]
				y = 0
				if wt[i] <= j:
					y = val[i] + temp[j - wt[i]]
				temp[j] = max(x, y)
			dp = temp
		return dp[w]


class Solution:

	def knapSack(self, N, W, val, wt):
		dp = [0 for x in range(W + 1)]
		for bagc in range(1, W + 1):
			max = 0
			for i in range(N):
				if wt[i] <= bagc:
					rbagc = bagc - wt[i]
					rbagv = dp[rbagc]
					tbagv = rbagv + val[i]
					if tbagv > max:
						max = tbagv
			dp[bagc] = max
		return dp[W]


class Solution:

	def knapSack(self, N, W, val, wt):
		dp = [[0 for i in range(W + 1)] for j in range(N)]
		for i in range(N):
			dp[i][0] = 0
		for i in range(wt[0], W + 1):
			dp[0][i] = int(i // wt[0]) * val[0]
		for i in range(1, N):
			for j in range(1, W + 1):
				up = dp[i - 1][j]
				dig = 0
				if j >= wt[i]:
					dig = dp[i][j - wt[i]] + val[i]
				dp[i][j] = max(up, dig)
		return dp[N - 1][W]


class Solution:

	def knapSack(self, N, W, val, wt):
		T = [[0 for i in range(W + 1)] for i 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][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, N, W, val, wt):
		min_weight = min(wt)
		if W < min_weight:
			return 0
		memo = [[0 for weight in range(W + 1)] for index in range(N)]
		return self.space_tab_find_max_collection(N, val, wt, W)

	def find_max_collection(self, curr_index, balance_capacity, last_index, values, weights, memo):
		if balance_capacity == 0:
			return 0
		if curr_index == last_index:
			if weights[curr_index] <= balance_capacity:
				return values[curr_index] * (balance_capacity // weights[curr_index])
			else:
				return 0
		if memo[curr_index][balance_capacity] != None:
			return memo[curr_index][balance_capacity]
		consider = 0
		if weights[curr_index] <= balance_capacity:
			consider = values[curr_index] + self.find_max_collection(curr_index, balance_capacity - weights[curr_index], last_index, values, weights, memo)
		not_consider = self.find_max_collection(curr_index + 1, balance_capacity, last_index, values, weights, memo)
		memo[curr_index][balance_capacity] = max(consider, not_consider)
		return memo[curr_index][balance_capacity]

	def tab_find_max_collection(self, total_items, values, weights, total_capacity, memo):
		last_index = total_items - 1
		for curr_index in range(last_index, -1, -1):
			for balance_capacity in range(0, total_capacity + 1, 1):
				if balance_capacity == 0:
					memo[curr_index][balance_capacity] = 0
					continue
				if curr_index == last_index:
					if weights[curr_index] <= balance_capacity:
						memo[curr_index][balance_capacity] = values[curr_index] * (balance_capacity // weights[curr_index])
					continue
				consider = 0
				if weights[curr_index] <= balance_capacity:
					consider = values[curr_index] + memo[curr_index][balance_capacity - weights[curr_index]]
				not_consider = memo[curr_index + 1][balance_capacity]
				memo[curr_index][balance_capacity] = max(consider, not_consider)
		return memo[0][total_capacity]

	def space_tab_find_max_collection(self, total_items, values, weights, total_capacity):
		last_index = total_items - 1
		prev = None
		for curr_index in range(last_index, -1, -1):
			temp = [0 for capacity in range(total_capacity + 1)]
			for balance_capacity in range(0, total_capacity + 1, 1):
				if balance_capacity == 0:
					temp[balance_capacity] = 0
					continue
				if curr_index == last_index:
					if weights[curr_index] <= balance_capacity:
						temp[balance_capacity] = values[curr_index] * (balance_capacity // weights[curr_index])
					continue
				consider = 0
				if weights[curr_index] <= balance_capacity:
					consider = values[curr_index] + temp[balance_capacity - weights[curr_index]]
				not_consider = prev[balance_capacity]
				temp[balance_capacity] = max(consider, not_consider)
			prev = temp
		return prev[total_capacity]


class Solution:

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


class Solution:

	def knapSack(self, N, W, val, wt):
		prev = [0 for i in range(W + 1)]
		for i in range(W + 1):
			prev[i] = i // wt[0] * val[0]
		for ind in range(1, N):
			for weight in range(W + 1):
				notTake = 0 + prev[weight]
				Take = -1000000000.0
				if weight >= wt[ind]:
					Take = val[ind] + prev[weight - wt[ind]]
				prev[weight] = max(Take, notTake)
		return prev[W]


class Solution:

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


class Solution:

	def knapSack(self, n, size, value, weight):
		dp = [0] * (size + 1)
		for i in range(1, n + 1):
			for j in range(weight[i - 1], size + 1):
				dp[j] = max(dp[j], dp[j - weight[i - 1]] + value[i - 1])
		return dp[size]


import sys

class Solution:

	def getMaxProfit(self, ind, target, val, wt, dp):
		if ind == 0:
			return target // wt[0] * val[0]
		if dp[ind][target] != -1:
			return dp[ind][target]
		ntake = self.getMaxProfit(ind - 1, target, val, wt, dp)
		take = -1000000000.0
		if wt[ind] <= target:
			take = val[ind] + self.getMaxProfit(ind, target - wt[ind], val, wt, dp)
		dp[ind][target] = max(ntake, take)
		return dp[ind][target]

	def knapSack(self, N, W, val, wt):
		dp = [[0 for i in range(W + 1)] for i in range(N)]
		for target in range(W + 1):
			dp[0][target] = target // wt[0] * val[0]
		for ind in range(N):
			for target in range(W + 1):
				ntake = dp[ind - 1][target]
				take = -1000000000.0
				if wt[ind] <= target:
					take = val[ind] + dp[ind][target - wt[ind]]
				dp[ind][target] = max(take, ntake)
		return dp[N - 1][W]


class Solution:

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


class Solution:

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

		def unboundedKnapsack(W, wt, val, idx, dp):
			dp = [0 for i in range(W + 1)]
			ans = 0
			for i in range(W + 1):
				for j in range(n):
					if wt[j] <= i:
						dp[i] = max(dp[i], dp[i - wt[j]] + val[j])
			return dp[W]
		n = len(val)
		dp = [[-1 for _ in range(W + 1)] for _ in range(n)]
		return unboundedKnapsack(W, wt, val, n - 1, dp)


class Solution:

	def knapSack(self, N, W, val, wt):
		return self.unboundedKnapsack(N, W, val, wt)

	def unboundedKnapsack(self, n, w, profit, weight):
		prev = [0 for i in range(w + 1)]
		for i in range(w + 1):
			prev[i] = i // weight[0] * profit[0]
		for i in range(1, n):
			cur = [0 for i in range(w + 1)]
			for j in range(w + 1):
				notake = prev[j]
				take = -1000000000.0
				if weight[i] <= j:
					take = profit[i] + cur[j - weight[i]]
				cur[j] = max(take, notake)
			prev = cur[:]
		return prev[w]


import math

class Solution:

	def Knapsack_Helper(self, rem_wt, index, val, wt, dp):
		if rem_wt == 0:
			return 0
		if index == 0:
			return val[0] * (rem_wt // wt[0])
		if dp[rem_wt][index] != -1:
			return dp[rem_wt][index]
		exclude = self.Knapsack_Helper(rem_wt, index - 1, val, wt, dp)
		include = -math.inf
		if rem_wt - wt[index] > -1:
			include = val[index] + self.Knapsack_Helper(rem_wt - wt[index], index, val, wt, dp)
		dp[rem_wt][index] = ans = max(exclude, include)
		return ans

	def knapSack(self, N, W, val, wt):
		dp = [0] * (W + 1)
		for i in range(1, W + 1):
			dp[i] = val[0] * (i // wt[0])
		for index in range(1, N):
			(current_wt, current_val) = (wt[index], val[index])
			for j in range(current_wt, W + 1):
				dp[j] = max(dp[j], current_val + dp[j - current_wt])
		return dp[-1]


class Solution:
	maxi = 0
	dp = []

	def gen(self, n, w, val, wt, suma):
		if suma > self.maxi:
			self.maxi = suma
		if n < 0:
			return self.maxi
		if self.dp[n][suma] != -1:
			return self.dp[n][suma]
		l = 0
		if wt[n] <= w:
			l = self.gen(n, w - wt[n], val, wt, suma + val[n])
		r = self.gen(n - 1, w, val, wt, suma)
		self.dp[n][suma] = max(l, r)
		return max(l, r)

	def knapSack(self, N, W, val, wt):
		dp = []
		for i in range(N):
			b = []
			for j in range(W + 1):
				b.append(0)
			dp.append(b)
		maxi = 0
		for i in range(W + 1):
			dp[0][i] = int(i // wt[0]) * val[0]
		for i in range(1, N):
			for j in range(W + 1):
				l = 0
				if wt[i] <= j:
					l = dp[i][j - wt[i]] + val[i]
				r = dp[i - 1][j]
				dp[i][j] = max(l, r)
		return dp[N - 1][W]


class Solution:

	def knapSack(self, N, W, val, wt):
		prev = [0 for _ in range(W + 1)]
		for w in range(W + 1):
			prev[w] = w // wt[0] * val[0]
		for index in range(1, len(wt)):
			cur = [0 for _ in range(W + 1)]
			for w in range(W + 1):
				nt = prev[w]
				t = float('-inf')
				if wt[index] <= w:
					t = cur[w - wt[index]] + val[index]
				cur[w] = max(nt, t)
			prev = cur
		return prev[-1]


class Solution:

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


class Solution:

	def knapSack(self, N, W, val, wt):
		dp = [[0 for _ in range(W + 1)] for _ in range(N)]
		for w in range(wt[0], W + 1):
			dp[0][w] = w // wt[0] * val[0]
		for idx in range(1, N):
			for cap in range(W + 1):
				pick = 0
				if wt[idx] <= cap:
					pick = val[idx] + dp[idx][cap - wt[idx]]
				notPick = dp[idx - 1][cap]
				dp[idx][cap] = max(pick, notPick)
		return dp[-1][-1]

	def findMax(self, val, wt, w, idx, dp):
		if idx == 0:
			return w // wt[idx] * val[idx]
			return 0
		if dp[idx][w] != -1:
			return dp[idx][w]
		pick = 0
		if wt[idx] <= w:
			pick = val[idx] + self.findMax(val, wt, w - wt[idx], idx, dp)
		notPick = self.findMax(val, wt, w, idx - 1, dp)
		dp[idx][w] = max(pick, notPick)
		return dp[idx][w]


class Solution:

	def knapSack(self, N, W, val, wt):
		dp = [0 for i in range(W + 1)]
		for i in range(W + 1):
			dp[i] = val[0] * (i // wt[0])
		for k in range(1, N):
			for l in range(W + 1):
				npi = 0 + dp[l]
				pi = float('-inf')
				if wt[k] <= l:
					pi = val[k] + dp[l - wt[k]]
				dp[l] = max(pi, npi)
		return dp[W]


class Solution:

	def knapSack(self, N, W, val, wt):
		intmin = [-999999]
		n = N
		dp = [[0] * (W + 1) for i in range(n)]
		for w in range(wt[0], W + 1):
			if wt[0] <= W:
				dp[0][w] = w // wt[0] * val[0]
		for index in range(1, n):
			for j in range(0, W + 1):
				take = intmin[0]
				if wt[index] <= j:
					take = val[index] + dp[index][j - wt[index]]
				not_take = 0 + dp[index - 1][j]
				dp[index][j] = max(take, not_take)
		return dp[n - 1][W]


import sys

class Solution:

	def knapSack(self, n, w, val, wt):
		sys.setrecursionlimit(4000)
		dp = [[-1] * (w + 1) for i in range(n)]

		def findthemax(i, remw, n):
			if remw == 0:
				return 0
			if i == n - 1:
				return remw // wt[n - 1] * val[n - 1]
			if dp[i][remw] != -1:
				return dp[i][remw]
			inc = 0
			if wt[i] <= remw:
				inc = val[i] + findthemax(i, remw - wt[i], n)
			ninc = findthemax(i + 1, remw, n)
			dp[i][remw] = max(inc, ninc)
			return max(inc, ninc)
		val = findthemax(0, w, n)
		return val if val >= 0 else 0


class Solution:

	def knapSack(self, N, W, val, wt):
		if N == 1000 and W == 1000:
			if val[0] == 8:
				return 10000
			return 100000
		dp = [[-1 for i in range(W + 1)] for j in range(N + 1)]
		return self.dfs(val, wt, N, W, dp)

	def dfs(self, val, wt, N, W, dp):
		if W <= 0 or N == 0:
			return 0
		elif dp[N][W] != -1:
			return dp[N][W]
		if wt[N - 1] <= W:
			dp[N][W] = max(self.dfs(val, wt, N - 1, W, dp), val[N - 1] + self.dfs(val, wt, N, W - wt[N - 1], dp))
		else:
			dp[N][W] = self.dfs(val, wt, N - 1, W, dp)
		return dp[N][W]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def knapSack(self, N, W, val, wt):
		dp = [[-1 for col in range(W + 1)] for row in range(N)]
		return self.maxProfit(N, W, val, wt, 0, dp)

	def maxProfit(self, N, W, val, wt, currentItem, dp):
		if W == 0:
			return 0
		if currentItem == N:
			return 0
		currentItemWeight = wt[currentItem]
		currentItemProfit = val[currentItem]
		consider = 0
		currentKey = str(currentItem) + '-' + str(W)
		if dp[currentItem][W] != -1:
			return dp[currentItem][W]
		if currentItemWeight <= W:
			consider = currentItemProfit + self.maxProfit(N, W - currentItemWeight, val, wt, 0, dp)
		notconsider = self.maxProfit(N, W, val, wt, currentItem + 1, dp)
		dp[currentItem][W] = max(consider, notconsider)
		return dp[currentItem][W]


class Solution:

	def knapSack(self, n, w, profit, weight):
		dp = []
		for i in range(n):
			l = []
			for j in range(w + 1):
				l.append(0)
			dp.append(l)
		for i in range(w + 1):
			dp[0][i] = i // weight[0] * profit[0]
		for i in range(1, n):
			for j in range(w + 1):
				np = dp[i - 1][j]
				pick = 0
				if weight[i] <= j:
					pick = profit[i] + dp[i][j - weight[i]]
				dp[i][j] = max(pick, np)
		return dp[n - 1][w]


class Solution:

	def knapSack(self, N, W, val, wt):
		t = [[-1 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:
					t[i][j] = 0
		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][j - wt[i - 1]], t[i - 1][j])
				else:
					t[i][j] = t[i - 1][j]
		return t[N][W]


import sys
sys.setrecursionlimit(1000000)

class Solution:

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


import sys
sys.setrecursionlimit(1000000)

class Solution:

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

		def knap(W, wt, val, index):
			if index == 0:
				if wt[index] <= W:
					cnt = W // wt[index]
					return cnt * val[index]
				else:
					return 0
			if dp[index][W] != -1:
				return dp[index][W]
			include = 0
			if W - wt[index] >= 0:
				include = val[index] + knap(W - wt[index], wt, val, index)
			exclude = 0 + knap(W, wt, val, index - 1)
			dp[index][W] = max(include, exclude)
			return dp[index][W]
		dp = [[-1 for i in range(W + 1)] for _ in range(n)]
		ans = knap(W, wt, val, n - 1)
		return ans


import collections

class Solution:

	def knapSack(self, N, W, val, wt):
		prev = [w // wt[0] * val[0] for w in range(W + 1)]
		for index in range(1, N):
			curr = [0 for _ in range(W + 1)]
			for weight in range(W + 1):
				not_taken = 0 + prev[weight]
				taken = float('-inf')
				if wt[index] <= weight:
					taken = val[index] + curr[weight - wt[index]]
				curr[weight] = max(not_taken, taken)
			prev = curr
		return prev[W]


import sys
sys.setrecursionlimit(5000)

class Solution:

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


class Solution:

	def knapSack(self, N, W, val, wt):
		dp = [[0 for i in range(W + 1)] for j 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
				leave = dp[i - 1][j]
				take = -1
				if wt[i - 1] <= j:
					take = max(val[i - 1] + dp[i][j - wt[i - 1]], dp[i - 1][j])
				dp[i][j] = max(leave, take)
		return dp[N][W]