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, 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())
# print(w)
# print(v)
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
# print(dp)
# dp loop
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)
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np

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

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

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

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

print(dp[0][W])

Submission status: Time Limit Exceeded

Solution code:
n, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
w = [wv[i][0] for i in range(n)]
v = [wv[i][1] for i in range(n)]
inf = float('inf')
# dp[i][weight] 
# := i-1番目までの品物で重さweightを超えないように選んだときの価値の総和の最大値
dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
for i in range(n):
    for sum_w in range(W+1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[i])
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
print(dp[n][W])

Submission status: Time Limit Exceeded

Solution code:
n,W=map(int,input().split())
items=[list(map(int,input().split())) for i in range(n)]
w=[items[i][0] for i in range(n)]
v=[items[i][1] for i in range(n)]

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

print(dp[0][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)]
w=[items[i][0] for i in range(n)]
v=[items[i][1] for i in range(n)]

memo=[[-1]*(W+1) for i in range(n+1)]
def dfs(i,j):
  global memo
  if memo[i][j]>=0:
    return memo[i][j]
  else :
    if i==n:
      memo[i][j]=0
    elif j<w[i]:
      memo[i][j]=dfs(i+1,j)
    else:
      memo[i][j]=max(dfs(i+1,j),dfs(i+1,j-w[i])+v[i])
  return memo[i][j]

print(dfs(0,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)]
w=[items[i][0] for i in range(n)]
v=[items[i][1] for i in range(n)]

memo=[[-1]*(W+1) for i in range(n+1)]
def dfs(i,j):
  if memo[i][j]>=0:
    return memo[i][j]
  else :
    if i==n:
      memo[i][j]=0
      return memo[i][j]
    elif j<w[i]:
      memo[i][j]=dfs(i+1,j)
      return memo[i][j]
    else:
      memo[i][j]=max(dfs(i+1,j),dfs(i+1,j-w[i])+v[i])
      return memo[i][j]
print(dfs(0,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)]
w=[items[i][0] for i in range(n)]
v=[items[i][1] for i in range(n)]

memo=[[-1]*(W+1) for i in range(n+1)]
def dfs(i,j):
  if i==n:
    return 0
  if memo[i][j]!=-1:
    return memo[i][j]
  else:
    if  j<w[i]:
      memo[i][j]=dfs(i+1,j)
      return memo[i][j]
    else:
      memo[i][j]=max(dfs(i+1,j),dfs(i+1,j-w[i])+v[i])
      return memo[i][j]
print(dfs(0,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)]
w=[items[i][0] for i in range(n)]
v=[items[i][1] for i in range(n)]

memo=[[-1]*(W+1) for i in range(n+1)]
def dfs(i,j):
  if i==n:
    return 0
  if memo[i][j]!=-1:
    return memo[i][j]
  else:
    if  j<w[i]:
      return dfs(i+1,j)
    else:
      return max(dfs(i+1,j),dfs(i+1,j-w[i])+v[i])
print(dfs(0,W))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, Counter, defaultdict
from fractions import gcd

input = sys.stdin.readline  


def main():
    n, w = map(int, input().split())
    WVs = [list(map(int, input().split())) for i in range(n)]
    #i個目の品物を取る場合
    dp = [[0]*(w+1) for _ in range (n)]
    dp[0] = [0]*(w+1)

    for i in range(n):
        for j in range(w+1):
            wi = WVs[i][0]
            vi = WVs[i][1]

            if j - wi >= 0:
                dp[i][j] = max([dp[i-1][j-wi] + vi, dp[i-1][j]])
            else:
                dp[i][j] = dp[i-1][j] 

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

    for i in range(min(W, W-w), -1, -1):
        if dp[i] != -1:
            dp[i+w] = max(dp[i+w], dp[i]+v)

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
#1:初期化
N,W = map(int,input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int,input().split())))
dp = [[0]*(W+1) for i in range(N+1)]

#print(wv)
#print(dp)
#2:初期値(元からゼロなので記述無し)

#3:dp実行部(貰うDP)
for i in range(1,N+1):
    for j in range(1,W+1):
        if wv[i-1][0] <= j:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
        else:
            dp[i][j] = dp[i-1][j]
        #print(i,j)
        #print(*dp,sep="\n")

#4:出力
print(dp[N][W])

