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())
wv=[[0,0]]+[list(map(int,input().split())) for _ in range(N)]

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

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

            
print(max(dp[N]))

Submission status: Time Limit Exceeded

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

# DPテーブル
dp = np.zeros((N+1, W+1), dtype=int)


def solve():
    for n in range(N - 1, -1, -1):
        for w in range(0, W + 1):
            if w < wv[n, 0]:
                dp[n, w] = dp[n + 1, w]
            else:
                dp[n, w] = max(dp[n+1, w], dp[n+1, w - wv[n, 0]] + wv[n, 1])

    print(dp[0, W])


def main():
    solve()


##########
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, W = map(int, input().split())
    items = []
    for i in range(N):
        w, v = map(int, input().split())
        items.append({'value': v, 'weight': w})

    def knapsack(i, w):
        if i >= N:
            return 0
        elif w - items[i]['weight'] < 0:
            return knapsack(i+1, w)
        else:
            v1 = knapsack(i+1, w)
            v2 = knapsack(i+1, w - items[i]['weight']) + items[i]['value']
            return max(v1, v2)

    print(knapsack(0, W))


##########
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

        # 重さ j+w での最大価値
        X = {}
        for j in V.keys():
            if j+w <= W:
                X[j+w] = max(V.get(j+w, 0), V.get(j, 0) + v)

        for k in X.keys():
            V[k] = X[k]

        # 重さ w での最大価値 (単体での最大価値)
        if w <= W:
            V[w] = max(V.get(w, 0), v)

    print(max(V.values()))


##########
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, M = map(int, input().split())
    # C = [list(map(int, input().split())) for i in range(N)]
    V, W = [0]*N, [0]*N
    for i in range(N):
        W[i], V[i] = map(int, input().split())
    dp = [[0]*(M+1) for i in range(N+1)]
    # print(dp)
    # print(W)
    
    for i in range(N):
        for w in range(M+1):
            if w - W[i] >= 0:
               dp[i+1][w] = max(dp[i+1][w], dp[i][w-W[i]] + V[i]) 
            dp[i+1][w] = max(dp[i+1][w], dp[i][w])
    print(dp[N][M])    


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# D Knapsack 1
import sys

sys.setrecursionlimit(10**8)

n, w = map(int,input().split())
wv_list = [[int(x) for x in input().split()] for y in range(n)]

dp = [[float("-Inf")] * (w+1) for _ in range(n+1)]
dp[0] = [0]*(w+1)
memo = [[False] * (w+1) for _ in range(n+1)]
memo[0] = [True] * (w+1)

def dp_solve(i, j):
    if memo[i][j]:
        return dp[i][j]
    _w,_v = wv_list[i-1]
    _ret = 0
    if j-_w < 0:
        _ret = dp_solve(i-1, j)
    else:
        _ret = max(dp_solve(i-1, j), dp_solve(i-1, j-_w) + _v)
    dp[i][j] = _ret
    memo[i][j] = True
    return _ret

print(dp_solve(n, w))

Submission status: Time Limit Exceeded

Solution code:
# D Knapsack 1
import sys

sys.setrecursionlimit(10**8)

n, w = map(int,input().split())
wv_list = [[int(x) for x in input().split()] for y in range(n)]

dp = [[float("-Inf")] * (w+1) for _ in range(n+1)]
dp[0] = [0]*(w+1)
memo = [[False] * (w+1) for _ in range(n+1)]
memo[0] = [True] * (w+1)

def dp_solve(dp, wv_list, i, j):
    if memo[i][j]:
        return dp[i][j]
    _w,_v = wv_list[i-1]
    _ret = 0
    if j-_w < 0:
        _ret = dp_solve(dp, wv_list, i-1, j)
    else:
        _ret = max(dp_solve(dp, wv_list, i-1, j), dp_solve(dp, wv_list, i-1, j-_w) + _v)
    dp[i][j] = _ret
    memo[i][j] = True
    return _ret

