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:
n,mw=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(n)]
dp=[[0 for _ in range(mw+1)] for _ in range(n+1)]
for i in range(n):
    weight,value=l[i]
    for j in range(mw+1):
        dp[i+1][j]=max(dp[i+1][j],dp[i][j])
        if j+weight<=mw:
            dp[i+1][j+weight]=max(dp[i][j+weight],dp[i][j]+value)
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input=sys.stdin.readline

def dp(N,W):
    ans=np.zeros(W+1,dtype=np.int)
    for _ in range(N):
        w,v=map(int,input().split())
        for i in range(W,w-1,-1):
            tmp=ans[i-w]+v
            if ans[i]<tmp:
                ans[i]=tmp
    print(ans[-1])

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

Submission status: Time Limit Exceeded

Solution code:
N,W=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):
        tmp=dp[i-w]+v
        if tmp>dp[i]:
            dp[i]=tmp
print(dp[W])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
def maxValue(MW,w,v,end):
    if end==0 or MW==0:
        return 0
    if w[end-1]>MW:
        return maxValue(MW,w,v,end-1)
    else:
        return max(v[end-1]+maxValue(MW-w[end-1],w,v,end-1),maxValue(MW,w,v,end-1))
n,k = list(map(int,input().split()))
w=[]
v=[]
for i in range(n):
  x = list(map(int,input().split()))
  w.append(x[0])
  v.append(x[1])
print(maxValue(k,w,v,n))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

N, W = map(int, input().split())
WV = []

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

@lru_cache(None)
def Knap(i, j):
  ret = 0
  if i == N:
    ret = 0
  elif j < WV[i][0]:
    ret = Knap(i+1, j)
  else:
    ret = max(Knap(i+1, j), Knap(i+1, j-WV[i][0])+WV[i][1] )
  return ret

print(Knap(0, W))

Submission status: Time Limit Exceeded

Solution code:
def knapsack(N,W,w,v):
    dp = [[0]*(W+1) for _ in range(N)]
    
    for i in range(N):
        for j in range(W+1):
            if j-w[i]>=0:
                dp[i][j] = max(dp[i-1][j],v[i]+ dp[i-1][j-w[i]])
            else:
                dp[i][j] = dp[i-1][j]
    
    return dp[N-1][W]

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

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

Submission status: Time Limit Exceeded

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

	
    
	a,b=map(int,input().split())
	
	for j in range(1,w+1):
		dp1[j]=dp[j]
		if(a<=j):
			dp1[j]=max(dp1[j],dp[j-a]+b)
	
	dp=dp1.copy()
print(dp[w])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
def knapsack(w,weight,value):
    n = len(weight)
    if(n==0):
        return 0

    if(table[n][w] != -1):
        return table[n][w]

    if(weight[0] > w):
        table[n][w] =  knapsack(w,weight[1:], value[1:])
        return table[n][w]
    table[n][w] = max(knapsack(w,weight[1:],value[1:]), value[0]+knapsack(w-weight[0],weight[1:],value[1:]) )
    return table[n][w]


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

table = [[-1 for i in range(w+1)] for j in range(n+1)]

print(knapsack(w,weight,value))

Submission status: Time Limit Exceeded

Solution code:
[N,W]=[int(x) for x in input().split()]
weight_and_value=[[0,0]]
for i in range(N):
  weight_and_value.append([int(x) for x in input().split()]) 
dp=[[0 for i in range(W+1)] for i in range(N+1)]
for i in range(1,N+1):
  for w in range(W+1):
    if weight_and_value[i][0]>w:
      dp[i][w]=dp[i-1][w]
    else:
      dp[i][w]=max(dp[i-1][w],dp[i-1][w-weight_and_value[i][0]]+weight_and_value[i][1])

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
a = [int(x) for x in input().split()]
weight = a[1]
dp = [0] * weight + [0]
for x in range(a[0]):
    b = [int(x) for x in input().split()]
    for x in range(weight, b[0] - 1, -1):
        dp[x] = max(dp[x], dp[x - b[0]] + b[1])
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
# import numpy as np
starttime = time.time()
# import numpy as np
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    # sys.setrecursionlimit(int(pow(10,6)))
    sys.stdin = open("input.txt", "r")
    # sys.stdout = open("../output.txt", "w")