Submission status: Time Limit Exceeded

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

table = [[0] * (W + 1) for _ in range(N + 1)]
for n in range(N):
    for w in range(W + 1):
        addn = table[n][w - goods[n][0]] + goods[n][1] if w - goods[n][0] >= 0 else 0
        table[n + 1][w] = max(table[n][w], addn)
print(table[N][W])

Submission status: Time Limit Exceeded

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

def main():
  n, W = map(int, input().split())
  dp = [0]*(W+1)
  for _ in range(n):
    w, v = map(int, input().split())
    for j in range(W, w-1, -1):
      dp[j] = max(dp[j-w] + v, dp[j])
  print(dp[W])
  
if __name__ == "__main__":
  main()

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

def f2(N,W,weights, values):
    @lru_cache(None)
    def f3(i,j):
        if i == 0 and j <= 0:
            return 0
        if j <= 0 or i < 0:
            return 0
        if j - weights[i] >= 0:
            return max(values[i] + f3(i-1, j - weights[i]),f3(i-1,j))
        return f3(i-1,j)
    return f3(N-1,W)


N, W = map(int, input().split())
weights, values = [0]*N, [0]*N
for i in range(N):
    weights[i], values[i] = map(int, input().split())
print(f2(N,W,weights,values))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

def f2(N,W,weights, values):
    @lru_cache(None)
    def f3(i,j):
        if i == 0 and j <= 0:
            return 0
        if j <= 0 or i < 0:
            return 0
        if j - weights[i] >= 0:
            return max(f3(i-1,j), values[i] + f3(i-1, j - weights[i]))
        return f3(i-1,j)
    return f3(N-1,W)


N, W = map(int, input().split())
weights, values = [0]*N, [0]*N
for i in range(N):
    weights[i], values[i] = map(int, input().split())
print(f2(N,W,weights,values))

Submission status: Time Limit Exceeded

Solution code:
def f(N,W,weights,values):
    dp = [[0]*(W+1) for _ in range(N+1)]

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


N, W = map(int, input().split())
weights, values = [0]*N, [0]*N
for i in range(N):
    weights[i], values[i] = map(int, input().split())
f(N,W,weights,values)

Submission status: Time Limit Exceeded

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

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

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

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

print(dp[W][n])

Submission status: Time Limit Exceeded

Solution code:
n,w = map(int, input().split())
wv = []
for _ in range(n):
    data = list(map(int,input().split()))
    wv.append(data)
 
dct={}
 
def solve(i,j):
    if i>=n:
        return 0
 
    ky = str(i)+"_"+str(j)
    if ky in dct:
        return dct[ky]
 
 
    weight=wv[i][0]
    value =wv[i][1]
 
    if j<weight: # can't push this item
        val = solve(i+1,j)
    else:# push or not push
        val =  max(solve(i+1,j-weight)+value, solve(i+1,j))
 
    dct[ky] = val
 
    return val
 
print(solve(0,w))

Submission status: Time Limit Exceeded

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

dct={}

def solve(i,j):
    if i>=n:
        return 0

    ky = str(i)+"_"+str(j)
    if ky in dct:
        return dct[ky]


    weight=wv[i][0]
    value =wv[i][1]

    if j<weight: # can't push this item
        val = solve(i+1,j)
    else:# push or not push
        val =  max(solve(i+1,j-weight)+value, solve(i+1,j))

    dct[ky] = val

    return val

print(solve(0,w))

Submission status: Time Limit Exceeded

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

def solve(i,j):
    if i>=n:
        return 0

    weight=wv[i][0]
    value =wv[i][1]

    if j<weight: # can't push this item
        val = solve(i+1,j)
    else:# push or not push
        val =  max(solve(i+1,j-weight)+value, solve(i+1,j))

    return val

print(solve(0,w))

Submission status: Time Limit Exceeded

Solution code:
a = list(map(int, input().split()))
b = [list(map(int, input().split())) for i in range(a[0])]

result = []

max_weight = a[1]

def calc(i, queue):
    if len(b) <= i:
        return

    current = b[i]
    prev = queue[-1] if 0 < len(queue) else [0, 0] 
    
    if current[0] + prev[0] <= max_weight:
        result.append(prev[1] + current[1])
    
    next_queue = queue[:]
    next_queue.append([prev[0] + current[0], prev[1] + current[1]])
    calc(i + 1, next_queue)
    calc(i + 1, queue)

