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.



Sample input:
3 8
3 30
4 50
5 60


Sample output:
90

Submission status: Time Limit Exceeded

Solution code:
from sys import stdout,stdin
def knapsack(C,n,wei,val,mat):
    if(C==0 or n==0):
        return 0
    else:
        if(C>=wei[n-1]):
            a=mat[C-wei[n-1]][n-1]
            b=mat[C][n-1]
            if(a==-1):
                a=knapsack(C-wei[n-1],n-1,wei,val,mat)
                mat[C-wei[n-1]][n-1]=a
            if(b==-1):
                b=knapsack(C,n-1,wei,val,mat)
                mat[C][n-1]=b
            mat[C][n]=max(a+val[n-1],b)
            return (max(a+val[n-1],b))
        else:
            alp=matrix[C][n-1]
            if(alp==-1):
                alp=knapsack(C,n-1,wei,val,mat)
                mat[C][n-1]=alp
                mat[C][n]=alp
            return(alp)
N,W=map(int,stdin.readline().split())
matrix=[[-1 for i in range(0,N+1)]for j in range(0,W+1)]
for i in range(0,len(matrix)):
    matrix[i][0]=0
for i in range(0,len(matrix[0])):
    matrix[0][i]=0
weights=[]
values=[]
for i in range(0,N):
    w,v=map(int,stdin.readline().split())
    weights.append(w)
    values.append(v)
knapsack(W,N,weights,values,matrix)
stdout.write(str(matrix[W][N]))

Submission status: Time Limit Exceeded

Solution code:
def knapsack(C,n,wei,val,mat):
    if(C==0 or n==0):
        return 0
    else:
        if(C>=wei[n-1]):
            a=mat[C-wei[n-1]][n-1]
            b=mat[C][n-1]
            if(a==-1):
                a=knapsack(C-wei[n-1],n-1,wei,val,mat)
                mat[C-wei[n-1]][n-1]=a
            if(b==-1):
                b=knapsack(C,n-1,wei,val,mat)
                mat[C][n-1]=b
            mat[C][n]=max(a+val[n-1],b)
            return (max(a+val[n-1],b))
        else:
            alp=matrix[C][n-1]
            if(alp==-1):
                alp=knapsack(C,n-1,wei,val,mat)
                mat[C][n-1]=alp
                mat[C][n]=alp
            return (alp)
N,W=map(int,input().split())
matrix=[[-1 for i in range(0,N+1)]for j in range(0,W+1)]
for i in range(0,len(matrix)):
    matrix[i][0]=0
for i in range(0,len(matrix[0])):
    matrix[0][i]=0
weights=[]
values=[]
for i in range(0,N):
    w,v=map(int,input().split())
    weights.append(w)
    values.append(v)
knapsack(W,N,weights,values,matrix)
print(matrix[W][N])

Submission status: Time Limit Exceeded

Solution code:
def knapsack(C,n,wei,val):
    if(C==0 or n==0):
        return 0
    else:
        if(C>=wei[n-1]):
            return (max(knapsack(C-wei[n-1],n-1,wei,val)+val[n-1],knapsack(C,n-1,wei,val)))
        else:
            return (knapsack(C,n-1,wei,val))
N,W=map(int,input().split())
weights=[]
values=[]
for i in range(0,N):
    w,v=map(int,input().split())
    weights.append(w)
    values.append(v)
print(knapsack(W,N,weights,values))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[0] * (W+1) for i in range(N+1)]

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

    print(dp[N][W])

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]" 
    v = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# atcoder https://atcoder.jp/contests/dp/tasks/dp_d
def main():
    N, W = map(int, input().split())
    w, v = [], []
    for _ in range(N):
        wi, vi = map(int, input().split())
        w.append(wi)
        v.append(vi)


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

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

    print(dp[N][W])

main()

Submission status: Time Limit Exceeded

Solution code:
# atcoder https://atcoder.jp/contests/dp/tasks/dp_d