except:
    pass

n,W=L()

dp=[0 for i in range(W+1)]
for i in range(n):
    w,v=L()
    for k in range(W,w-1,-1):
        dp[k]=max(dp[k],dp[k-w]+v)
print(max(dp))

endtime = time.time()
# print(f"Runtime of the program is {endtime - starttime}")

Submission status: Time Limit Exceeded

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

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

s.sort()

ans=[s[0]]

for i in range(1,n):
    for j in range(len(ans)):
        if s[i][0]+ans[j][0]<= W :
            ans.append((s[i][0]+ans[j][0],s[i][1]+ans[j][1]))

print(max(ans,key= lambda x : x[1])[1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

dp = np.zeros(W+1, np.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:
import numpy as np

N,W = map(int,input().split())
wv = np.array([list(map(int,input().split())) for _ in range(N)])
dp=np.zeros([N+1,W+1])

#　基本形
for i in range(1,N+1):
    dp[i][:wv[i-1][0]] = dp[i-1][:wv[i-1][0]]
    for j in range(wv[i-1][0],W+1):
        dp[i][j] = max(dp[i-1][j],dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
print(int(dp[-1,-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


from numba import njit
import numpy as np


N, K = ints()
W, V = read_col(N)
W = np.array(W, dtype=np.int64)
V = np.array(V, dtype=np.int64)


# @njit('(i8,i8,i8[:],i8[:])', cache=True)
def main(N, K, W, V):
    dp = np.zeros((N + 1, K + 1), dtype=np.int64)
    for i in range(N + 1):
        dp[i, 0] = 0

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


main(N, K, W, V)

Submission status: Time Limit Exceeded

Solution code:
n, W = map(int, input().split())
w = []
v = []
for i in range(n):
  w_, v_ = map(int, input().split())
  w.append(w_)
  v.append(v_)
  
  
dp = [0] * (W+1)

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

Submission status: Time Limit Exceeded

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


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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,W = map(int,input().split())
wv = np.array([list(map(int,input().split())) for _ in range(N)])
dp=np.zeros([N+1,W+1])

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

Submission status: Time Limit Exceeded

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

for i in range(1, n + 1):
    for j in range(1, w + 1):
        if j - wv[i][0] >= 0:
            dp[i][j] = max(dp[i - 1][j - wv[i][0]] + wv[i][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())
wv = []
for i in range(N):
    wv.append(list(map(int,input().split())))
    
#- dp[i][j] i番目より後ろの品物から、重さjまで許して荷物を入れた時の価値の最大
dp = [[0]*(W+1) for i in range(N+1)]

for i in range(N-1,-1,-1):#N番目以降は品物がもうないので0。→N-1からやる
    for j in range(W,-1,-1): #重いほうから見ていく
        if j<wv[i][0]:#i番目の荷物の重さがそもそも許容値よりも大きい→いれられない
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j],dp[i+1][j-wv[i][0]]+wv[i][1])#いれない or いれる　の大きいほう
#最後の出力は、0番目以降の品物(つまり、全部)から、重さWまで許したときの価値の最大
print(dp[0][W])

Submission status: Time Limit Exceeded

Solution code:
n,W=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
dp=[[0 for _ in range(W+1)] for _ in range(n+1)]
for i in range(n):
    weight,value=a[i]
    for j in range(W+1):
        dp[i+1][j]=max(dp[i][j],dp[i+1][j])
        if j+weight<=W:
            dp[i+1][j+weight]=max(dp[i][j+weight],dp[i][j]+value)
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
a=[list(map(int,input().split())) for _ 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):
        weight,value=a[i]
        dp[i+1][j]=max(dp[i][j],dp[i+1][j])
        if j+weight<=w:
            dp[i+1][j+weight]=max(dp[i][j+weight],dp[i][j]+value)
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input =sys.stdin.readline 
number, weight = input().rstrip().split()
number = int(number)
weight = int(weight)

items = [list(map(int,input().rstrip().split())) for _ in range(number)]
#print(items)
dp = [[0]*(weight+1) for _ in range(number+1)]

for i in  range(number):
    for j in range(weight+1):
        if j < items[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-items[i][0]] + items[i][1])

print(dp[number][weight])

Submission status: Time Limit Exceeded

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

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

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

for i, (wi, vi) in enumerate(items):
    for j in range(w + 1):
        if j >= wi:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - wi] + vi)
        else:
            dp[i + 1][j] = dp[i][j]

print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(n)]

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

for i, (wi, vi) in enumerate(items):
    for j in range(w + 1):
        if j >= wi:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - wi] + vi)
        else:
            dp[i + 1][j] = dp[i][j]

