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):
N, W = map(int, input().split())
wvs = []
for _ in range(N):
    wvs.append(list(map(int, input().split())))


def chmax(x, w1, w2, diff):
    if dp[x][w1] < dp[x-1][w2]+diff:
        dp[x][w1] = dp[x-1][w2]+diff
        return True
    return False


dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
    for sum_w in range(W+1):
        
        if sum_w-wvs[i][0] >= 0:
            
            chmax(i+1, sum_w, sum_w-wvs[i][0], wvs[i][1])
        chmax(i+1, sum_w, sum_w, 0)  
print(max(dp[N]))

Solution (Python):
N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]
 
dp = [[0 for _ in range(W+10)] for _ in range(N+10)]
 
for i, (item_weight, item_value) in enumerate(items):
    for total_weight in range(W+1):
        if (total_weight-item_weight) >= 0:
            dp[i+1][total_weight] = dp[i][total_weight-item_weight] + item_value
        dp[i+1][total_weight] = max(dp[i+1][total_weight], dp[i][total_weight])
        
print(dp[N][W])

Solution (Python):
N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]

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

for i, (item_weight, item_value) in enumerate(items):
    for total_weight in range(W+1):
        if (total_weight-item_weight) >= 0:
            dp[i+1][total_weight] = max(dp[i][total_weight-item_weight] + item_value, dp[i+1][total_weight])
        dp[i+1][total_weight] = max(dp[i+1][total_weight], dp[i][total_weight])
        
print(dp[N][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 + 1)]
for i in range(n):
  for j in range(w + 1):
    if j + wv[i][0] <= w:
      dp[i + 1][j + wv[i][0]] = max(dp[i + 1][j + wv[i][0]], dp[i][j] + wv[i][1])
    dp[i + 1][j] = max(dp[i][j], dp[i + 1][j])
print(max(dp[-1]))

Solution (Python):
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]+v, dp[w:], out=dp[w:])  
    

print(dp[-1])


"""
今dpは一次元配列
dp[:-w]は後ろからw個より前の要素, つまり(N-w)個
dp[w:]は前からw個より後ろの要素, つまり(N-w)個
よって形状が一致する
"""

"""
dp[:-w]は今見ている"重さw, 価値v"の荷物を入れることのできる状態のナップサック
dp[:-w]+vをすることで、今見ているその荷物を入れた時の価値の総和になる.
今、"重さw, 価値v"の荷物を入れたナップサックと、dp[w:]を比較する。
それぞれの要素について大きい方が新しい要素となり、out=dp[w:]によって上書きされる。
maxmimumが返すのはnp配列。そのnp配列の形状は比較対象となっている配列の形状と一致するから、
問題なく上書きできる
"""

Solution (Python):
def knapsack(N,W,weight,value):
  
  inf=float("inf")
  dp=[[-inf for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0

  
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w: 
        dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
      else: 
        dp[i+1][w]=dp[i][w]
  return dp[N][W]

N,W = map(int,input().split())
lstw = [0 for i in range(N)]
lstv = [0 for i in range(N)]

for i in range(N):
  w,v = map(int, input().split() ) 
  lstw[i] = w
  lstv[i] = v
  
ret = knapsack(N,W,lstw,lstv)
  
print(ret)

Solution (Python):
import numpy as np
import sys

N, W = [int(v) for v in input().strip().split(' ')]
dp = np.zeros(W + 1, dtype = 'uint64')

for _ in range(N):
    w, v = [int(v) for v in sys.stdin.readline().split(' ')]
    np.maximum(dp[:-w] + v, dp[w:], out = dp[w:])

print(dp[W])

Solution (Python):
N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]

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

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

res = dp[N][W]
print(res)

Solution (Python):
from collections import Counter,defaultdict
import sys,bisect,math,itertools,string,queue
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

n,w = inpl()
ww = [0] * n
vv = [0] * n
for i in range(n):
    ww[i],vv[i] = inpl()
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 >= ww[i]:
            dp[i+1][j] = max(dp[i][j], dp[i][j-ww[i]]+vv[i])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[n][w])