calc(0, [])

print(max(result))

Submission status: Time Limit Exceeded

Solution code:
a = list(map(int, input().split()))
b = [list(map(int, input().split())) for i in range(a[0])]

result = []

max_weight = a[1]

def calc(i, queue):
    if len(b) <= i:
        return

    current = b[i]
    # print(queue)
    # print(i - 1)
    prev = queue[-1] if 0 < len(queue) else [0, 0] 
    
    if current[0] + prev[0] <= max_weight:
        result.append(prev[1] + current[1])
    
    next_queue = queue[:]
    next_queue.append([prev[0] + current[0], prev[1] + current[1]])
    # print(next_queue)
    # print(queue)
    calc(i + 1, next_queue)
    calc(i + 1, queue)

calc(0, [])

print(max(result))

Submission status: Time Limit Exceeded

Solution code:
input1 = input().split()

N = int(input1[0])
C = int(input1[1])

item_list = []
item_list.append([0,0])


for _ in range(N):
    input2 = input().split()
    item_list.append(list(map(int,input2)))
    

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



for i in range(N):
    for w in range(C + 1):
        for s in range(w + 1):
            if item_list[i + 1][0] == s:
                dp[i + 1][w] = dp[i][w - s] + item_list[i + 1][1]
            else:
                dp[i+1][w] = max(dp[i+1][w],dp[i][w])


print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
input1 = input().split()

N = int(input1[0])
C = int(input1[1])

item_list = []
item_list.append([0,0])


for _ in range(N):
    input2 = input().split()
    item_list.append(list(map(int,input2)))
    

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


for i in range(N):
    s = item_list[i + 1][0]
    for w in range(C + 1):
        if s <= w:
            dp[i + 1][w] = max(dp[i][w], dp[i][w - s] + item_list[i + 1][1])
        else:
            dp[i + 1][w] = dp[i][w]


print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
input1 = input().split()

N = int(input1[0])
C = int(input1[1])

item_list = []
item_list.append([0,0])


for _ in range(N):
    input2 = input().split()
    item_list.append(list(map(int,input2)))
    

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



for i in range(N):
    s = item_list[i + 1][0]
    for w in range(C + 1):
        if s <= w:
            dp[i + 1][w] = max(dp[i][w], dp[i][w - s] + item_list[i + 1][1])
        else:
            dp[i + 1][w] = dp[i][w]


print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
input1 = input().split()

N = int(input1[0])
C = int(input1[1])

item_list = []
item_list.append([0,0])


for _ in range(N):
    input2 = input().split()
    item_list.append(list(map(int,input2)))
    

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



for i in range(N):
    for w in range(C + 1):
        s = item_list[i + 1][0]
        if s <= w:
            dp[i + 1][w] = max(dp[i + 1][w], dp[i][w], dp[i][w - s] + item_list[i + 1][1])
        else:
            dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])


print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
input1 = input().split()

N = int(input1[0])
C = int(input1[1])

item_list = []
item_list.append([0,0])


for _ in range(N):
    input2 = input().split()
    item_list.append(list(map(int,input2)))
    

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



for i in range(N):
    for w in range(C + 1):
        for s in range(w + 1):
            if item_list[i + 1][0] == s:
                dp[i + 1][w] = dp[i][w - s] + item_list[i + 1][1]
            else:
                dp[i+1][w] = max(dp[i+1][w],dp[i][w])


print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
N, W, *t = map( int, open( 0 ).read().split() )
d = [[ 0 for _ in range( W + 1 ) ] for _ in range( N + 1 ) ]
ans = 0

i = 0
for w, v in zip( *[ iter( t )] * 2 ):
  for j in range( 1, W + 1 ):
    d[ i + 1 ][ j ] = d[ i ][ j ]
    if j - w >= 0:
      d[ i + 1 ][ j ] = max( d[ i ][ j - w ] + v, d[ i ][ j ] )
  i += 1
print( d[N][W])

Submission status: Time Limit Exceeded

Solution code:
# D
import numpy as np

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

weight = []
value = []
for i in range(N):
    x, y = list(map(int, input().split()))
    weight.append(x)
    value.append(y)

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

    #DP
    for i in range(N):
        for w in range(W+1):
          if weight[i]<=w: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
            dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
          else: #入る可能性はない
            dp[i+1][w]=dp[i][w]
    return dp[N][W]