print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
# リスト
N, W = list(map(int, input().split()))
w = list()
v = list()

dp = list()

for i in range (0, N):
	inp = list(map(int, input().split()))

	w.append(inp[0])
	v.append(inp[1])	

for i in range (0, N + 1):
	dp.append([0] * ( W + 1 ))

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

Submission status: Time Limit Exceeded

Solution code:
import math
from decimal import *

n, w = map(int, input().split())
cost, weights = [],[]
for i in range(n):
    a,b = map(int, input().split())
    weights.append(a)
    cost.append(b)

def kp(pt, c, ans):
    if(pt==-1 or c==0):
        return ans
    else:
        var1, var2 = 0, 0
        var1= kp(pt-1, c, ans)
        if(c >= weights[pt]):
            var2 = cost[pt]+kp(pt-1, c-weights[pt], ans)
        ans = max(var1, var2)
    return ans
ans = kp(n-1, w, 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    item_count, capacity = [int(x) for x in input().split()]
    weights, values = [], []
    for _ in range(item_count):
        w, v = [int(x) for x in input().split()]
        weights.append(w)
        values.append(v)
    # dp[i][j]
    # = (i番目までの品物を、重さがj以下になるように選んだときの価値の最大値)
    dp = [[0] * (capacity + 1) for _ in range(item_count)]
    for item_i in range(item_count):
        for weight_i in range(1, capacity + 1):
            if (w := weights[item_i]) <= weight_i:
                dp[item_i][weight_i] = max(
                    dp[item_i - 1][weight_i - w] + values[item_i],
                    dp[item_i - 1][weight_i])
            else:
                dp[item_i][weight_i] = dp[item_i - 1][weight_i]
    print(dp[item_count - 1][capacity])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main(N, W, P):
    dp = [[0]*(W + 1) for _ in range(N)]
    for j in range(P[0][0], W+1):
        dp[0][j] = P[0][1]

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

            dp[i][j] = max(dp[i-1][j-P[i][0]] + P[i][1],
                        dp[i-1][j])

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

if __name__ == "__main__":
    N, W = map(int, input().split()) #N個の製品、Wの制限
    P = [tuple(map(int, input().split())) for _ in range(N)]
    main(N, W, P)

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split()) #N個の製品、Wの制限
P = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[0]*(W + 1) for _ in range(N)]

for j in range(P[0][0], W+1):
    dp[0][j] = P[0][1]

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

        dp[i][j] = max(dp[i-1][j-P[i][0]] + P[i][1],
                       dp[i-1][j])

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

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split()) #N個の製品、Wの制限
P = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[0]*(W + 1) for _ in range(N)]

for j in range(P[0][0], W+1):
    dp[0][j] = P[0][1]

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

        dp[i][j] = max(dp[i-1][j-P[i][0]] + P[i][1],
                       dp[i-1][j],
                       dp[i][j-1])

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

Submission status: Time Limit Exceeded

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

w_list = [0] * n
v_list = [0] * n
for i in range(n):
    w_list[i], v_list[i] = map(int, input().split())

dp = [0] * (w + 1)
for i in range(n):
    for j in range(w, -1, - 1):
        v = dp[j] + v_list[i]
        if j + w_list[i] <= w and dp[j + w_list[i]] < v:
            dp[j + w_list[i]] = v
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
n,W=list(map(int,input().split()))
li=[]
wr=[0]*n
vr=[0]*n
dd = [[0 for _ in range(W+1)] for k in range(n+1)]