print(dp_solve(dp, wv_list, 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 _ 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[N][W])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N0,W0 = map(int,input().split())

import copy
def exec_dp(N,W):
  dp = np.zeros(W+1,dtype=np.int64) 
  for i in range(N):
    w,v = map(int,input().split())
    prev = copy.copy(dp)
    for j in range(w,W+1):
      dp[j] = np.maximum(prev[j-w]+v, prev[j])
  print(dp[-1])

exec_dp(N0,W0)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N0,W0 = map(int,input().split())

import copy
def exec_dp(N,W):
  dp = np.zeros(W+1,dtype=np.int64) 
  for i in range(N):
    w,v = map(int,input().split())
    prev = copy.copy(dp)
    for j in range(W+1):
      if j >= w:
        dp[j] = np.maximum(prev[j-w]+v, prev[j])
  print(dp[-1])

exec_dp(N0,W0)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N0,W0 = map(int,input().split())

def exec_dp(N,W):
  dp = np.zeros((N+1,W+1),dtype=np.int64) 
  for i in range(N):
    w,v = map(int,input().split())
    for j in range(W+1):
      if j - w >= 0:
        dp[i+1][j] = np.maximum(dp[i][j-w] + v, dp[i][j])
      else:
        dp[i+1][j] = dp[i][j]
  print(int(dp[N][W]))

exec_dp(N0,W0)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N0,W0 = map(int,input().split())

def exec_dp(N,W):
  dp = np.zeros((N+1,W+1)) 
  for i in range(N):
    w,v = map(int,input().split())
    for j in range(W+1):
      if j - w >= 0:
        dp[i+1][j] = max(dp[i][j-w] + v, dp[i][j])
      else:
        dp[i+1][j] = dp[i][j]
  print(int(dp[N][W]))

exec_dp(N0,W0)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N0,W0 = map(int,input().split())
wv0 = [list(map(int,input().split())) for _ in range(N0)]

def exec_dp(N,W,wv):
  dp = np.zeros((N+1,W+1))
  for w in range(W+1):
    for i in range(N):
      w_prev = w - wv[i][0]
      if w_prev >= 0:
        a = dp[i][w_prev] + wv[i][1]
        b = dp[i][w]
        if a > b:
          dp[i+1][w] = a
        else:
          dp[i+1][w] = b
      else:
        dp[i+1][w] = dp[i][w]
  print(int(dp[N][W]))

exec_dp(N0,W0,wv0)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N0,W0 = map(int,input().split())
wv0 = [list(map(int,input().split())) for _ in range(N0)]

def exec_dp(N,W,wv):
  dp = np.zeros((N+1,W+1))
  for w in range(W+1):
    for i in range(N):
      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(int(max(dp[N])))

exec_dp(N0,W0,wv0)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(N)]

dp = np.zeros((N+1,W+1))
for w in range(W+1):
  for i in range(N):
    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(int(max(dp[N])))

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

Submission status: Time Limit Exceeded

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

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

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


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

print(dp[N][W])

Submission status: Time Limit Exceeded

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

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

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, W, *WV = map(int, read().split())
    weight = WV[::2]
    value = WV[1::2]

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

    print(dp[N][W])
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
def dfs(item_i, W):
    if item_i >= N:
        return 0
    if visited[item_i][W]:
        return table[item_i][W]
    visited[item_i][W] = True
    if W - w_list[item_i] < 0:
        table[item_i][W] = dfs(item_i+1, W)
    else:
        table[item_i][W] = max(dfs(item_i+1, W), dfs(item_i+1, W-w_list[item_i]) + v_list[item_i])
    
    return table[item_i][W]

N, W = map(int, input().split())
w_list = []
v_list = []
for i in range(N):
    w, v = map(int, input().split())
    w_list += [w]
    v_list += [v]