Solution (Python):
def main():

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

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

    max_v = 0
    for i in range(N):
        w, v = map(int, input().split())
        for j in range(W+1):
            if j - w >= 0:
                dp[(i+1)%2][j] = max(dp[i%2][j], dp[i%2][j-w]+v)
            else:
                dp[(i+1)%2][j] = dp[i%2][j]
        max_v = max(max(dp[(i+1)%2]), max_v)

    return max_v

if __name__ == '__main__':
    print(main())

Solution (Python):
def main():

    N, W = map(int, input().split())
    cur = dict()
    cur[0] = 0
    for _ in range(N):
        w, v = map(int, input().split())
        temp = cur.copy()
        for w1 in temp:
            if w1 + w <=W:
                if w1+w not in cur:
                    cur[w1+w] = temp[w1] + v
                else:
                    cur[w1+w] = max(cur[w1+w], temp[w1]+v)
    return max(cur.values()) 


if __name__ == '__main__':
    print(main())

Solution (Python):
def A(w, v, n,V):
    mem=[0 for i in range(V+1)]
    if n == 0 or V == 0:
        return 0
 
    for i in range(n):
        for j in range(V,w[i]-1,-1):
            m=v[i]+ mem[j - w[i]]
            if m>mem[j]:
                mem[j]=m
    return mem[V]
n,V=input().split()
n,V=int(n),int(V)
 
w=[0]*n
v=[0]*n
for i in range(n):
  x,y=input().split()
  w[i],v[i]=int(x),int(y)
 
print(A(w,v,n,V))

Solution (Python):
from collections import defaultdict

n, w = [int(x) for x in input().split()]
d = []
for _ in range(n):
    ww, nu = [int(x) for x in input().split()]
    d.append((ww, nu))



dd = defaultdict(lambda: defaultdict(int))
for ww in range(w+1):
    dd[0][ww] = 0

for nn in range(n+1):
    dd[nn][0] = 0

for nn in range(1, n+1):
    www, nu = d[nn-1]
    for ww in range(1, w+1):
        
        cur = dd[nn-1][ww]

        
        if www <= ww:
            rem_ww = ww - www
            cand = dd[nn-1][rem_ww] + nu
            if cand > cur:
                cur = cand

        dd[nn][ww] = cur

print(dd[n][w])

Solution (Python):
N, capW = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]
 
def knapsack01(items, capW):
    dp = [0] * (capW+1)
    for wi, vi in items:
        for w in reversed(range(wi, capW+1)):
            v0 = dp[w-wi] + vi
            if v0 > dp[w]:
                dp[w] = v0
    return max(dp)
 
print(knapsack01(items, capW))

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

Solution (Python):
n, w = map(int, input().split())
wv_array = [[int(x) for x in input().split()] for y in range(n)]

dp = [[0 for x in range(w + 1)] for y in range(n+1)]

index = 1
for ww, vv in wv_array:
    for capacity in range(1, w + 1):
        if ww <= capacity:
            dp[index][capacity] = max(dp[index - 1][capacity - ww] + vv, dp[index-1][capacity])
        else:
            dp[index][capacity] = dp[index - 1][capacity]
    index += 1
print(max(dp[n]))

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
values=[[0]*(w+1) for i in range(n+1)]

for i in range(n):
    values[i+1][wv[i][0]]=max(values[i+1][wv[i][0]],wv[i][1])
    for j in range(1,w+1):
        if values[i][j]!=0:
            if wv[i][0]+j<=w:
                values[i+1][wv[i][0]+j]=max(values[i+1][wv[i][0]+j],values[i][j]+wv[i][1])
            values[i+1][j]=max(values[i+1][j],values[i][j])

print(max(values[-1]))

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

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

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

Solution (Python):
N,W = list(map(int, input().split()))
m = []
v = []
dp = [[0 for i in range(W+1)]for j in range(N+1)]
for i in range(N):
    a,b = map(int, input().split())
    m.append(a)
    v.append(b)

