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:
import numpy as np

n,k = [int(i) for i in input().split()]
w = []
v = []
for _ in range(n):
    a,b = [int(i) for i in input().split()]
    w.append(a)
    v.append(b)

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

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

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
w = [0 for _ in range(N)]
v = [0 for _ in range(N)]
for i in range(N):
    w[i], v[i] = map(int, input().split())

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

for i in range(N):
    for sum_w in range(1, 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])

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
L = list(list(map(int,input().split())) for i in range(N))

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

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

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

Submission status: Time Limit Exceeded

Solution code:


n, w = map(int, raw_input().split())
items = []
for _ in range(n):
    wi, vi = map(int, raw_input().split())
    items.append((wi, vi))

dp = [[0] * (w + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    wi, vi = items[i - 1]
    for j in range(1, w + 1):
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        if j >= wi:
            dp[i][j] = max(dp[i][j], vi + dp[i - 1][j - wi])
print(dp[n][w])

Submission status: Time Limit Exceeded

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

weight = [0 for i in range(N)]
value = [0 for j in range(N)]
for i in range(N):
    weight[i],value[i] = map(int,input().split())

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 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]

print(DP[N][W])

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
ws, vs = [0]*N, [0]*N

for i in range(N):
    ws[i], vs[i] = map(int, input().split())

import numpy as np
mem = np.ndarray((N, W+1), dtype=np.int64)
mem[:] = -1

def get(n, w):
    if mem[n][w] != -1:
        return mem[n][w]
    if n == 0:
        if w >= ws[0]:
            ans = vs[0]
        else:
            ans = 0
    elif w < ws[n]:
        ans = get(n - 1, w)
    else:
        ans = max(get(n - 1, w), get(n - 1, w-ws[n])+vs[n])
    mem[n][w] = ans
    return ans

print(get(N-1, W))

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
ws, vs = [0]*N, [0]*N

for i in range(N):
    ws[i], vs[i] = map(int, input().split())

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

def get(n, w):
    if mem[n][w] is not None:
        return mem[n][w]
    if n == 0:
        if w >= ws[0]:
            ans = vs[0]
        else:
            ans = 0
    elif w < ws[n]:
        ans = get(n - 1, w)
    else:
        ans = max(get(n - 1, w), get(n - 1, w-ws[n])+vs[n])
    mem[n][w] = ans
    return ans

print(get(N-1, W))

Submission status: Time Limit Exceeded

Solution code:
n,max_w = map(int,input().split())
w=[]
v=[]

for i in range(n):
  tmp_w,tmp_v = map(int,input().split()) 
  w.append(tmp_w)
  v.append(tmp_v)

dp =[[-1]*(max_w+1) for i in range(n+1)]
  
#i番目以降の品物から、重さの総和がj以下となるように選ぶ
def knapsac(i,j):
  if dp[i][j]>=0:
    return dp[i][j]
  if i == n:
    #品物は残っていない
    dp[i][j] = 0
  elif j < w[i]:
    #品物が入らない
    dp[i][j] = knapsac(i+1,j)
  else:
    #品物が入る→品物を入れる場合と入れない場合を両方試す
    dp[i][j] = max(knapsac(i+1,j),knapsac(i+1,j-w[i])+v[i])
  return dp[i][j]

print(knapsac(0,max_w))

Submission status: Time Limit Exceeded

Solution code:
n,max_w = map(int,input().split())
w=[]
v=[]

for i in range(n):
  tmp_w,tmp_v = map(int,input().split()) 
  w.append(tmp_w)
  v.append(tmp_v)
  
dp=[[0]*(max_w+1) for i in range(n)]

#dp[i番目の品まで入れられる][重さがj以下]
for j in range(max_w+1):
  if j < w[0]:
    dp[0][j]=0
  else:
    dp[0][j]=v[0]
    
for i in range(0,n-1):
  for j in range(max_w+1):
    if j < w[i+1]:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j],dp[i][j-w[i+1]]+v[i+1])
print(dp[n-1][max_w])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from functools import lru_cache
N, W = map(int, input().split())
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]


@lru_cache(None)
def dp(w: 'int', n: 'int') -> 'int':
    if w == 0 or n == 0:
        return 0
    if s[n - 1][0] > w:
        return dp(w, n - 1)
    else:
        return max(dp(w, n - 1), dp(w - s[n - 1][0], n - 1) + s[n - 1][1])


print(dp(W, N))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,W = IL()
w = []
v = []

for i in range(N):
  a,b = IL()
  w.append(a)
  v.append(b)

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

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

Submission status: Time Limit Exceeded