table = [[0 for j in range(W+1)]for i in range(N)]
visited = [[False for j in range(W+1)]for i in range(N)]

ans = dfs(0, W)
print(ans)

Submission status: Time Limit Exceeded

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

import sys
import numpy as np

def main():
    n,k = map(int,(input().split()))
    items=[np.array((input().split()),int) for _ in range(n)]
    dp = np.zeros((n,k+1))
    for i in range(n):
        for j in range(k+1):
            if i==0 and j>=items[0][0]:
                dp[0][j]=items[0][1]
            elif i>0 and j>=items[i][0]:
                dp[i][j]=max(dp[i-1][j],items[i][1]+dp[i-1][j-items[i][0]])
            elif j < items[i][0] and i > 0:
                dp[i][j]=dp[i-1][j]
    print (int(dp.max()))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


def main():
    N, W = [int(i) for i in input().strip().split()]
    items = [[int(i) for i in input().strip().split()] for _ in range(N)]

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

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

    return dp[-1][-1]


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

Submission status: Time Limit Exceeded

Solution code:
def chmax(dp, i, x):
  if dp[i] < x:
    dp[i] = x
    return True
  return False

n, W = map(int, input().split())
dp = [-10**9]*(W+1)
dp[0] = 0
for i in range(n):
  w, v = map(int, input().split())
  for i in range(W-w,-1,-1):
    dp[i+w] = max(dp[i+w], dp[i] + v) 
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
input = sys.stdin.readline

# sys.setrecursionlimit(100000)


def main():
    N, W = [int(i) for i in input().strip().split()]
    items = [[int(i) for i in input().strip().split()] for _ in range(N)]

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

    def knapsack(capacity, value, idx):
        if dp[capacity][idx] != -1:
            return dp[capacity][idx]
        if idx < 0 or W < 0:
            return value
        if items[idx][0] > capacity:
            dp[capacity][idx] = knapsack(capacity, value, idx - 1)
            return dp[capacity][idx]
        else:
            dp[capacity][idx] = max(
                knapsack(capacity, value, idx - 1),
                knapsack(capacity - items[idx][0],
                         value, idx-1) + items[idx][1]
            )
            return dp[capacity][idx]

    knapsack(W, 0, N - 1)
    return max(dp[-1])


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

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
input = sys.stdin.readline

# sys.setrecursionlimit(100000)


def main():
    N, W = [int(i) for i in input().strip().split()]
    items = [[int(i) for i in input().strip().split()] for _ in range(N)]

    @lru_cache(None)
    def knapsack(capacity, value, idx):
        if idx < 0:
            return value
        if items[idx][0] > capacity:
            return knapsack(capacity, value, idx - 1)
        else:
            return max(
                knapsack(capacity, value, idx - 1),
                knapsack(capacity - items[idx][0],
                         value + items[idx][1], idx - 1)
            )

    return knapsack(W, 0, N-1)


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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, W =map(int, input().split())
weight = [0] * 110
value = [0] * 110
dp = np.zeros(shape=(N + 1, W + 1), dtype = np.int64)
#dp = [[0] * (110) for _ in range(10010)]

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

for i in range(N):
    for w in range(W + 1):
        if(w >= weight[i]):
            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:

def knap(w,v,c,n):
    if c==0 or n==0:
        return 0
    if w[n-1]<=c:
        return max(knap(w,v,c-w[n-1],n-1)+v[n-1],knap(w,v,c,n-1))
    else:
        return knap(w,v,c,n-1)
      
n,c=map(int,input().split())
v= []
w = []
for  i in range(n):
  W,V=map(int,input().split())
  w.append(W)
  v.append(V)
print(knap(w,v,c,n))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n,w=n1()
WV=n3(n)

W=[0]
W.extend([x[0] for x in WV])
V=[0]
V.extend([x[1] for x in WV])

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-W[i]>=0:
            dp[i][j]=max(dp[i-1][j-W[i]]+V[i],dp[i-1][j])
        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())