print(knapsack(N,W,weight, value))

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
s = [list(map(int, input().split())) for i in range(n)]
ws = [x[0] for x in s]
v = [x[1] for x in s]

dp = [[0]*(w+1) for _ in range(n+1)]
for i in range(n):
    for sum_w in range(w+1):
        if sum_w + ws[i] <= w:
            dp[i+1][sum_w + ws[i]] = max(dp[i+1][sum_w + ws[i]],
                                         dp[i][sum_w]+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:
N, W = map(int, input().split())

wv = []
for i in range(N):
    wv.append(list(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 w - wv[i][0] >= 0:
            dp[i+1][w] = max(dp[i][w - wv[i][0]] + wv[i][1], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]

print(dp[N][W])

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    
    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 i in range(N+1)]

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

dp=[0]*(w+1)

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

print(max(dp))

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 i in range(N)])

dp = np.zeros((N+1, W+1), dtype=np.int)
for n in range(1, N + 1):
    for w in range(1, W+1):
        if w >= WV[n-1][0]:
        # weight = max(w-WV[n-1][0], 0)
            dp[n][w] = max(dp[n-1][w-WV[n-1][0]] + WV[n-1][1], dp[n-1][w])
        else:
            dp[n][w] = dp[n-1][w]

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

Submission status: Time Limit Exceeded

Solution code:
INF = 10**10 - 1


#指定数分の３つの整数を順番に受けてリストに入力
# スペース区切りの整数入力
N,Wmax = map(int, input().split())
w = [0]*(N+1)
v = [0]*(N+1)
for i in range(1,N+1):
    w[i],v[i] = map(int, input().split())

#dpの初期化
dp = [[-INF] * (Wmax+1) for i in range(N+1)]
for i in range(0,N+1):
    dp[i][0] = 0
#print(dp[0])

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

Vmax = 0
for ww in range(1,Wmax+1):
    Vmax = max(Vmax,dp[N][ww])
print(Vmax)

Submission status: Time Limit Exceeded

Solution code:
INF = 10**10 - 1


#指定数分の３つの整数を順番に受けてリストに入力
# スペース区切りの整数入力
N,Wmax = map(int, input().split())
w = [0]*(N+1)
v = [0]*(N+1)
for i in range(1,N+1):
    w[i],v[i] = map(int, input().split())

#dpの初期化
dp = [[-INF] * (Wmax+1) for i in range(N+1)]
for i in range(0,N+1):
    dp[i][0] = 0
#print(dp[0])

for i in range(1,N+1):
    for ww in range(1,Wmax+1):
        dp[i][ww] = dp[i-1][ww]        
        if w[i] > ww:
            continue
        else:
            dp[i][ww] = max(dp[i][ww],dp[i-1][ww-w[i]]+v[i])
    #print(dp[i])

Vmax = 0
for ww in range(1,Wmax+1):
    Vmax = max(Vmax,dp[N][ww])
print(Vmax)

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
List=[list(map(int,input().split())) for i in range(N)]
w,v=zip(*List)
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]>=0:
      dp[i+1][j]=max(dp[i+1][j],dp[i][j-w[i]]+v[i])
    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())
x = [list(map(int, input().split())) for _ in range(n)]

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

for i, (wi, vi) in enumerate(x):
    dp_pre = dp[1 - i % 2]
    dp_cur = dp[i % 2]
    for j in range(1, wi):
        dp_cur[j] = dp_pre[j]
    for j in range(wi, w + 1):
        dp_cur[j] = max(dp_pre[j], dp_pre[j - wi] + vi)
print(max(dp_cur))

Submission status: Time Limit Exceeded

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

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

for i, (wi, vi) in enumerate(x):
    for j in range(1, wi):
        dp[i % 2][j] = dp[1 - i % 2][j]
    for j in range(wi, w + 1):
        dp[i % 2][j] = max(dp[1 - i % 2][j], dp[1 - i % 2][j - wi] + vi)
print(max(dp[i % 2]))

Submission status: Time Limit Exceeded

Solution code:
# import math
# import numpy as np

