Problem:
 Score : 100 points    Problem Statement There are N items, numbered 1, 2, \ldots, N .
For each i ( 1 \leq i \leq N ), Item i has a weight of w_i and a value of v_i .  Taro has decided to choose some of the N items and carry them home in a knapsack.
The capacity of the knapsack is W , which means that the sum of the weights of items taken must be at most W .  Find the maximum possible sum of the values of items that Taro takes home.      Constraints  All values in input are integers.  1 \leq N \leq 100  1 \leq W \leq 10^5  1 \leq w_i \leq W  1 \leq v_i \leq 10^9         Input Input is given from Standard Input in the following format:  N  W  w_1  v_1  w_2  v_2  :  w_N  v_N       Output Print the maximum possible sum of the values of items that Taro takes home.        Sample Input 1 3 8
3 30
4 50
5 60      Sample Output 1 90  Items 1 and 3 should be taken.
Then, the sum of the weights is 3 + 5 = 8 , and the sum of the values is 30 + 60 = 90 .       Sample Input 2 5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000      Sample Output 2 5000000000  The answer may not fit into a 32-bit integer type.       Sample Input 3 6 15
6 5
5 6
6 4
6 6
3 5
7 2      Sample Output 3 17  Items 2, 4 and 5 should be taken.
Then, the sum of the weights is 5 + 6 + 3 = 14 , and the sum of the values is 6 + 6 + 5 = 17 .

Solution (Python):

import sys
input = sys.stdin.readline

def knapsack(W: int, weight: "Array[int]", value: "Array[int]") -> int:
    
    dp = [0] * (W + 1)
    for w, v in zip(weight, value):
        for cur_w in range(W, w - 1, -1):
            dp[cur_w] = max(dp[cur_w], dp[cur_w - w] + v)
    return dp[-1]


def main():
    N, W = tuple(map(int, input().split()))
    A = tuple(tuple(map(int, input().split())) for _ in range(N))
    weight, value = zip(*A)
    ans = knapsack(W, weight, value)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
N, W = map(int, input().split())
w = []
v = []
for _ in range(N):
    x, y = map(int,input().split())
    w.append(x)
    v.append(y)
    
dp = [ [0 for i in range(W+1)] for j in range(N+1) ]

for i in range(N):
    for j in range(W+1):
        if j-w[i] >= 0:
            dp[i+1][j] = max( dp[i][j], dp[i][j-w[i]]+v[i] )
        dp[i+1][j] = max(dp[i+1][j],dp[i][j])

print(dp[N][W])

Solution (Python):
N, W = map(int, input().split())
items = [None] * N
for n in range(N):
    w, v = map(int, input().split())
    items[n] = (w, v)

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(N):
    for j in range(W + 1):
        w, v = items[i]
        if j >= w:
            dp[i + 1][j] = max(dp[i][j - w] + v, dp[i][j])
        else:
            dp[i + 1][j] = dp[i][j]
print(dp[N][W])

Solution (Python):


N, W = map(int, input().split())
items = [tuple(map(int, input().split())) for i in range(N)]

dp = [[0 for w_sum in range(W+100)] for i in range(N+100)]

for i in range(N):
    for w_sum in range(W+1):

        
        
        if w_sum-items[i][0] >= 0:
            dp[i+1][w_sum] = max(dp[i+1][w_sum],
                                 dp[i][w_sum-items[i][0]]+items[i][1])

        
        dp[i+1][w_sum] = max(dp[i+1][w_sum], dp[i][w_sum])

print(dp[N][W])

Solution (Python):
n,W=map(int,raw_input().split())
w=[]
val=[]
for i in range(n):
    p=map(int,raw_input().split())
    w.append(p[0])
    val.append(p[1])
dp = [0]*(W+1)
for i in range(n):
    for j in range(W,w[i]-1,-1):
        dp[j]=max(dp[j],dp[j-w[i]]+val[i])
print(dp[-1])

Solution (Python):
n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]

dp = [0]*(w+1)

for i in range(n):
    for j in range(w, wv[i][0]-1, -1):
        dp[j] = max(dp[j], dp[j-wv[i][0]]+wv[i][1])

print(max(dp))