for i in range(N):
    for j in range(W):
        if j+m[i] <= W:
            dp[i+1][j+m[i]] = max(dp[i][j] + v[i], dp[i+1][j+m[i]])
        dp[i+1][j] = max(dp[i][j], dp[i+1][j])


print(max(dp[-1]))

Solution (Python):
N,W = list(map(int, input().split()))
v = []
m = []
dp = [[-1 for i in range(W+1)]for j in range(N+1)]
for i in range(N):
    a,b = list(map(int, input().split()))
    m.append(a)
    v.append(b)

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

print(max(dp[-1]))

Solution (Python):
N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for _ in range(N)]

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] :
            dp[i+1][j] = max(dp[i][j-wv[i][0]] + wv[i][1], dp[i][j])
        else :
            dp[i+1][j] = dp[i][j]
print(dp[N][W])

Solution (Python):
N, capW = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]

def knapsack01(items, capW):
    dp = [0] * (capW+1)
    for wi, vi in items:
        dp = [v1 if v1 >= v2 else v2 for v1, v2 in zip(dp, [0]*wi + [v+vi for v in dp[:capW-wi+1]])]
    return max(dp)

print(knapsack01(items, capW))

Solution (Python):
N, capW = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]

def knapsack01(items, capW):
    dp = [0] * (capW+1)
    for wi, vi in items:
        for w in reversed(range(wi, capW+1)):
            v0 = dp[w-wi] + vi
            if v0 > dp[w]:
                dp[w] = v0
    return max(dp)

print(knapsack01(items, capW))

Solution (Python):
n,W = map(int,input().split())
table = [[0]*(W+1) for _ in range(n+1)]
for i in range(n):
  w,v = map(int,input().split())
  for k in range(W+1):
    if k < w:
      table[i+1][k] = table[i][k]
    else:
      table[i+1][k] = max(table[i][k],table[i][k-w]+v)

print(table[n][W])

Solution (Python):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)



N, W = map(int, input().split())
w = [0] * N
v = [0] * N

for i in range(N):
    a, b = map(int, input().split())
    w[i] = a
    v[i] = b

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

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

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

print(dp[N][W])

Solution (Python):
n, s = [int(i) for i in  raw_input().split()]
weights = []
values = []

for _ in xrange(n):
    w, v = [int(i) for i in raw_input().split()]
    weights.append(w)
    values.append(v)

def knapsack(weights, values, limit):
    n = len(weights)
    

    prev = [0 for _ in xrange(limit+1)]

    if weights[0] <= limit:
        for w in xrange(weights[0], limit+1):
            prev[w] = values[0]

    for i in xrange(1, n):
        
        current = [0] * (limit+1)
        for w in xrange(1, limit+1):
            current[w] = max(prev[w], current[w])
            if weights[i] <= w:
                current[w] = max(current[w], prev[w-weights[i]] + values[i])
        prev = list(current)

    return prev[-1]



print(knapsack(weights, values, s))

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


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

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

print(dp[N][W])

Solution (Python):
nums, weight = map(int,input().split())
ary  = [0 for i in range(nums)]
for i in range(nums):
    ary[i] = list(map(int,input().split()))
dp =[[0 for i in range(weight+1)]for i in range(nums+1)]
 
check = 0
for i in range(nums):
    for x in range(weight+1):
        if x - ary[i][0] >= 0:
            check = dp[i][x -ary[i][0]] + ary[i][1]
            if check > dp[i+1][x]:
                dp[i+1][x] = check
 
        check = dp[i][x]
        if check > dp[i+1][x]:
            dp[i+1][x] = check
 
print(dp[nums][weight])

Solution (Python):
n,tw = map(int, input().split())
wt = [];    val = []
for i in range(n):
    a,b = map(int, input().split())
    wt.append(a);   val.append(b)
dp = [[0 for i in range(tw+1)] for j in range(n+1)]
for i in range(n):
    for j in range(1,tw+1):
        if j < wt[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], val[i]+dp[i][j-wt[i]])