N, W = map(int, input().split())
w, v = [], []
for _ in range(N):
    wi, vi = map(int, input().split())
    w.append(wi)
    v.append(vi)


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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())

weight_value = [0] * n
for i in range(n):
  weight_value[i] = [int(_) for _ in input().split()]
  
dp = [[0] * (w+1) for i in range(n+1)]

for i in range(n):
  for w_upper in range(w+1):
    if w_upper - weight_value[i][0] >= 0:
      dp[i+1][w_upper] = max(dp[i][w_upper - weight_value[i][0]] + weight_value[i][1], dp[i][w_upper])
    else:
      dp[i+1][w_upper] = dp[i][w_upper]
print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
def run():
  N, W = map(int, input().split())
  wv_li = [[0, 0]]+[list(map(int, input().split())) for n in range(N)]
  dp = [[0]*(N+1) for w in range(W+1)]
  #print(wv_li)
  #print(dp)
  for w in range(1, W+1):
    for n in range(1, N+1):
      wn, vn = wv_li[n]
      if w < wn:
        dp[w][n] = dp[w][n-1]
      else:
        dp[w][n] = max(dp[w][n-1], dp[w-wn][n-1]+vn)
  print(dp[W][N])
      
  
if __name__ == '__main__':
  run()

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())

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

# dp[i][j]: 荷物iまでにおける重さj以下の最大価値
dp = [[0]*(W+1) for i in range(N+1)]

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

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

Submission status: Time Limit Exceeded

Solution code:

num, weight_limit = map(int, input().split())
wv_list = [list(map(int, input().split())) for _ in range(num)]

# dpの初期化
dp = [[0 for _ in range(num + 1)] for _ in range(weight_limit + 1)]

for w in range(1, weight_limit + 1):
    for n in range(1, num + 1):
        weight = wv_list[n-1][0]
        value = wv_list[n-1][1]

        if weight <= w:
            dp[w][n] = max(value + dp[w - weight][n-1], dp[w][n-1])

        else:
            dp[w][n] = dp[w][n-1]

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

Submission status: Time Limit Exceeded

Solution code:
# 入力
num, weight_limit = map(int, input().split())
wv_list = [list(map(int, input().split())) for _ in range(num)]

dp = []

for w in range(0, weight_limit + 1):
    dp.append([])
    for n in range(0, num + 1):
        weight = wv_list[n-1][0]
        value = wv_list[n-1][1]

        if w == 0 or n == 0:
            dp[w].append(0)

        elif weight <= w and value + dp[w - weight][n-1] > dp[w][n-1]:
            dp[w].append(value + dp[w - weight][n-1])

        else:
            dp[w].append(dp[w][n-1])

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

Submission status: Time Limit Exceeded

Solution code:
# 入力
num, weight_limit = map(int, input().split())
wv_list = [list(map(int, input().split())) for _ in range(num)]

# dpの初期化
dp = [[0 for _ in range(num + 1)] for _ in range(weight_limit + 1)]

for w in range(1, weight_limit + 1):
    for n in range(1, num + 1):
        weight = wv_list[n-1][0]
        value = wv_list[n-1][1]

        if weight <= w and value + dp[w - weight][n-1] > dp[w][n-1]:
            dp[w][n] = value + dp[w - weight][n-1]

        else:
            dp[w][n] = dp[w][n-1]

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, W =  list(map(int, input().split()))

    dp = [-1] * (W + 1)
    dp[0] = 0

    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            pre_v = dp[i]
            if pre_v == -1: continue
            dp[i + w] = max(dp[i + w], pre_v + v)

    print(max(dp))

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, W =  list(map(int, input().split()))

    dp = [-1] * (W + 1)
    dp[0] = 0

    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            if dp[i] == -1: continue
            dp[i + w] = max(dp[i + w], dp[i] + v)

    print(max(dp))

main()

Submission status: Time Limit Exceeded

Solution code:
N, W =  list(map(int, input().split()))

dp = [-1] * (W + 1)
dp[0] = 0