Solution code:
n,k=(int(i) for i in input().split())

e = [[int(i) for i in input().split()] for j in range(n)]
#print(e)

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

for j in range(k+1):
    if j >= e[0][0]:
      dp[0][j]=e[0][1]

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

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

Submission status: Time Limit Exceeded

Solution code:
n,k=(int(i) for i in input().split())

e = [[int(i) for i in input().split()] for j in range(n)]
#print(e)

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

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

print(max(dp[0]))

Submission status: Time Limit Exceeded

Solution code:
n,k=(int(i) for i in input().split())

e = [[int(i) for i in input().split()] for j in range(n)]
#print(e)

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

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

print(dp[0][-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import namedtuple

item = namedtuple('itm', ('w', 'v'))
n, W = map(int, input().split())
items = []
dic = dict()


def rec_dp(i: int, w: int) -> int:
    if (i, w) in dic:
        return dic[(i, w)]

    result = 0
    if i == n:
        pass
    elif w - items[i].w < 0:
        result = rec_dp(i + 1, w)
    else:
        result = max(
            rec_dp(i + 1, w),
            rec_dp(i + 1, w - items[i].w) + items[i].v
        )
    dic[(i, w)] = result
    return result


def main() -> None:
    global items
    for i in range(n):
        a, b = map(int, input().split())
        items += [item(a, b)]

    print(rec_dp(0, W))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import namedtuple


def next_str() -> str:
    result = ""
    while True:
        tmp = sys.stdin.read(1)
        if tmp.strip() != "":
            result += tmp
        elif tmp != "\r":
            break
    return result


def next_int() -> int:
    return int(next_str())


item = namedtuple('itm', ('w', 'v'))
n, W = map(int, input().split())
items = [item(next_int(), next_int()) for i in range(n)]
dic = dict()


def rec_dp(i: int, w: int) -> int:
    if (i, w) in dic:
        return dic[(i, w)]

    result = 0
    if i == n:
        pass
    elif w - items[i].w < 0:
        result = rec_dp(i + 1, w)
    else:
        result = max(
            rec_dp(i + 1, w),
            rec_dp(i + 1, w - items[i].w) + items[i].v
        )
    dic[(i, w)] = result
    return result


def main() -> None:
    print(rec_dp(0, W))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

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

print DP[W]

Submission status: Time Limit Exceeded

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

for i in range(n):
    a,b = map(int,input().split())
    w.append(a)
    v.append(b)
for i in range(n):
    for sum_w in range(k+1):
        if sum_w - w[i] >=0:
            dp[i+1][sum_w]=max(dp[i][sum_w],dp[i][sum_w - w[i]] + v[i])
        else:
            dp[i+1][sum_w]=dp[i][sum_w]

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

Submission status: Time Limit Exceeded

Solution code:
n,k=(int(i) for i in input().split())

w0=[0 for i in range(n+1)]
v0=[0 for i in range(n+1)]
for i in range(1,n+1):
  (w0[i],v0[i]) = (int(i) for i in input().split())
  
w=[0]
v=[0]
for j in range(1,n+1):
    for i in range(len(w)):
        if w[i]+w0[j] <= k:
            w=w+[w[i]+w0[j]]
            v=v+[v[i]+v0[j]]  

#print(n,k,w0,v0)
print(max(v))

Submission status: Time Limit Exceeded

Solution code:
n,k=(int(i) for i in input().split())

w0=[0 for i in range(n+1)]
v0=[0 for i in range(n+1)]
for i in range(1,n+1):
  (w0[i],v0[i]) = (int(i) for i in input().split())
  
w=[0]
v=[0]
for j in range(1,n+1):
    for i in range(len(w)):
        if w[i]+w0[j] <= k:
            w.append(w[i]+w0[j])
            v.append(v[i]+v0[j])  

#print(n,k,w0,v0)
print(max(v))

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
L = list(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 item in range(N) :
    w_i,v_i = L[item]
    for weight in range(W+1) :
        if weight - w_i >= 0 :
            dp[item+1][weight] = max(dp[item][weight], dp[item][weight-w_i] + v_i)
        else :
            dp[item+1][weight] = dp[item][weight]

ans = dp[N][W]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
n1=n
n=m
m=n1 
mat=[[0]*(n+1)]
for i in range(m):
      mat.append([0])
for i in range(m):
      s,w=map(int,input().split())
      for j in range(n):
            if s>j+1:
                  mat[i+1].append(mat[i][j+1])
            else:
                  mat[i+1].append(max(mat[i][j+1],w+mat[i][j+1-s]))
print(mat[m][n])

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
import numpy as np
N,W = list(map(int, input().split()))
wlist = [tuple(map(int, input().split())) for _ in range(N)]


# until ..w, v 
l = [(-1, 0, 0)]

ans = 0
while l:
    i_last, w, v = l.pop()
    if w > W:
        continue

    ans = max(ans, v)

    if i_last >= N-1:
        continue

    l.append( (i_last+1, w+wlist[i_last+1][0], 
                         v+wlist[i_last+1][1] ) )
    l.append( (i_last+1, w, 
                         v ) )
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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]*(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])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, W = MAP()
wN, vN = [0]*N, [0]*N
for i in range(N):
    wN[i], vN[i] = MAP()

# dp[何個目までから選ぶか][これまでに選んだ荷物の重さ] = これまでに選んだ荷物の価値
dp = [[0] * (W+1) for i in range(N+1)]

for i in range(N):
    for j in range(W+1):
        # 真下には常に送る
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if j + wN[i] <= W:
            # 重さが制限内なら右下にも送る
            dp[i+1][j+wN[i]] = max(dp[i+1][j+wN[i]], dp[i][j] + vN[i])
print(dp[N][W])

Submission status: Time Limit Exceeded

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

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=[[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 j>=w[i]:
            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[0][W])

Submission status: Time Limit Exceeded

Solution code:
import sys

n, we = map(int, input().split())

cf=[(0, 0)]*n

cf = sorted(tuple( int(x) for x in sys.stdin.readline().split()) for _ in range(n))

dp=[0]*(we+1)

best=0

for w,c in cf:
    for j in reversed(range(w, we+1)):
        if dp[j]<dp[j-w]+ c : dp[j]=dp[j-w]+ c
    # print(dp)
    best=max(best, dp[we])


print(best)

Submission status: Time Limit Exceeded

Solution code:
import sys

n, we = map(int, input().split())

cf=[(0, 0)]*n

for i in range(n):
    cf[i] = tuple( map(int, sys.stdin.readline().split()) )

dp=[0]*(we+1)

best=0

for w,c in cf:
    for j in reversed(range(w, we+1)):
        if dp[j]<dp[j-w]+ c : dp[j]=dp[j-w]+ c
    # print(dp)
    best=max(best, dp[we])


print(best)

# for i in range(1, n+1): print( dp[i], '\n' )

Submission status: Time Limit Exceeded

Solution code:
import sys

n, we = map(int, input().split())

cf=[(0, 0)]*(n+1)

for i in range(1, n+1):
    cf[i] = tuple( map(int, sys.stdin.readline().split()) )

dp=[0]*(we+1)

best=0

for i in range(1, n+1):
    for j in reversed(range(cf[i][0], we+1)):
        dp[j]=max( dp[j], dp[j-cf[i][0]]+ cf[i][1] )
        
    best=max(best, dp[we])


print(best)

# for i in range(1, n+1): print( dp[i], '\n' )

Submission status: Time Limit Exceeded

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

cf=[(0, 0)]*(n+1)

for i in range(1, n+1):
    cf[i] = tuple( map(int, input().split()) )

dp=[0]*(we+1)

best=0

for i in range(1, n+1):
    for j in reversed(range(cf[i][0], we+1)):
        dp[j]=max( dp[j], dp[j-cf[i][0]]+ cf[i][1] )
        
    best=max(best, dp[we])


print(best)

# for i in range(1, n+1): print( dp[i], '\n' )

Submission status: Time Limit Exceeded

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

cf=[(0, 0)]*(n+1)

for i in range(1, n+1):
    cf[i] = tuple( map(int, input().split()) )

dp=[[0]*(we+1) for _ in range(n+1)]

best=0

for i in range(1, n+1):
    for j in range(cf[i][0]):
        dp[i][j]=dp[i-1][j]
    for j in range(cf[i][0], we+1):
        dp[i][j]=max( dp[i][j-1], dp[i-1][j], dp[i-1][j-cf[i][0]]+ cf[i][1] )
    best=max(best, dp[i][we])


print(best)

# for i in range(1, n+1): print( dp[i], '\n' )

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

def parse(inp):
    N,W=map(int,next(inp).split())
    
    obj=np.empty([0,2],dtype=np.int64)
    for i in range(N):
        obj=np.append(obj,np.array([next(inp).split()],dtype=np.int64),axis=0)
    
    return N,W,obj
  
def main(inp):
    N=inp[0]
    W=inp[1]
    obj=inp[2]
    weight=obj.transpose()[0]
    value=obj.transpose()[1]
    
    
    dp=np.zeros([N,W+1],dtype=np.int64)
    for i in range(weight[0],W+1):
        dp[0][i]=value[0]
    
    for i in range(1,N):
        for sum_w in range(W+1):
            if(sum_w-weight[i]>=0):
                dp[i][sum_w]=max(dp[i][sum_w],dp[i-1][sum_w-weight[i]]+value[i]) 
            dp[i][sum_w]=max(dp[i-1][sum_w],dp[i][sum_w])
    
    return dp[N-1,W]
  
print(main(parse(sys.stdin)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, W = map(int, input().split())
weights = []
values = []
for i in range(N):
    w,v = map(int, input().split())
    weights.append(w)
    values.append(v)

dp = np.zeros((110,10**5+10), dtype='int64')

for i in range(N):
    for sumw in range(W+1):
        if sumw >= weights[i]:
            dp[i+1][sumw] = max(dp[i][sumw],dp[i][sumw-weights[i]]+values[i])
        dp[i+1][sumw] = max(dp[i][sumw],dp[i+1][sumw])

print(dp[N][W])

Submission status: Time Limit Exceeded

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

items = [[int(x) for x in input().split()] for j in range(n)]


def rec_dp(i: int, w: int) -> int:
    if dp[i][w] != -1:
        return dp[i][w]

    if i == n:
        result = 0
    else:
        item_w = items[i][0]
        item_v = items[i][1]
        if w < item_w:
            result = rec_dp(i + 1, w)
        else:
            result = max(
                rec_dp(i + 1, w),
                rec_dp(i + 1, w - item_w) + item_v
            )

    dp[i][w] = result
    return result


def main() -> None:
    global n, W
    print(rec_dp(0, W))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


n, W = map(int, input().split())
dp = [[-1 for w in range(W + 1)] for i in range(n + 1)]

items = [[int(x) for x in input().split()] for j in range(n)]


def rec_dp(i: int, w: int) -> int:
    if dp[i][w] != -1:
        return dp[i][w]

    if i == n:
        result = 0
    else:
        item = Item(items[i][0], items[i][1])
        if w < item.w:
            result = rec_dp(i + 1, w)
        else:
            result = max(
                rec_dp(i + 1, w),
                rec_dp(i + 1, w - item.w) + item.v
            )

    dp[i][w] = result
    return result


def main() -> None:
    global n, W
    print(rec_dp(0, W))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
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[i, w]:  i-r achaag oroltsuulaad , 
#            w hurtelh achaatai max value
# dp[i]: w1 ,,,,,wN

dp = [ {} for i in range(N)]

def DP(i, Wi):
  if Wi in dp[i]:
    return dp[i][Wi]

  if i == 0:
    if Wi >= w[i]:
      dp[i][Wi] = v[i]
    else:
      dp[i][Wi] = 0
    return dp[i][Wi]
  
  vmax = DP(i - 1, Wi)
  if Wi >= w[i]:
    vmax = max(vmax, v[i] + DP(i - 1, Wi - w[i]))
  dp[i][Wi] = vmax
  return dp[i][Wi]

print(DP(N - 1, W))

Submission status: Time Limit Exceeded

Solution code:
INF = float('inf')

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

dp = {0: 0}
for wi, vi in items:
    for w, v in list(dp.items()):
        if w+wi <= capW:
            dp[w+wi] = max(dp.get(w+wi, 0), v+vi)

print(max(dp.values()))

Submission status: Time Limit Exceeded

Solution code:
INF = float('inf')

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

dp = [-INF] * (capW+1)
dp[0] = 0
for wi, vi in items:
    for w in reversed(range(capW+1)):
        if dp[w] == -INF: continue
        if w+wi <= capW:
            dp[w+wi] = max(dp[w+wi], dp[w] + vi)

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(N)]
dp = {0: 0}
for i in range(N):
    for j in sorted(dp.keys(), reverse=True):
        w, v = wv[i][0], wv[i][1]
        nw = dp[j] + w
        nv = j + v
        if nw <= W:
            if nv in dp:
                if nw < dp[nv]:
                    dp[nv] = nw
            else:
                dp[nv] = nw


print(max(dp.keys()))

Submission status: Time Limit Exceeded

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

dp = [[0 for _ in range(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] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - WV[i][0]] + WV[i][1])


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

Submission status: Time Limit Exceeded

Solution code:
def main():
  N, W = list(map(int, input().split()))
  Data = []
  for i in range(N):
    Data.append(list(map(int, input().split())))
  
  DP = [0 for i in range(W+1)]
  
  for i in range(N):
    for j in range(W - Data[i][0], -1, -1):
      k = j + Data[i][0]
      DP[k] = max(DP[j] + Data[i][1], DP[k])
  
  print(DP[-1])
  
main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,w = map(int,input().split())
wv = []
for i in range(n):
    wv.append(list(map(int,input().split())))  
ans = []
for i in range(n):
    for j in list(itertools.combinations(wv,i+1)):
        wt,v = 0,0
        for k in j:
            wt += k[0]
            v += k[1]
        if wt <= w:
            ans.append(v)
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,w = map(int,input().split())
wv = []
for i in range(n):
    wv.append(list(map(int,input().split())))  
cob = []
for i in range(n):
    cob.extend(itertools.combinations(wv,i+1))
ans = []
for i in range(len(cob)):
    wt,v = 0,0
    for j in cob[i]:
        wt += j[0]
        v += j[1]
    if wt <= w:
        ans.append(v)
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import itertools as itr

n, wmax = list(map(int, input().split()))
w = [0]*(n+1)
v = [0]*(n+1)
for i in range(1, n+1):
    wi, vi = list(map(int, input().split()))
    w[i] = wi
    v[i] = vi
    
dp = [[0]*(wmax+1) for _ in range(n+1)]

for i, wi in itr.product(range(1, n+1), range(1, wmax+1)):
    if wi-w[i] >= 0:
        dp[i][wi] = max(dp[i-1][wi], dp[i-1][wi-w[i]]+v[i])
    else:
        dp[i][wi] = dp[i-1][wi]
            
print(dp[n][wmax])

Submission status: Time Limit Exceeded

Solution code:
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()
import copy
n,wmax=IL()
dp=[0 for i in range(wmax+1)]
for i in range(1,n+1):
    w,v=IL()
    predp=copy.deepcopy(dp)
    for j in range(w,wmax+1):
        dp[j]=max(predp[j],predp[j-w]+v)
print(dp[wmax])

Submission status: Time Limit Exceeded

Solution code:
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

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

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
weight=[0]*N
value=[0]*N
for i in range(N):
    weight[i],value[i]=map(int,input().split())
dp=[[0 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]
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,W = map(int,input().split())
dp=np.zeros(W+1,dtype=int)
for i in range(N):
	w,v = map(int,input().split())

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,W = map(int,input().split())
dp=np.zeros(W+1,dtype="int64")
for i in range(N):
	w,v = map(int,input().split())

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

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):
	w,v = map(int,input().split())

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

Submission status: Time Limit Exceeded

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

for num in range(N):
	w = wv[num][0]
	v = wv[num][1]

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

Submission status: Time Limit Exceeded

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

for num in range(N):
	w,v = map(int,input().split())

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

Submission status: Time Limit Exceeded

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

for num in range(N):
	w,v = map(int,input().split())

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def inpl(): return list(map(int, input().split()))


N, W = inpl()
A = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(1, N+1):
    w, v = inpl()
    for j in range(1, W+1):
        if j - w < 0:
            A[i][j] = A[i-1][j]
        else:
            A[i][j] = max(A[i-1][j], A[i-1][j-w]+v)
print(A[N][W])

Submission status: Time Limit Exceeded

Solution code:
N, W = [int(_) for _ in input().split()]
WV = sorted([[int(_) for _ in input().split()] for _ in range(N)],
            reverse=True)
dp = {}
dp[0] = 0
for w, v in WV:
    dp_o = dp.copy()
    for k in dp_o:
        if k + w <= W:
            dp[k + w] = max(dp_o.get(k + w, 0), dp_o[k] + v)
print(max([v for k, v in dp.items()]))

Submission status: Time Limit Exceeded

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

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

ans = 0
for i in range(W+1):
    ans = max(ans,dp[i])
print(ans)

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)]
# dp[n][w] = n番目までの品物による重量w以下の価値の総和の最大値

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

Submission status: Time Limit Exceeded

Solution code:
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):
    w, v = WV[i]
    for i in range(W,-1,-1):
        if i >= w:
            dp[i] = max( dp[i], dp[i-w]+v)
        else:
            break
print( dp[-1])

Submission status: Time Limit Exceeded

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_d
#2019-01-13
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    a, b = map(int, input().split())
    w += [a]
    v += [b]

DP = [0] * (W+1)
# i 円以下で買える商品の最大価値
for i in range(N):
    for weight in range(W,-1,-1):
        if weight - w[i] < 0 :continue
        DP[weight] = max(DP[weight], DP[weight - w[i]] +v[i])
print(DP[-1])