print(dp[n][tw])

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main2(): 
    N, W = LI()
    things = []
    for i in range(N):
        things.append(LI())

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

    for i, wv in enumerate(things):  
        w, v = wv
        if i == 0:
            for weight in range(W+1):  
                knapsack_dp[i][weight] = 0 if weight < w else v
        else:
            for weight in range(W+1):
                if weight-w < 0:
                    knapsack_dp[i][weight] = knapsack_dp[i-1][weight]
                else:
                    knapsack_dp[i][weight] = max(knapsack_dp[i-1][weight], knapsack_dp[i-1][weight-w]+v)

    print(knapsack_dp[N-1][W])

def main():
    N, W = LI()
    things = []
    for i in range(N):
        things.append(LI())

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

    
    for i, wv in enumerate(things):  
        w, v = wv
        if i == 0:
            for weight in range(W+1):  
                knapsack_dp[i][weight] = 0 if weight != w else v
        else:
            for weight in range(W+1):
                if weight-w < 0:
                    knapsack_dp[i][weight] = knapsack_dp[i-1][weight]
                else:
                    knapsack_dp[i][weight] = max(knapsack_dp[i-1][weight], knapsack_dp[i-1][weight-w]+v)

    print(max(knapsack_dp[N-1]))

main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N, W = LI()
    things = []
    for i in range(N):
        things.append(LI())

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

    for i, wv in enumerate(things):  
        w, v = wv
        if i == 0:
            for weight in range(W+1):  
                knapsack_dp[i][weight] = 0 if weight < w else v
        else:
            for weight in range(W+1):
                if weight-w < 0:
                    knapsack_dp[i][weight] = knapsack_dp[i-1][weight]
                else:
                    knapsack_dp[i][weight] = max(knapsack_dp[i-1][weight], knapsack_dp[i-1][weight-w]+v)

    print(knapsack_dp[N-1][W])

main()

Solution (Python):
N,W = map(int,input().split())
wv = [[int(x) for x in input().split()] for i in range(N)]
dp = [[0 for j in range(W+1)] for i in range(N+1)]
for i in range(N):
    for sum_w in range(W+1):
        if wv[i][0] + sum_w < W+1 and dp[i+1][wv[i][0]+sum_w] < dp[i][sum_w] + wv[i][1]:
            dp[i+1][wv[i][0]+sum_w] = dp[i][sum_w] + wv[i][1] 
        if dp[i+1][sum_w] < dp[i][sum_w]:
            dp[i+1][sum_w] = dp[i][sum_w]
print(dp[N][W])

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

Solution (Python):
N,W=map(int,input().split())
A = [list(map(int, input().split())) for i in range(N)]



dp = [[0 for i in range(W+1)] for j in range(N+1)]


for i in range(N):
    for w in range(W+1):
        if w>=A[i][0]:
            dp[i+1][w] = max([dp[i][w-A[i][0]]+A[i][1], dp[i][w]])
        else:
            dp[i+1][w] = dp[i][w]
        
print(int(dp[N][W]))

Solution (Python):
def p_e():
    """
    ナップサック問題（制約厳しい版） 
    """
    N, W = map(int, input().split())
    dp = [0] * (W + 1)
    for i in range(1, N + 1):
        w, v = map(int, input().split())
        NEXT = [0] * (W + 1)
        for j in range(1, W + 1):
            if j - w >= 0:
                NEXT[j] = max(v + dp[j - w], dp[j])
            else:
                NEXT[j] = dp[j]
        dp = NEXT

    print(max(NEXT))


if __name__ == '__main__':
    p_e()

Solution (Python):
def p_d():
    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(v + dp[i - 1][j - w], dp[i - 1][j])
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j])

    print(max(dp[N]))


if __name__ == '__main__':
    p_d()

Solution (Python):
def p_d():
    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(v + dp[i - 1][j - w], dp[i][j], dp[i - 1][j])
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j])

    print(max(dp[N]))


if __name__ == '__main__':
    p_d()

Solution (Python):
N,W = map(int,input().split())
wv_list = [tuple(map(int,input().split())) for _ in range(N)]

memo = [0  for _ in range(W+1)]