ws = [0] * N
vs = [0] * N

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

import numpy as np
dp_table = [[0]*(W+1) for _ in range(N+1)]

for i in range(1,N+1):
  for w_now in range(1,W+1):
    if w_now - ws[i-1] >= 0:
      dp_table[i][w_now] = max( dp_table[i-1][w_now], dp_table[ i-1][w_now-ws[i-1] ] + vs[i-1] )
    else:
      dp_table[i][w_now] = dp_table[i-1][w_now]
print(int(dp_table[-1][-1]))

Submission status: Time Limit Exceeded

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

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

import numpy as np
dp_table = np.zeros((N+1,W+1))

for i in range(1,N+1):
  for w_now in range(1,W+1):
    if w_now - ws[i-1] >= 0:
      dp_table[i, w_now] = max( dp_table[i-1 , w_now], dp_table[ i-1, w_now-ws[i-1] ] + vs[i-1] )
    else:
      dp_table[i, w_now] = dp_table[i-1 , w_now]
print(int(dp_table[-1, -1]))

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
a = list()
a.append([0, 0])
inf = float('inf')
for _ in range(N):
  x = list(map(int, input().split()))
  a.append(x)
dp = [[-inf for _ in range(W+1)]for _ in range(N+1)]
# dp[i][w] : i-1番目までで、wを超えないように選んだ時の価値の最大値
for w in range(W+1):
  dp[0][w] = 0
for i in range(N):
  for w in range(W+1):
    # i番目を選ぶかもしれないとき
    if w - a[i+1][0] >= 0:
      dp[i+1][w] = max(dp[i][w], dp[i][w-a[i+1][0]] + a[i+1][1])
    # i番目を選ばないとき
    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())
W = [0] * n
V = [0] * n
for i in range(n):
    a, b = map(int, input().split())
    W[i] = a
    V[i] = b


dp = [[0] * (10 ** 5 + 10) for _ in range(n + 10)]
for i in range(n):
    for sum_num in range(w + 1):
        if sum_num - W[i] >= 0:
            dp[i + 1][sum_num] = max(dp[i][sum_num - W[i]] + V[i], dp[i][sum_num])
        else:
            dp[i + 1][sum_num] = dp[i][sum_num]

print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,W = map(int,input().split())
l = [list(map(int,input().split()))for i in range(N)]
dp = np.zeros(shape=(N,W + 1),dtype = int)
for i in range(l[0][0],W + 1):
    dp[0][i] = l[0][1]
for i in range(1,N):
    for j in range(W + 1):
        if l[i][0] > j:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - l[i][0]] + l[i][1])
print(dp[N - 1][W])

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

Submission status: Time Limit Exceeded

Solution code:
# # https://atcoder.jp/contests/dp/tasks/dp_d
# def main():

#     N, W = map(int, input().split())
#     wv = [list(map(int, input().split())) for _ in range(N)]
#     w = [wv[0] for _ in range(N)]
#     v = [wv[1] for _ in range(N)]
#     # dp_v[i][limited_w]:
#     # 重さ制限がlimited_wで、０からi-1番目までの品物を選んだときの価値の最大値
#     dp_v = [[0 for _ in range(W + 1)] for _ in range(N + 1)]

#     for i in range(N):
#         for weight in range(W + 1):
#             # 重さ制限weightのもとで品物iを選べるなら選び、価値を更新
#             if weight >= w[i]:
#                 dp_v[i + 1][weight] = max(dp_v[i][weight - w[i]] + v[i], dp_v[i][weight])
#             else:
#                 dp_v[i + 1][weight] = max(dp_v[i + 1][weight], dp_v[i][weight])


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

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

    for i in range(N):
        for weight in range(W+1):
            # 品物iを（選べるなら）選ぶ
            if weight >= w[i]:
                vdp[i+1][weight] = max(vdp[i][weight - w[i]] + v[i],
                                       vdp[i][weight])
            # 品物iを選ばない
            vdp[i+1][weight] = max(vdp[i+1][weight], vdp[i][weight])
    print(vdp[N][W])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,v=[int(k) for k in input().split()]