for _ in range(N):
    w, v = map(int, input().split())
    for i in range(W - w, -1, -1):
        if dp[i] == -1: continue
        dp[i + w] = max(dp[i + w], dp[i] + v)

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
N, W =  list(map(int, input().split()))

dp = [0] * (W + 1)

for _ in range(N):
    w, v = map(int, input().split())
    for i in range(W - w, -1, -1):
        dp[i + w] = max(dp[i + w], dp[i] + v)

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
N, W =  list(map(int, input().split()))
w_list = []
v_list = []
dp = []
for _ in range(N):
    w, v = list(map(int, input().split()))
    w_list.append(w)
    v_list.append(v)
    dp.append({})

dp.append({})

for i in range(N + 1):
    for w in range(0, W + 1):
        dp[i][w] = 0


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

print(max(max(x.values()) for x in dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,w=map(int,input().split())
dp=[[0]*(w+1) for _ in range(n)]
l=[0]*n
for i in range(n):
    l[i]=list(map(int,input().split()))
#print(l)
for i in range(w+1):
    if i>=l[0][0]:
        dp[0][i]=l[0][1]
for i in range(w+1):
    for j in range(n-1):
        if i<l[j+1][0]:
            dp[j+1][i]=dp[j][i]
        else:
            dp[j+1][i]=max(dp[j][i-l[j+1][0]]+l[j+1][1],dp[j][i])


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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def solve(n, W, w, v):
    dp = np.zeros((n+1, W+1), dtype=int)
    for i in range(n-1, -1, -1):
        for j in range(W+1):
            nw = j + w[i]
            if nw <= W:
                dp[i, j] = max(
                    dp[i+1, j],
                    dp[i+1, nw] + v[i]
                )
            else:
                dp[i, j] = dp[i+1, j]
    return np.max(dp[0])

n, W = map(int, input().split())
w = np.zeros(n, dtype=int)
v = np.zeros(n, dtype=int)
for i in range(n):
    w[i], v[i] = map(int, input().split())
print(solve(n, W, w, v))

Submission status: Time Limit Exceeded

Solution code:
[print(f(f,W)[m]) 
  for I in [lambda:map(int, input().split())]
  for n,m in[I()]
  for W in[[I()for i in range(n)]]
for f in [lambda f,W:
        (lambda A,w,v:
          A[:w]+[max(A[i],A[i-w]+v)for i in range(w,m+1)]
        )(f(f,W[1:]),*W[0])
        if W else[0]*(m+1)]]

Submission status: Time Limit Exceeded

Solution code:
def f(n, m, WV):
  def shift(Arr, w, v):
    return [max(Arr[i], Arr[i - w] + v) if i >= w else Arr[i] for i in range(M + 1)]
  def red(WV):
    return [0] * (M+1) if not WV else shift(red(WV[1:]), *WV[0])
  return red(WV)
N, M = map(int, input().split())
print(f(N, M, [map(int, input().split()) for _ in range(N)])[M])

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
dp=[[0 for _ in range(w+1)] for _ in range(n+1)]
for i in range(n):
	a,b=map(int,input().split())
	for j in range(w):
		if j+1-a>=0:
			dp[i+1][j+1]=max(dp[i][j+1],dp[i][j+1-a]+b)
		else:
			dp[i+1][j+1]=dp[i][j+1]
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,copy
import numpy as np
sys.setrecursionlimit(10**8)
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,W = inpl()

dp = np.zeros((N+1,W+1),dtype=np.int64)

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

print(np.max(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,copy
import numpy as np
sys.setrecursionlimit(10**8)
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,W = inpl()

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

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

print(max(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,copy
sys.setrecursionlimit(10**8)
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,W = inpl()

wvlist = list()
for _ in range(N):
    wvlist.append(inpl())

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

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

print(max(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,copy
sys.setrecursionlimit(10**8)
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def sack (num,weight,value):
    if weight <= W:
        dp[num][weight] = max(dp[num][weight],value)
        if num < N:
            sack(num + 1, weight, value)
            sack(num+1,weight+wvlist[num][0],value+wvlist[num][1])

N,W = inpl()

wvlist = list()
for _ in range(N):
    wvlist.append(inpl())

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

j=0
k=0
sack(1,0,0)
sack(1,wvlist[0][0],wvlist[0][1])

print(max(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout

def knapsack(n: int, W: int, wt: list, val: list) -> int:
	dp = [0 for _ in range(W+1)]

	dp[0] = 0
	for i in range(n):
		for j in range(W, wt[i]-1, -1):
			dp[j] = max(dp[j], dp[j-wt[i]] + val[i])

	return dp[W]

def main():
	n, W = list(map(int, stdin.readline().strip().split()))

	wt = []
	val = []

	for _ in range(n):
		w, v = list(map(int, stdin.readline().strip().split()))

		wt.append(w)
		val.append(v)

	stdout.write(str(knapsack(n, W, wt, val)))


if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
n, limit = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
#print(L)
dp = [{} for i in range(n+1)]

for i in range(n):
    Lw, Lv =L[i][0], L[i][1] #①i番目の価値を重さテーブルに代入
    dp[i+1][Lw] = Lv 
    for w, v in dp[i].items():
        dp[i+1][w] = max(dp[i+1].get(w, 0), v) #② 一つ上の行の価値と比べて大きい方を代入
        if w + Lw <=limit:
            dp[i+1][w+Lw] = max(dp[i].get(w+ Lw, 0), Lv + v) #③一つ上の行の価値をループで1つづつ取り出し、i番目の価値と足し合わせる
        
print(max(dp[-1].values()))

Submission status: Time Limit Exceeded

Solution code:
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

N,W = MAP()
weight=[]
value=[]
for i in range(N):
    w,v = MAP()
    weight.append(w)
    value.append(v)

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

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int, input().split())

wv = [tuple(map(int, input().split())) for _ in range(N)]

dp = [[0 for _ in range(W+1)] for _ in range(N)]
#dp[i][j]：i番目の品物まで選べる時、重さjまで運べる時の最大価値

for i in range(N):
    for j in range(W+1):
        if j >= wv[i][0]:
            # 前者はi番目の品を選ばないとき、後者は選ぶとき
            dp[i][j] = max(dp[i-1][j], dp[i-1][j - wv[i][0]] + wv[i][1])
        else:
            dp[i][j] = dp[i-1][j]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,w=map(int,input().split())
    W=[0]*(n+1); V=[0]*(n+1)
    for i in range(1,n+1):
        a,b=map(int,input().split())
        W[i]=a; V[i]=b
    # dp[i][c] iまでの品物で、重さがc以下
    dp=[[-1]*(w+1) for _ in range(n+1)]
    # メモ化再帰
    def solve(i,c):
        if(dp[i][c]!=-1): return dp[i][c]
        if(i==0):
            dp[i][c]=0
            return dp[i][c];
        if(c-W[i]>=0):
            dp[i][c]=max(solve(i-1,c-W[i])+V[i],solve(i-1,c))
            return dp[i][c]
        else:
            dp[i][c]=solve(i-1,c)
            return dp[i][c]
    print(solve(n,w))
resolve()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#DP D
from functools import lru_cache
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
@lru_cache(maxsize=1000)
def dp(i, j):
    w,v=wv[i]
    if i==-1:
        return 0
    elif j<w:
        return dp(i-1, j)
    else:
        return max(dp(i-1, j),dp(i-1, j-w)+v)
print(dp(n-1,W))

Submission status: Time Limit Exceeded

Solution code:
#DP D
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
def dp(i, j):
    w,v=wv[i]
    if i==-1:
        return 0
    elif j<w:
        return dp(i-1, j)
    else:
        return max(dp(i-1, j),dp(i-1, j-w)+v)
print(dp(n-1,W))

Submission status: Time Limit Exceeded

Solution code:
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] * (W + 1) for _ in range(N + 1)]
# dp[i][j](j=0,1,...,W)の値が求まっている状態で、dp[i+1][j]を更新することを考える
for i in range(N):
    for j in range(W + 1):
		# 品物(w[i],v[i])を選ぶとき、j-w[i]>=0に限って、価値v[i]が加算される
        if j - w[i] >= 0:
            dp[i + 1][j] = dp[i][j - w[i]] + v[i]
		# 品物(w[i],v[i])を選ばないとき、何も加算しない
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
#print(dp)

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [ [0 for _ in range(W+1)] for _ in range(N) ]

    dp[0][w[0]] = v[0]

    for i in range(1,N):
        for j in range(0,W+1):
            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(dp[-1][-1])
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
n,w = map(int,input().split())
value = []
weight = []
dp = [[0]*(w+1) for _ in range(n+1)]
for i in range(n):
    x,y = map(int,input().split())
    value += [y]
    weight += [x]
for i in range(n):
    for j in range(w+1):
        if j - weight[i] >= 0:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j-weight[i]]+value[i])
        dp[i+1][j] = max(dp[i+1][j],dp[i][j])
print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
I = [list(map(int, input().split())) for i in range(N)]
dp = [0] * (W+1)

for i in range(N):
  wi, vi = I[i]
  for w in range(W, wi-1, -1):
    dp[w] = max(dp[w], dp[w-wi]+vi)

print(dp[W])

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
dp = [0 for i in range(W+1)]

for i in range(N):
  wi, vi = map(int, input().split())
  for w in range(W, wi-1, -1):
    if dp[w-wi]+vi <= dp[w]:
      continue
    dp[w] = dp[w-wi]+vi

print(dp[W])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N, W = map(int, input().split())
dp = [0 for i in range(W+1)]

for i in range(N):
  wi, vi = map(int, input().split())
  for w in range(W, wi-1, -1):
    dp[w] = max(dp[w], dp[w-wi]+vi)

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
dp = [0 for i in range(W+1)]

for i in range(N):
  wi, vi = map(int, input().split())
  for w in range(W, wi-1, -1):
    dp[w] = max(dp[w], dp[w-wi]+vi)

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
dp = [0]*(W+1)

for i in range(N):
  wi, vi = map(int, input().split())
  for w in range(W, wi-1, -1):
    dp[w] = max(dp[w], dp[w-wi]+vi)

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,W = map(int, input().split())
dp = np.zeros((N+1,W+1), dtype=np.int64)
for i in range(N):
    w,v = map(int, input().split())
    for j in range(W):
        if j+w <= W:
            dp[i+1][j+w] = max(dp[i+1][j+w], dp[i][j] + v) # 取る場合
        dp[i+1][j] = max(dp[i+1][j], dp[i][j]) # 取らない場合
print(max(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
#wv=[[int(i) for i in input().split()] for j in range(n)]
dp=[0]*(w+1)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
n, limit= map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

#各重さとi番目の荷物を入れ終わった状態のテーブルをつくる
dp = [[0 for _ in range(limit+1)] for _ in range(n)]

#初期状態
for w in range(limit+1):
    if L[0][0] <=w:
        dp[0][w] = L[0][1]

for i in range(n):
    for w in range(limit+1):
        if w < L[i][0]: #場合分け 荷物よりも容量が小さいとき
            dp[i][w] = dp[i-1][w]
        else:           # 荷物よりも容量が大きいとき
            dp[i][w] = max(L[i][1] + dp[i-1][w-L[i][0]], dp[i-1][w]) # w = (w - L[i][0]) + L[i][0]

print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
import random
import copy
from collections import Counter

def get_population():
    population = []
    for i in range(individual_length):
        population.append([random.randint(0,1) for j in range(gene_length)])
    return population

def evaluate(pop):
    pop.sort(reverse=True)
    return pop

def two_point_crossover(parent1, parent2):
    r = [random.randint(0,1) for _ in range(gene_length)]
    child = [parent1[i] if r[i] else parent2[i] for i in range(gene_length)]
    return child

def mutate(parent):
    r = random.randint(0, gene_length-1)
    child = copy.deepcopy(parent)
    child[r] = 1 if child[r] == 0 else 0
    return child

def fitness(pop):
    value = 0
    weight = 0
    for i in range(N):
        if pop[i]:
            value += L[i][1]
            weight += L[i][0]
    if weight <= W:
        return value
    else:
        return 0

N,W = [int(zz) for zz in input().split()]
L = [[0,0] for _ in range(N)]

ans = []
for i in range(N):
    p,q = [int(zz) for zz in input().split()]
    L[i][0] = p
    L[i][1] = q

gene_length = N
individual_length = 100
generation = 150
mutate_rate = 0.1
elite_rate = 0.2

for _ in range(3):
    pop = evaluate([(fitness(p), p) for p in get_population()])

    for i_episode in range(generation):

        eva = evaluate(pop)
        elites = eva[:int(len(pop)*elite_rate)]

        pop = elites
        while len(pop) < individual_length:
            if random.random() < mutate_rate:
                m = random.randint(0, len(elites)-1)
                child = mutate(elites[m][1])
            else:
                m1 = random.randint(0, len(elites)-1)
                m2 = random.randint(0, len(elites)-1)
                child = two_point_crossover(elites[m1][1], elites[m2][1])
            pop.append((fitness(child), child))

    eva = evaluate(pop)
    ans.append(pop[0][0])

counter = Counter(ans)

print(counter.most_common()[0][0])

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
dp = [[0]*(W+1) for i in range(N+1)]

for i in range(1, N+1):
  wi, vi = map(int, input().split())
  for w in range(1, W+1):
    if w - wi < 0:
      dp[i][w] = dp[i-1][w]
    else:
      dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi]+vi)

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
class Item:
  def __init__(self, w, v):
    self.w = w
    self.v = v

N, W = map(int, input().split())
items = [Item(0, 0)] + [Item(*map(int, input().split())) for i in range(N)]
dp = [[0]*(W+1) for i in range(N+1)]

for i in range(1, N+1):
  item = items[i]
  for w in range(1, W+1):
    if w - item.w < 0:
      dp[i][w] = dp[i-1][w]
    else:
      dp[i][w] = max(dp[i-1][w], dp[i-1][w-item.w]+item.v)

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
N, W = list(map(int, input().split()))
w = []
v = []
for i in range(N):
    wi, vi = list(map(int, input().split()))
    w.append(wi)
    v.append(vi)

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

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

Submission status: Time Limit Exceeded

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

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

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

print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [0] * (W + 1)
    for i in range(N):
        for j in range(W, -1, -1):
            if j + w[i] <= W:
                dp[j + w[i]] = max(dp[j + w[i]], dp[j] + v[i])
    ret = max(dp)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]" 
    v = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
N, K = [int(i) for i in input().split()]
wvs = [(int(w), int(v)) for w,v in [input().split() for _ in range(N)]]
dp = [0]*(K)
for i, wv in enumerate(wvs):
  w,v = wv
  tmp_dp = copy.deepcopy(dp)
  for j in range(i,K):
    if (j+w) <= K:
      tmp_dp[j+w-1] = max(dp[j+w-1], dp[j-1] + v)
  dp = tmp_dp
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
# DP
def main():
    from builtins import int, map, max, min, range
    from sys import stdin
    readline = stdin.readline

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

    dp = [-1] * (W + 1)
    dp[0] = 0
    max_w = 0
    for _ in range(N):
        w, v = map(int, readline().split())
        for j in range(min(max_w, W - w), -1, -1):
            dpj = dp[j]
            if dpj != -1:
                jw = j + w
                if dpj + v > dp[jw]:
                    dp[jw] = dpj + v
                if jw > max_w:
                    max_w = jw
    print(max(dp))


main()