# S = input()
# N = int(input())
N, W = map(int, input().split())
# A = list(map(int, input().split()))
# B = [int(input()) for _ in range(n)]
A = []
B = []
for _ in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)
# As = np.array(As)
# Bs = np.array(Bs)

# 二次元配列の初期化
# [[inf, inf, inf], [inf, inf, inf]]
dp = [[0] * (W + 1) for i in range(N + 1)]

def solve():
    for i in range(N):
        for w in range(W + 1):
            if w - A[i] >= 0:
                dp[i+1][w] = max(dp[i+1][w], dp[i][w - A[i]] + B[i])

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

    return dp[N][W]

# 0 [0, 0, 0, 0, 0, 0, 0, 0, 0]
# 1 [0, 0, 0, 30, 30, 30, 30, 30, 30]
# 2 [0, 0, 0, 30, 50, 50, 50, 80, 80]
# 3 [0, 0, 0, 30, 50, 60, 60, 80, 90]

print(solve())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, w = map(int ,input().split())
items = []
for i in range(n):
    array = list(map(int, input().split()))
    items.append(array)
dp = np.zeros((n+1, w+1))

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


print(int(dp[i][j]))

Submission status: Time Limit Exceeded

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

dp=[0]*(w+1)

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

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
#python3

def main():
    n, w = map(int, input().split())
    weight = [0 for _ in range(110)]
    value = [0 for _ in range(110)]

    for i in range(n):
        x, y = map(int, input().split())
        weight[i] = x
        value[i] = y

    
    dp = [[0 for _ in range(110000)] for i in range(110)]

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

main()

Submission status: Time Limit Exceeded

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

ws = [0] * n
vs = [0] * n

for i in range(n):
  a, b = map(int, input().split())
  ws[i] = a
  vs[i] = b
  
dp = [0] * (w + 1)

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

Submission status: Time Limit Exceeded

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

ws = []
vs = []

for i in range(n):
  a, b = map(int, input().split())
  ws.append(a)
  vs.append(b)

dp = [0] * (w + 1)

for i in range(n):
  for j in reversed(range(w + 1)):
    if j + ws[i] <= w:
      dp[j + ws[i]] = max(dp[j + ws[i]], dp[j] + vs[i])
      
print(dp[w])

Submission status: Time Limit Exceeded

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

ws, vs = zip(*[map(int, input().split()) for _ in range(n)])

dp = [0] * (w + 1)

for i in range(n):
  for j in reversed(range(w + 1)):
    if j + ws[i] <= w:
      dp[j + ws[i]] = max(dp[j + ws[i]], dp[j] + vs[i])
      
print(dp[w])

Submission status: Time Limit Exceeded

Solution code:
def solve(N, W, weightValues):
    dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
    for i in range(1, N + 1):
        w, v = weightValues[i - 1]
        for j in range(1, W + 1):
            if j < w:  # you cant take it
                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][W])


def iln(): return list(map(int, input().split()))


N, W = iln()
w_v = []
for i in range(N):
    w_v.append(iln())

solve(N, W, w_v)

Submission status: Time Limit Exceeded

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

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

print(dp[-1])

Submission status: Time Limit Exceeded

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


def knapsack(N,W,V):
    dp = [[0]*(W+1) for _ in range(N+1)]

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

print(knapsack(N,W,V))

Submission status: Time Limit Exceeded

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


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

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

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

            if sum_w - wv[i][0] >= 0:
                DP[i+1][sum_w] = max(
                    DP[i][sum_w - wv[i][0]] + wv[i][1],
                    DP[i+1][sum_w])

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

    print(DP[N][W])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

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

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

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

            if sum_w - wv[i][0] >= 0:
                DP[i+1][sum_w] = max(
                    DP[i][sum_w - wv[i][0]] + wv[i][1],
                    DP[i+1][sum_w])

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

    print(DP[N][W])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def solve(N, W, weight_values):
      dp = [0 for _ in range(W + 1)]
     
      for i in range(N):
        wi, vi = weight_values[i]
        for w in range(W, wi - 1, -1): # loop from W down to wi
          if dp[w - wi] + vi > dp[w]:
            dp[w] = dp[w - wi] + vi
     
      print(dp[W])
    
def iln(): return list(map(int, input().split()))

N, W = iln()
w_v = []
for i in range(N):
	w_v.append(iln())

solve(N, W, w_v)

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

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