for i in range(n):
	w,v=map(int,input().split())
	wr[i]=w
	vr[i]=v
mw=min(wr)
def maxv(i,w):
	if dd[i][w]!=0:
		
		return dd[i][w]
	if i==n:
		return 0
	if W-w<mw:
		return 0
	if w+wr[i]<=W:
		a=vr[i]+maxv(i+1,w+wr[i])
	else:
		a=0
	b=maxv(i+1,w)
	c=max(a,b)
	dd[i][w]=c
	return c
print(maxv(0,0))

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
ITEM = []
vmax, wmax = 0,0
for _ in range(N):
  w,v = map(int, input().split())
  ITEM.append((v,w))
  vmax = max(vmax,v)
  wmax = max(wmax,w)

INF = 10**18
    
def solve2():
  #dp[i][w] i個目までを選んで、重さW以下で実現できる最大の価値
  # TLEしたらiを消す。
  dp = [0] * (wmax*N+1)
  dp[0] = 0
  for i in range(1,N+1):
    v1,w1 = ITEM[i-1]
    # dp[i]消すなら、wは大きい方から探索する
    for w in range(wmax*i,-1,-1):
      if w-w1>=0:
        dp[w] = max(dp[w], dp[w-w1]+v1)
  ret = max(dp[:W+1])
  
  #for d in dp:
    #print(dp[0:20])
  return ret

ans = solve2()
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n,W=list(map(int,input().split()))
li=[]
wr=[0]*n
vr=[0]*n
dd=defaultdict(lambda:0)
for i in range(n):
	w,v=map(int,input().split())
	wr[i]=w
	vr[i]=v
mw=min(wr)
def maxv(i,w):
	if dd[(i,w)]!=0:
		
		return dd[(i,w)]
	if i==n:
		return 0
	if W-w<mw:
		return 0
	if w+wr[i]<=W:
		a=vr[i]+maxv(i+1,w+wr[i])
	else:
		a=0
	b=maxv(i+1,w)
	c=max(a,b)
	dd[(i,w)]=c
	return c
print(maxv(0,0))

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
w_v = [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):
        dp[i+1][j] = max(dp[i][j], dp[i+1][j])
        if j-w_v[i][0] >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-w_v[i][0]] + w_v[i][1])
print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n,W=list(map(int,input().split()))
li=[]
wr=[0]*n
vr=[0]*n
dd=defaultdict(lambda:0)
for i in range(n):
	w,v=map(int,input().split())
	wr[i]=w
	vr[i]=v
mw=min(wr)
def maxv(i,w):
	if dd[(i,w)]!=0:
		return dd[(i,w)]
	if i==n:
		return 0
	if W-w<mw:
		return 0
	if w+wr[i]>W:
		m=maxv(i+1,w)
		dd[(i,w)]=m
		return m
	a=vr[i]+maxv(i+1,w+wr[i])
	b=maxv(i+1,w)
	c=max(a,b)
	dd[(i,w)]=c
	return c
print(maxv(0,0))

Submission status: Time Limit Exceeded

Solution code:
#from collections import defaultdict
n,W=list(map(int,input().split()))
li=[]
wr=[0]*n
vr=[0]*n
#dd=defaultdict(lambda:0)
for i in range(n):
	w,v=map(int,input().split())
	wr[i]=w
	vr[i]=v
def maxv(i,w):
	#if dd[(i,w)]!=0:
#		return dd[(i,w)]
	if i==n:
		return 0
	if w+wr[i]>W:
		m=maxv(i+1,w)
		#dd[(i,w)]=m
		return m
	a=vr[i]+maxv(i+1,w+wr[i])
	b=maxv(i+1,w)
	c=max(a,b)
	return c
print(maxv(0,0))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n,W=list(map(int,input().split()))
li=[]
wr=[0]*n
vr=[0]*n
dd=defaultdict(lambda:0)
for i in range(n):
	w,v=map(int,input().split())
	wr[i]=w
	vr[i]=v