Solution (Python):
n,w = map( int, input().split() )
wv = []
for _ in range(n): wv.append( list( map( int, input().split() ) ) )

dp = [[0]*(w+1) for _ in range(n+1)]
for i in range(n):
    for j in range(w+1):
        if j-wv[i][0] < 0:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max( dp[i-1][j-wv[i][0]]+wv[i][1], dp[i-1][j] )

print(dp[n-1][w])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

N,W = map(int,input().split())

dp = np.zeros(W+1, dtype=np.int64)
for _ in range(N):
    w,v = map(int,input().split())
    np.maximum(dp[w:], dp[:-w] + v, out = dp[w:])

answer = dp.max()
print(answer)

Solution (Python):
n, w = map(int, input().split())
W, V =[0]*n, [0]*n
for i in range(n):
  W[i],V[i] = map(int, input().split())

dp =[[0 for i in range(w+1)] for j in range(n+1)]

for i in range(1,n+1):
  for j in range(w+1):
    if W[i-1] < j+1:
      dp[i][j] = max(dp[i-1][j-W[i-1]]+V[i-1],dp[i-1][j])
    else:
      dp[i][j] = dp[i-1][j]
      
print(dp[n][w])

Solution (Python):
def main():
    n, w = map(int, input().split())
    dp = [[0]*(w+1) for _ in range(n+1)]
    for i in list(range(n+1))[1:]:
        wi, vi = map(int, input().split())
        dp[i] = [max(dp[i-1][j], dp[i-1][j-wi]+vi) if j >= wi else dp[i-1][j] for j in range(w+1)]
    print(max(dp[-1]))

if __name__ == '__main__':
    main()

Solution (Python):
n, w = map(int, input().split())
dp = [[0]*(w+1) for _ in range(n+1)]
for i in list(range(n+1))[1:]:
    wi, vi = map(int, input().split())
    dp[i] = [max(dp[i-1][j], dp[i-1][j-wi]+vi) if j >= wi else dp[i-1][j] for j in range(w+1)]
print(max(dp[-1]))

Solution (Python):
n, w = map(int, input().split())
import numpy as np
dp = np.zeros(w+1, np.int64)
for i in range(n):
    wi, vi = map(int, input().split())
    np.maximum(dp[:-wi]+vi, dp[wi:], out=dp[wi:])
print(max(dp))

Solution (Python):
import numpy as np

n, w = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(n)]
table = np.zeros(w+1, dtype=np.int64)

for i in range(n):
    l = table[:-wv[i][0]]
    r = table[wv[i][0]:]
    np.maximum(l + wv[i][1], r, out = r)

print(table[w])

Solution (Python):
n,w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
dp = [[0]*(w+1) for _ in range(n)]

dp[0][wv[0][0]] = wv[0][1]

for i in range(1,n):
  for j in range(w+1):
    if j < wv[i][0]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(dp[i-1][j-wv[i][0]]+wv[i][1],dp[i-1][j])
      
print(max(max(dp)))

Solution (Python):
import copy

def solve(N, W, w, v):
    dp = [[0]*(W+1) for _ in range(N+2)]
    for i in range(N):
        for sum_w in range(W):
            if sum_w+w[i] <=W:
                dp[i+1][sum_w+w[i]] = max(dp[i][sum_w+w[i]], dp[i][sum_w]+v[i])
        dp[i+2] = copy.copy(dp[i+1])
    return max(dp[-1])

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
w,v=[], []
for i in wv:
    w.append(i[0])
    v.append(i[1])

print(solve(N, W, w, v))

Solution (Python):
N,W=map(int,input().split())
dp=[[0]*(W+1) for _ in range(N+1)]
for i in range(1,N+1):
	w,v=map(int,input().split())
	for j in range(1,W+1):
		if j-w>=0:
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)
		else:
			dp[i][j]=dp[i-1][j]
print(dp[N][W])

Solution (Python):
def DP():
    n,W = map(int, input().split(' '))
    WV = (map(int, input().split(' ')) for _ in range(n))
    dp = [0] * (W+1)

    for w, v in WV:
        for j in range(W, w-1, -1):
            DP = dp[j-w] + v
            if dp[j] < DP:
                dp[j] = DP
    return max(dp)
print(DP())