for weight,value in wv_list:
    for w in range(W+1)[::-1]:
        if w  >= weight:
            memo[w] = max(memo[w], memo[w-weight]+value)
            
print(memo[W])

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    N,W = map(int,input().split())
    dp = [-1 for _ in range(W+1)]
    dp[W] = 0
    for _ in range(N):
        nm,nv = [int(a) for a in input().split()]
        for j in range(nm,W+1):
            a = nm
            if dp[j] == -1:
                continue
            if dp[j-a] < dp[j] + nv:
                dp[j-a] = dp[j] + nv
    print(max(dp))

if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
from copy import *

N, W = map(int, input().split())
dp1, dp2 = [0] * (W+1), [0] * (W+1)
for i in range(N):
    w, v = map(int, input().split())
    for j in range(W+1):
        if w <= j:
            dp2[j] = max(dp2[j], dp1[j-w]+v)
    dp1 = deepcopy(dp2)
print(max(dp1))

Solution (Python):
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

def sol():
    N, W = map(int, input().split())
    items = [0] * N

    for i in range(N):
        w, v = map(int, input().split())
        items[i] = (v, w)

    dp = [0] * (W + 1)

    for value, weight in items:
        for w in range(W + 1)[:: -1]:
            if w - weight >= 0:
                dp[w] = max(dp[w], dp[w - weight] + value)

    print(dp[W])

sol()

Solution (Python):
from sys import stdin
def main():
  from builtins import int, range
  readline = stdin.readline
  n, w = map(int, readline().split())
  t = [-1] * (w + 1)
  t[w] = 0
  for _ in range(n):
    nw, nv = map(int, readline().split())
    for i in range(nw, w + 1):
      ti = t[i]
      if ti == -1:
        continue
      if t[i - nw] < ti + nv:
        t[i - nw] = ti + nv
  print(max(t))
main()

Solution (Python):
from sys import stdin
def main():
  from builtins import int, range
  readline = stdin.readline
  n, w = map(int, readline().split())
  t = [-1 for i in range(w + 1)]
  t[w] = 0
  for _ in range(n):
    nw, nv = map(int, readline().split())
    for i in range(nw, w + 1):
      ti = t[i]
      if ti == -1:
        continue
      if t[i - nw] < ti + nv:
        t[i - nw] = ti + nv
  print(max(t))
main()

Solution (Python):
from sys import stdin
def main():
  from builtins import int, range
  readline = stdin.readline
  n, w = [int(e) for e in readline().split()]
  t = [-1 for i in range(w + 1)]
  t[w] = 0
  for _ in range(n):
    nw, nv = [int(e) for e in readline().split()]
    for i in range(nw, w + 1):
      if t[i] == -1:
        continue
      if t[i - nw] < t[i] + nv:
        t[i - nw] = t[i] + nv
  print(max(t))
main()

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+1)]

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

print(dp[N][W])

Solution (Python):
def d():
    N,W = map(int, input().split())
    nupList = (map(int, input().split()) for _ in range(N))
    dp = [0] * (W + 1)

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

    return dp[W]

print(d())

Solution (Python):
def d():
    N,W = map(int, input().split())
    nupList = (map(int, input().split()) for _ in range(N))
    dp = [0] * (W + 1)

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

    return max(dp)

print(d())

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())

Solution (Python):

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

Solution (Python):
N, W = list(map(int, input().split()))
W += 1
A = [0] * W
wi, vi = list(map(int, input().split()))
A[wi] = vi

for _ in range(N-1):
    wi, vi = list(map(int, input().split()))
    tmp = [0] * W

    for w in range(W):
        if w-wi < 0:
            tmp[w] = A[w]
        else:
            tmp[w] = max(A[w-wi] + vi, A[w])

    A = tmp

print(max(A))

Solution (Python):
n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for i 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 = [tuple(map(int, input().split())) for i 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())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

dp_v = [0] * (W+1)