def maxv(i,w):
	if dd[(i,w)]!=0:
		return dd[(i,w)]
	if i==n:
		return 0
	if w+wr[i]>W:
		m=maxv(i+1,w)
		dd[(i,w)]=m
		return m
	a=vr[i]+maxv(i+1,w+wr[i])
	b=maxv(i+1,w)
	c=max(a,b)
	dd[(i,w)]=c
	return c
print(maxv(0,0))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n,W=list(map(int,input().split()))
li=[]
wr=[0]*n
vr=[0]*n
dd=defaultdict(lambda:0)
for i in range(n):
	w,v=map(int,input().split())
	wr[i]=w
	vr[i]=v
def maxv(i,w):
	if dd[(i,w)]!=0:
		return dd[(i,w)]
	if i==n:
		return 0
	if w+wr[i]>W:
		return maxv(i+1,w)
	a=vr[i]+maxv(i+1,w+wr[i])
	b=maxv(i+1,w)
	c=max(a,b)
	dd[(i,w)]=c
	return c
print(maxv(0,0))

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 for _ in range(W+1)] for i 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[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import *
sys.setrecursionlimit(1000100)
MOD=1000000007
INF=(1<<60)
pi=acos(-1.0)

def chmin(ans,b):
  if ans[0]>b:
    ans[0]=b
    return True
  else:
    return False
def chmax(ans,b):
  if ans[0]<b:
    ans[0]=b
    return True
  else:
    return False


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

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

##dp
table=[[-INF for i in range(W+1)] for j in range(N)]

def dp(i,j):
  if i<0 or j<=0:
    return 0
  if table[i][j]>-INF:
    return table[i][j]
  
  ret=[-INF]
  chmax(ret,dp(i-1,j))
  if j-w[i]>=0:
    chmax(ret,dp(i-1,j-w[i])+v[i])
    
  table[i][j]=ret[0]
  return table[i][j]

print(dp(N-1,W))

"""
for i in range(N):
  for j in range(W+1):
    if(j!=0):
      print(" ",end="")
    print(dp(i,j),end="")
  print()
"""

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 7)

n, w = map(int, input().split())
weights, values = [], []

for _ in range(n):
    wi, vi = map(int, input().split())
    
    weights.append(wi)
    values.append(vi)  

@lru_cache(maxsize=1024)
def f(w, n):
    # if (w, n) in cache:
        # return cache[(w, n)]
    
    if w == 0 or n == 0:
        # cache[(w, n)] = 0
        return 0
    
    if w < weights[n-1]:
        return f(w, n-1)

    
    return max(f(w, n-1), f(w-weights[n-1], n-1) + values[n-1])

print(f(w, len(weights)))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

n, w = map(int, input().split())
weights, values = [], []

for _ in range(n):
    wi, vi = map(int, input().split())
    
    weights.append(wi)
    values.append(vi)  

cache = {}
def f(w, n):
    if (w, n) in cache:
        return cache[(w, n)]
    
    if w == 0 or n == 0:
        cache[(w, n)] = 0
        return 0
    
    if w < weights[n-1]:
        return f(w, n-1)

    
    return max(f(w, n-1), f(w-weights[n-1], n-1) + values[n-1])


print(f(w, len(weights)))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

n, w = map(int, input().split())
weights, values = [], []

for _ in range(n):
    wi, vi = map(int, input().split())
    
    weights.append(wi)
    values.append(vi)  

@lru_cache(maxsize=1024)
def f(w, n):
    if w == 0 or n == 0:
        return 0
    
    if w < weights[n-1]:
        return f(w, n-1)

    return max(f(w, n-1), f(w-weights[n-1], n-1) + values[n-1])


print(f(w, len(weights)))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

n, w = map(int, input().split())
weights, values = [], []

for _ in range(n):
    wi, vi = map(int, input().split())
    
    weights.append(wi)
    values.append(vi)

weights, values = tuple(weights), tuple(values)    

@lru_cache(maxsize=None)
def f(w, n):
    if w == 0 or n == 0:
        return 0
    
    if w < weights[n-1]:
        return f(w, n-1)

    return max(f(w, n-1), f(w-weights[n-1], n-1) + values[n-1])