li=[]
for i in range(n):
  li.append([int(k) for k in input().split()])
  
dp=[[0 for i in range(v+1)] for j in range(n+1)]
for a in range(1,n+1):
  for b in range(1,v+1):
    if(li[a-1][0]<=b):
      dp[a][b]=max(li[a-1][1]+dp[a-1][b-li[a-1][0]],dp[a-1][b])
    else:
      dp[a][b]=dp[a-1][b]
print(dp[n][v])

Submission status: Time Limit Exceeded

Solution code:
n,v=[int(k) for k in input().split()]
li=[]
for i in range(n):
  li.append([int(k) for k in input().split()])
  
dp=[[0 for i in range(v+1)] for j in range(n+1)]
for a in range(1,n+1):
  for b in range(1,v+1):
    if(li[a-1][0]<=b):
      dp[a][b]=max(li[a-1][1]+dp[a-1][b-li[a-1][0]],dp[a-1][b])
    else:
      dp[a][b]=dp[a-1][b]
print(dp[n][v])

Submission status: Time Limit Exceeded

Solution code:
def rec(i, j):
    if dp[i][j] >= 0:
        return dp[i][j]
    if i==n:
        res = 0
    elif j < w[i]:
        res = rec(i+1, j)
    else:
        res = max(rec(i+1, j), rec(i+1, j-w[i])+v[i])
    # print(res)
    dp[i][j] = res
    return res
    

n, W = map(int, input().split())
w = []
v = []
for i in range(n):
    w1, v1 = map(int, input().split())
    w.append(w1)
    v.append(v1)
dp = [[-1]*(W+1) for i in range(n+1)]
print(rec(0, W))

Submission status: Time Limit Exceeded

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

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

print(ans[N][W])

Submission status: Time Limit Exceeded

Solution code:
import sys
rl = sys.stdin.readline
N, W = map(int, rl().split())
dp = [-1]*(W+1)
dp[0] = 0
for _ in range(N):
    w, v = map(int, rl().split())
    for i in range(W-w, -1, -1):
        dpi = dp[i]
        if dpi == -1:
            continue
        if dp[i+w] < dpi + v:
            dp[i+w] = dpi + v
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys

rl = sys.stdin.readline

N, W = map(int, rl().split())
li1 = [map(int, rl().split()) for _ in range(N)]
dp = [-1]*(W+1)
dp[0] = 0
for w, v in li1:
    for i in range(W-w, -1, -1):
        dpi = dp[i]
        if dpi == -1:
            continue
        if dp[i+w] < dpi + v:
            dp[i+w] = dpi + v
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
# D Knapsack 1


n, w = map(int,input().split())
wv_list = [[int(x) for x in input().split()] for y in range(n)]

dp = [[float("-Inf")] * (w+1) for _ in range(n+1)]
dp[0] = [0]*(w+1)
memo = [[False] * (w+1) for _ in range(n+1)]
memo[0] = [True] * (w+1)

def dp_solve(dp, wv_list, i, j):
    if memo[i][j]:
        return dp[i][j]
    _w,_v = wv_list[i-1]
    _ret = 0
    if j-_w < 0:
        _ret = dp_solve(dp, wv_list, i-1, j)
    else:
        _ret = max(dp_solve(dp, wv_list, i-1, j), dp_solve(dp, wv_list, i-1, j-_w) + _v)
    dp[i][j] = _ret
    memo[i][j] = True
    return _ret

print(dp_solve(dp, wv_list, n, w))

Submission status: Time Limit Exceeded

Solution code:
# D Knapsack 1