for i in range(N):
    for j in (reversed(range(W+1))):
        if (j == 0 or dp_v[j] != 0) and j+w[i] <= W and dp_v[j+w[i]] < dp_v[j] + v[i]:
            dp_v[j+w[i]] = dp_v[j] + v[i]
            
max = 0        
for i in range(W+1):
    if max < dp_v[i]:
        max = dp_v[i]

print(max)

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+1)]

for i in range(1, N+1):
    weight = WV[i-1][0]
    value = WV[i-1][1]
    for w in range(W+1):
        if w-weight<0:
            dp[i][w] = dp[i-1][w]
        else:
            dp[i][w] = max(dp[i-1][w-weight]+value, dp[i-1][w])
print(dp[N][W])

Solution (Python):

def knapsack(target, W, V): 
    P = [[0] * (target + 1) for _ in range(len(V))]
    for vi in range(len(V)):
        row, prev = P[vi], P[vi - 1]
        for w in range(target + 1):
            if vi > 0:
                row[w] = prev[w] 
                if w >= W[vi]:
                    new = P[vi - 1][w - W[vi]] + V[vi]
                    if new > P[vi][w]: 
                        row[w] = new
            else:
                if w >= W[vi]:
                    row[w] = V[vi]
    return P[len(V) - 1][target]

def knapsack_rec(target, W, V): 
    P = [-1] * (target + 1)
    P[target] = 0 

    for vi in range(len(V)):
        we = W[vi]
        va = V[vi]
        for i in range(we, target + 1):
            if P[i] != -1 and P[i - we] < P[i] + va:
                P[i - we] = P[i] + va

    return max(P)

assert knapsack_rec(15, [6, 5, 6, 6, 3, 7], [5, 6, 4, 6, 5, 2]) == 17

if __name__ == "__main__":
    import sys
    n, w, *r = map(int, sys.stdin.read().split())
    W, V = r[::2], r[1::2]
    ans = knapsack_rec(w, W, V)
    print(ans)

Solution (Python):
n, W = map(int, input().split())
obj = [list(map(int, input().split())) for _ in range(n)]
DP = [[0]*2*W for _ in range(n+1)]

for i in range(1, n+1):
    for w in range(W+1):
        weight, value = obj[i-1]
        DP[i][w] = max(DP[i-1][w], DP[i][w])
        if w + weight <= W:
            DP[i][w + weight] = max(DP[i - 1][w] + value, DP[i][w + weight])

ans = max(DP[n])
print(ans)

Solution (Python):
import sys
import numpy as np
input = sys.stdin.readline
N, W = map(int, input().split())
def knapsack():
  dp = np.zeros((N+1, W+1), dtype=int)
  c = np.arange(1, N+1)
  for i in c:
    w, v = map(int, input().split())
    dp[i][w:] = np.maximum(dp[i-1][w:], dp[i-1][:-w] + v)
    dp[i][:] = np.maximum(dp[i][:], dp[i-1][:])
  return dp[-1][-1]
print(knapsack())

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


if __name__ == '__main__':
    main()

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

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


for i in range(n):
    for j in range(w + 1):
        use = 0
        if j - wv[i][0] >= 0:
            use = dp[i - 1][j - wv[i][0]] + wv[i][1]
        nouse = dp[i - 1][j]

        dp[i][j] = max(use, nouse)

print(max(dp[-1]))

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

Solution (Python):
N,W=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):
  w,v=map(int,input().split())
  for j in range(1,w):
    dp[i][j]=dp[i-1][j]
  for j in range(w,W+1):
    if w<=j:
      dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)
print(dp[N][W])

Solution (Python):
N,W=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):
  w,v=map(int,input().split())
  for j in range(1,W+1):
    if w<=j:
      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):

import sys
input = sys.stdin.readline

def main():
    N, W = tuple(map(int, input().split()))
    A = tuple(tuple(map(int, input().split())) for _ in range(N))
    dp = [0] * (W + 1)
    for i in range(N):
        for j in range(W, A[i][0] - 1, -1):
            dp[j] = max(dp[j], dp[j - A[i][0]] + A[i][1])
    print(dp[-1])


if __name__ == "__main__":
    main()