print(f(w, len(weights)))

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
val,w = [],[]
for _ in range(N):
  wi,ni = map(int,input().split())
  val.append(ni)
  w.append(wi)

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout
n, w = list(map(int,stdin.readline().split()))
values = []
weights = []
for _ in range(n):
	v,a = list(map(int, stdin.readline().split()))
	values.append(a)
	weights.append(v)
values = [0] + values
weights = [0] + weights

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

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

print(str(dp[n][w]))

Submission status: Time Limit Exceeded

Solution code:
n, w = list(map(int,input().split()))
values = []
weights = []
for _ in range(n):
	v,a = list(map(int,input().split()))
	values.append(a)
	weights.append(v)
values = [0] + values
weights = [0] + weights

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

for i in range(n+1):
	for j in range(w+1):
		if i == 0 or j == 0:
			dp[i][j] = 0
		else:
			if weights[i] <= j:
				dp[i][j] = max(dp[i-1][j],
			   	dp[i-1][j-weights[i]] + values[i])
			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())
W=[]
V=[]
for i in range(n):
  a,b=map(int,input().split())
  W.append(a)
  V.append(b)
DP=[[0]*(w+1) for j in range(n+1)]
for p in range(n):
  for q in range(w+1):
    if q<W[p]:
      DP[p+1][q]=DP[p][q]
    else:
      DP[p+1][q]=max(DP[p][q], DP[p][q-W[p]]+V[p])
print(DP[n][w])

Submission status: Time Limit Exceeded

Solution code:
n,mw=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(n)]
dp=[[0 for _ in range(mw+1)]for _ in range(n+1)]
for i in range(n):
    w,v=l[i]
    for j in range(mw):
        dp[i+1][j]=max(dp[i+1][j],dp[i][j])
        if j+w<=mw:
            dp[i+1][j+w]=max(dp[i+1][j+w],dp[i][j]+v)
print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
 
dpt = [0] * (W+1)
 
for i in range(N):
    w, v = map(int, input().split())
    for j in range(W, w-1, -1):
        a = dpt[j]
        b = dpt[j-w]+v
        if a > b:
            dpt[j] = a
        else:
            dpt[j] = b
 
print(dpt[W])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
items = [list(map(int, input().split())) for i in range(N)]

dpt = [0] * (W+1)

for w, v in items:
    for j in range(W, w-1, -1):
        a = dpt[j]
        b = dpt[j-w]+v
        if a > b:
            dpt[j] = a
        else:
            dpt[j] = b

print(dpt[W])

Submission status: Time Limit Exceeded

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

dpt = [0] * (W+1)

for w, v in items:
    for j in range(W, w-1, -1):
        a = dpt[j]
        b = dpt[j-w]+v
        if a > b:
            dpt[j] = a
        else:
            dpt[j] = b

print(dpt[W])

Submission status: Time Limit Exceeded

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

dpt = [0] * (W+1)

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

print(dpt[W])

Submission status: Time Limit Exceeded

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

dpt = [0] * (W+1)

for i in range(N):
    w, v = items[i]
    for j in range(W, w-1, -1):
        dpt[j] = max(dpt[j], dpt[j-w] + v)

print(dpt[W])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
m,w = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(m)]

dp = [[0]*(w+1) for _ in range(m+1)]

# 初期値を調整
for w_i in range(1, w+1):
  dp[0][w_i] = float("-inf")
  
for w_i in range(w+1):
  for m_i in range(1, m+1):
    if w_i-WV[m_i-1][0]>=0:
      dp[m_i][w_i] = max(dp[m_i-1][w_i], dp[m_i-1][w_i-WV[m_i-1][0]]+WV[m_i-1][1])
    else:
      dp[m_i][w_i] = dp[m_i-1][w_i]

      
print(max(dp[-1]))

Submission status: Time Limit Exceeded

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

weight=[]
value=[]

for i in range(n):
    a,b=map(int,input().split())
    weight+=[a]
    value+=[b]

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

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

print(dp[n][w])