n, w = map(int,input().split())
wv_list = [[int(x) for x in input().split()] for y in range(n)]

dp = [[float("-Inf")] * (w+1) for _ in range(n+1)]
dp[0] = [0]*(w+1)
memo = [[False] * (w+1) for _ in range(n+1)]
memo[0] = [True] * (w+1)

def dp_solve(dp, wv_list, i, j):
    if memo[i][j]:
        return dp[i][j]
    _w,_v = wv_list[i-1]
    _ret = 0
    if j-_w < 0:
        _ret = dp_solve(dp, wv_list, i-1, j)
    else:
        _ret = max(dp_solve(dp, wv_list, i-1, j), dp_solve(dp, wv_list, i-1, j-_w) + _v)
    dp[i][j] = _ret
    return _ret

print(dp_solve(dp, wv_list, n, w))

Submission status: Time Limit Exceeded

Solution code:
# D Knapsack 1
import copy

n, w = map(int, input().split())
wv_list = [[int(x) for x in input().split()] for y in range(n)] # n*2

dp = [float('-Inf')] * (w+2)
dp[0] = 0
buy_list = [[False] * n for j in range(w+2)] # (w+2)*n

for i in range(w):
    for j in range(n):
        if buy_list[i][j]:
            continue
        _w = wv_list[j][0]
        _v = wv_list[j][1]
        if i+_w > w:
            _w = w - i + 1
        if dp[i+_w] < dp[i]+_v:
            dp[i+_w] = dp[i]+_v
            buy_list[i+_w] = copy.deepcopy(buy_list[i])
            buy_list[i+_w][j] = True
            
print(max(dp[:w+1]))

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

Submission status: Time Limit Exceeded

Solution code:
import sys
# import numpy as np
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))
# import profile

def solve():
	n, w = read(); 
	dp = [[0 for i in range(w+1)] for j in range(n)]
	w_v_list = [read() for i in range(n)]
	# for i in dp:print(*i)
	# print("\n")
	# print(w_v_list)
	for i in range(n):
		for j in range(w+1):
			elem_w, elem_v = w_v_list[i]
			if elem_w <= j:
				dp[i][j] = max(elem_v + dp[i-1][j - elem_w], dp[i][j-1], dp[i-1][j])
				# w_v_list[i][1] = 0
			else:
				dp[i][j] = max(dp[i][j-1], dp[i-1][j])
	# for i in dp:print(*i)
	print(dp[n-1][w])




if __name__ == "__main__":
	solve()

Submission status: Time Limit Exceeded

Solution code:
n, W = [int(x) for x in input().split()]
ans = 0
dp = [0 for _ in range(W+1)]
for i in range(n):
    weight, value = [int(x) for x in input().split()]    
    for w in reversed(range(W+1)):
        if w >= weight:
            dp[w] = max(dp[w], dp[w-weight]+value)

ans = max(dp)

print(ans)
"""
int main() {
    int n;
    int W;
    long long ans = 0;
    scanf("%d%d", &n, &W);
    
    vector<vector<long long>> dp(n+1, vector<long long>(W+1));
    
    for (int i = 1; i <= n; i++) {
        int weight;
        int value;
        scanf("%d%d", &weight, &value);
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i-1][w]; // ignore
            if (w >= weight) {
                dp[i][w] = max(dp[i][w], dp[i-1][w-weight]+value); // add
            }
            ans = max(ans, dp[i][w]);
        }
    }
    
    printf("%lld", ans);
    
	return 0;
}
"""

Submission status: Time Limit Exceeded

Solution code:
n, W = [int(x) for x in input().split()]
ans = 0
dp = [0 for _ in range(W+1)]
for i in range(n):
    weight, value = [int(x) for x in input().split()]    
    for w in reversed(range(W+1)):
        if w >= weight:
            dp[w] = max(dp[w], dp[w-weight]+value)

ans = max(dp)

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

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