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:
def DP():
  
  n,m=map(int,input().split())
  dp=[0]*(m+2)

  for i in range(n):  #商品を一つずつ見ていく。
    w,v=(map(int,input().split()))
    for j in range(m+1,w,-1): #w~(限界-w)までのdpの箱に入れていく。(例)w,m=3,8なら3~5
      if (dp[j-w]+v)>dp[j]:
        dp[j]=dp[j-w]+v
      else:
        dp[j]=dp[j]
  return max(dp) 
print(DP())

Submission status: Time Limit Exceeded

Solution code:
def DP():
  n,m=map(int,input().split())
  dp=[0]*(m+2)

  for i in range(n):  #商品を一つずつ見ていく。
    w,v=(map(int,input().split()))
    for j in range(m+1,w,-1): #w~(限界-w)までのdpの箱に入れていく。(例)w,m=3,8なら3~5
      dp[j]=max(dp[j-w]+v,dp[j])
  return max(dp)
print(DP())

Submission status: Time Limit Exceeded

Solution code:
n,W = map(int, input().split(' '))
WV = (map(int, input().split(' ')) for _ in range(n))
dp = [0] * (W+1)
 
for w, v in WV:
  for j in range(W, w-1, -1):
    DP = dp[j-w] + v
    if dp[j] < DP:
      dp[j] = DP
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n,W = map(int, input().split(' '))
WV = (map(int, input().split(' ')) for _ in range(n))
dp = [0] * (W+1)
 
for w, v in WV:
  for j in range(W, w-1, -1):
    DP = dp[j-w] + v
    if dp[j] < DP:
      dp[j] = DP
print(dp[W])

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
dp=[0]*(m+2)

for i in range(n):  #商品を一つずつ見ていく。
  w,v=(map(int,input().split()))
  for j in range(m+1,w,-1): #w~(限界-w)までのdpの箱に入れていく。(例)w,m=3,8なら3~5
    if (dp[j-w]+v)>dp[j]:
      dp[j]=dp[j-w]+v
    else:
      dp[j]=dp[j]
    
print(dp[m+1])

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
dp=[0]*(m+2)

for i in range(n):  #商品を一つずつ見ていく。
  w,v=(map(int,input().split()))
  for j in range(m+1,w,-1): #w~(限界-w)までのdpの箱に入れていく。(例)w,m=3,8なら3~5
    dp[j]=max(dp[j-w]+v,dp[j])
    
print(dp[m+1])

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
d=[ list(map(int,input().split()))  for i in range(n)]
dp=[0]*(m+2)

for i in range(n):  #商品を一つずつ見ていく。
  for j in range(m+1,d[i][0],-1): #w~(限界-w)までのdpの箱に入れていく。(例)w,m=3,8なら3~5
    dp[j]=max(dp[j-d[i][0]]+d[i][1],dp[j]) #d[i][0]=w d[i][1]=v
    
print(dp[m+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.append(a)
  value.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 - weight[i] >= 0:
      dp[i+1][j] = max(dp[i][j],dp[i][j-weight[i]] + value[i])
    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())

dp = [0] * (W + 1)

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

print(dp[W])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
n,w=map(int,input().split())
l=[[]]
for i in range(n):
  l.append(list(map(int,input().split())))
dp=[[-1 for i in range(w+2)] for j in range(n+2)]
def knap(x,y):
  if dp[x][y]!=-1:
    return dp[x][y]
  if x==n+1:
    res=0
  elif y<l[x][0]:
    res=knap(x+1,y)
  else:
    res=max(knap(x+1,y),knap(x+1,y-l[x][0])+l[x][1])
  dp[x][y]=res
  return res
knap(1,w)
print(dp[1][w])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
n,w=map(int,input().split())
l=[]
for i in range(n):
  l.append(list(map(int,input().split())))
dp=[[-1 for i in range(w+1)] for j in range(n+1)]
def knap(x,y):
  if dp[x][y]!=-1:
    return dp[x][y]
  if x==n:
    res=0
  elif y<l[x][0]:
    res=knap(x+1,y)
  else:
    res=max(knap(x+1,y),knap(x+1,y-l[x][0])+l[x][1])
  dp[x][y]=res
  return res
knap(0,w)
print(dp[0][w])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
n,w=map(int,input().split())
l=[[]]
for i in range(n):
  l.append(list(map(int,input().split())))
dp=[[-1 for i in range(w+1)] for j in range(n+1)]
def knap(x,y):
  if x==n+1:
    return 0
  if dp[x][y]!=-1:
    return dp[x][y]
  elif y<l[x][0]:
    res=knap(x+1,y)
  else:
    res=max(knap(x+1,y),knap(x+1,y-l[x][0])+l[x][1])
  dp[x][y]=res
  return res
knap(1,w)
print(dp[1][w])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
n,w=map(int,input().split())
l=[[]]
for i in range(n):
  l.append(list(map(int,input().split())))
dp=[[-1 for i in range(w+2)] for j in range(n+2)]
def knap(x,y):
  if dp[x][y]!=-1:
    return dp[x][y]
  if x==n+1:
    res=0
  elif y<l[x][0]:
    res=knap(x+1,y)
  else:
    res=max(knap(x+1,y),knap(x+1,y-l[x][0])+l[x][1])
  dp[x][y]=res
  return res
knap(1,w)
print(dp[1][w])

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
l=[[]]
for i in range(n):
  l.append(list(map(int,input().split())))
dp=[[-1 for i in range(w+1)] for j in range(n+1)]
for i in range(w+1):
  dp[0][i]=0
for j in range(n+1):
  dp[j][0]=0
def knap(x,y):
  if dp[x][y]!=-1:
    return dp[x][y]
  else:
    if l[x][0]>y:
      res=knap(x-1,y)
    else:
      res=max(knap(x-1,y),knap(x-1,y-l[x][0])+l[x][1])
    dp[x][y]=res
    return res
knap(n,w)
print(dp[n][w])

Submission status: Time Limit Exceeded

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


def chmax(a, b):
    """
    2値の大きい値を返す

    Args:
        a   (int)   : 値１
        b   (int)   : 値２
    Return:
        a   (int)   : aまたはbの大きい値
    """
    if a < b:
        a = b
    return a


def main():

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

    # knopsock[n][0] = w    :   n = 品物の位置 , w = 重さ
    # knopsock[n][1] = v    :   n = 品物の位置 , v = 価値
    knapsack = [list(map(int, readline().split())) for _ in range(N)]

    # db[n][w] = v          :   w = 現在の重さ, n = 見てきた品物の数, v = 現在の価値
    dp = [[0] * (W + 1) for _ in range(N + 1)]

    for n in range(1, N + 1):
        for w in range(W + 1):
            if w - knapsack[n - 1][0] < 0:
                dp[n][w] = dp[n - 1][w]
            else:
                dp[n][w] = chmax(dp[n - 1][w], dp[n - 1]
                                 [w - knapsack[n - 1][0]] + knapsack[n - 1][1])

    print(dp[N][W])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 再帰関数使用時は再帰上限を十分にとること
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
 
# グローバル変数定義
INF = 10 ** 13
N, W = map(int, input().split())
 
# knopsock[n][0] = w    :   n = 品物の位置 , w = 重さ
# knopsock[n][1] = v    :   n = 品物の位置 , v = 価値
knapsack = [list(map(int, input().split())) for _ in range(N)]
 
# db[n][w] = v          :   w = 現在の重さ, n = 見てきた品物の数, v = 現在の価値
db = [[INF] * W for _ in range(N)]
 
 
def dfs(n, w):
    """
    品物に対する深さ優先探索による全探索（メモ化再帰）。
 
    Args:
        n (int) : 見てきた品物の数
        w (int) : ここまでの重さの総和
 
    Returns:
        v (int) : 価値の総和の最大値
    """
 
    # 終了条件：現在の個数が全ての品物の個数を越える
    if n >= N:
        return 0
 
    if w + knapsack[n][0] > W:
        # １つ前までの重さ + 今回の品物の重さが重さの最大値を越えていたら今回の品物は選べない
        return dfs(n + 1, w)
    else:
        # 今回の品物を選ぶか選ばないかで全探索
        return max([dfs(n + 1, w), dfs(n + 1, w + knapsack[n][0]) + knapsack[n][1]])
 
 
def main():
    out = dfs(0, 0)
    print(out)
 
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 再帰関数使用時は再帰上限を十分にとること
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

# グローバル変数定義
INF = 10 ** 13
N, W = map(int, input().split())

# knopsock[n][0] = w    :   n = 品物の位置 , w = 重さ
# knopsock[n][1] = v    :   n = 品物の位置 , v = 価値
knapsack = [list(map(int, input().split())) for _ in range(N)]

# db[n][w] = v          :   w = 現在の重さ, n = 見てきた品物の数, v = 現在の価値
db = [[INF] * W for _ in range(N)]


def dfs(n, w):
    """
    品物に対する深さ優先探索による全探索（メモ化再帰）。

    Args:
        n (int) : 見てきた品物の数
        w (int) : ここまでの重さの総和

    Returns:
        v (int) : 価値の総和の最大値
    """

    # 終了条件：現在の個数が全ての品物の個数を越える
    if n >= N:
        return 0

    if w + knapsack[n][0] > W:
        # １つ前までの重さ + 今回の品物の重さが重さの最大値を越えていたら今回の品物は選べない
        return dfs(n + 1, w)
    else:
        # 今回の品物を選ぶか選ばないかで全探索
        return max([dfs(n + 1, w), dfs(n + 1, w + knapsack[n][0]) + knapsack[n][1]])


def main():
    out = dfs(0, 0)
    print(out)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 再帰関数使用時は再帰上限を十分にとること
import sys
sys.setrecursionlimit(10 ** 8)

# グローバル変数定義
INF = 10 ** 13
N, W = map(int, input().split())

# knopsock[n][0] = w    :   n = 品物の位置 , w = 重さ
# knopsock[n][1] = v    :   n = 品物の位置 , v = 価値
knapsack = [list(map(int, input().split())) for _ in range(N)]

# db[n][w] = v          :   w = 現在の重さ, n = 見てきた品物の数, v = 現在の価値
db = [[INF] * W for _ in range(N)]


def dfs(n, w):
    """
    品物に対する深さ優先探索による全探索（メモ化再帰）。

    Args:
        n (int) : 見てきた品物の数
        w (int) : ここまでの重さの総和

    Returns:
        v (int) : 価値の総和の最大値
    """

    # 終了条件：現在の個数が全ての品物の個数を越える
    if n >= N:
        return 0

    if w + knapsack[n][0] > W:
        # １つ前までの重さ + 今回の品物の重さが重さの最大値を越えていたら今回の品物は選べない
        return dfs(n + 1, w)
    else:
        # 今回の品物を選ぶか選ばないかで全探索
        return max([dfs(n + 1, w), dfs(n + 1, w + knapsack[n][0]) + knapsack[n][1]])


def main():
    out = dfs(0, 0)
    print(out)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
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 w in range(W+1):
    if w-_w >= 0:
      dp[i+1][w] = max(dp[i][w],dp[i][w-_w]+_v)
    else:
      dp[i+1][w] = dp[i][w]

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
import sys

import numpy as np

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

# 数と重さで配列を作る
# 値は価値の最大値


def main():
    N, W = map(int, readline().split())
    WV = np.array([[int(x) for x in readline().split()] for _ in range(N)])

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

    for w, v in WV:
        np.maximum(dp[1:, w:], dp[:-1, :-w] + v, out=dp[1:, w:])

    print(np.max(dp[:, W]))


main()

Submission status: Time Limit Exceeded

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

table = {i: [0]*(W+1) for i in range(N+1)}
def dp(N, W):
  for i in range(1, N+1):
    w, v = items[i-1]
    for j in range(1, W+1):
      if w <= j:
        table[i][j] = max(table[i-1][j-w]+v, table[i-1][j])
      else:
        table[i][j] = table[i-1][j]
  return table[N][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 _ in range(N)]

import numpy as np

table = np.zeros((N+1, W+1))
def dp(N, W):
  for i in range(1, N+1):
    w, v = items[i-1]
    for j in range(1, W+1):
      if w <= j:
        table[i][j] = max(table[i-1][j-w]+v, table[i-1][j])
      else:
        table[i][j] = table[i-1][j]
  return int(table[N][W])

print(dp(N, W))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import copy

def main():
    N, W= map(int, raw_input().split())
    dp = np.zeros(W+1)
 
    for i in range(N):
        w, v = map(int, raw_input().split())
        dp_temp = copy.deepcopy(dp)
        for j in range(W+1):
            dp_pre = dp[j]
            if j-w > -1:
                dp_update = dp[j-w] + v
            else:
                dp_update = 0
            dp_temp[j] = max(dp_pre, dp_update)
 
        dp = dp_temp
 
    print int(dp[-1])

main()

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, raw_input().split())
dp = [0]*(W+1)
 
for i in xrange(N):
    w, v = map(int, raw_input().split())
    for j in xrange(W, w-1, -1):
        x = dp[j-w] + v
        if x > dp[j]:
            dp[j] = x
 
print dp[-1]

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, raw_input().split())
a = []
for i in range(N):
    a.append(map(int, raw_input().split()))

dp = [0]*(W+1)

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

print dp[-1]

Submission status: Time Limit Exceeded

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

for i in range(N):
    w, v = map(int, raw_input().split())
    for j in range(W, w-1, -1):
        x = dp[j-w] + v
        if x > dp[j]:
            dp[j] = x

print dp[-1]

Submission status: Time Limit Exceeded

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

for i in range(N):
    w, v = map(int, raw_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, raw_input().split())
dp = np.zeros(W+1)

for i in range(N):
    w, v = map(int, raw_input().split())
    for j in range(W, w-1, -1):
        x = dp[j-w]+v
        if x > dp[j]:
            dp[j] = x


print int(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, W = map(int, raw_input().split())
dp = np.zeros(W+1)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, W = map(int, raw_input().split())
dp = np.zeros((W+1, N))

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import copy
 
N, W = map(int, raw_input().split())
dp = np.zeros((W+1, N))

w, v = map(int, raw_input().split())

dp[w][0] = v

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

print int(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)]
res=[0 for _ in range(w+1)]
for i in range(n):
    for j in range(w,a[i][0]-1,-1):
        res[j]=max(res[j],res[j-a[i][0]]+a[i][1])
print(res[w])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import copy

N, W= map(int, raw_input().split())
dp = np.zeros(W+1)

for i in range(N):
   w, v = map(int, raw_input().split())
   dp_temp = copy.deepcopy(dp)
   for j in range(W+1):
      dp_pre = dp[j]
      if j-w > -1:
         dp_update = dp[j-w] + v
      else:
         dp_update = 0
      dp_temp[j] = max(dp_pre, dp_update)

   dp = dp_temp

print int(dp[-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
n, W = map(int, sys.stdin.readline().split())
#L = [[map(int, sys.stdin.readline().split())] for _ in range(n)]
dp = [[0 for _ in range(W+1)] for _ in range(n)]
for i in range(n):
    w, v =map(int, sys.stdin.readline().split())
    for j in range(W+1):
        dp[i][j] = max(dp[i-1][j], dp[i][j])
        if dp[i-1][j] !=0 and j+w<=W:
            dp[i][j+w] = max(dp[i-1][j+w], v+ dp[i-1][j])
            #print(dp, i)
        
    dp[i][w] = max(dp[i-1][w], v)
    

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

Submission status: Time Limit Exceeded

Solution code:
N, W = [int(_) for _ in input().split()]
dp = [0] * (W + 10)  # [[0] * 3 for _ in range(10 ** 5 + 2)]

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

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
# W分の配列を用意、全Wに対してVが最大になるものを見つける
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for _ in range(N)]

dp=[-1]*(W+1)
dp[0]=0
for i in range(N):
  w,v=WV[i]
  for j in range(W-w,-1,-1): # 逆順じゃないと同じものを二つ選べる
    if dp[j]!=-1:
      dp[j+w]=max(dp[j+w],dp[j]+v)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
# W分の配列を用意、全Wに対してVが最大になるものを見つける
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for _ in range(N)]

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

Submission status: Time Limit Exceeded

Solution code:
class Knapsack:
    def __init__(self):
        pass

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

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

def knapsack_01():
    for i in range(1, N+1):
        for w in range(1, W+1):
            if items[i].w <= w:
                if items[i].v + C[i-1][w-items[i].w] > C[i-1][w]:
                    C[i][w] = items[i].v + C[i-1][w-items[i].w]
                else:
                    C[i][w] = C[i-1][w]
            else:
                C[i][w] = C[i-1][w]

knapsack_01()
print(C[N][W])

Submission status: Time Limit Exceeded

Solution code:
# D - Knapsack 1 Educational DP Contest / DP
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

N,W = nm()
Weight = []
Value = []

for i in range(N):
    w,v = nm()
    Weight.append(w)
    Value.append(v)

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m = map(int, input().split())
    w = [0] * n
    v = [0] * n
    for i in range(n):
        wt, vt = list(map(int, input().split()))
        w[i] = wt
        v[i] = vt
    l = [0] * (m + 1)
    for i in range(n):
        for j in range(m, -1, -1):
            l[j] = max(v[i] + l[j-w[i]], l[j]) if j - w[i] >= 0 else l[j]
    print(l[-1])
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m = map(int, input().split())
    w = [0] * n
    v = [0] * n
    for i in range(n):
        wt, vt = list(map(int, input().split()))
        w[i] = wt
        v[i] = vt
    l = [0] * (m + 1)
    for i in range(n):
        l= [max(v[i] + l[j-w[i]], l[j]) if j - w[i] >= 0 else l[j] for j in range(m+1)]
    print(l[-1])
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m = map(int, input().split())
    w = [0] * n
    v = [0] * n
    for i in range(n):
        wt, vt = list(map(int, input().split()))
        w[i] = wt
        v[i] = vt
    l = [[0] * (m + 1) for _ in range(n)]
    for i in range(n):
        for j in range(m+1):
            if j - w[i] >= 0:
                l[i][j] = max(v[i] + l[i-1][j-w[i]], l[i-1][j])
            else:
                l[i][j] = l[i-1][j]
    print(l[-1][-1])
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, W = map(int, input().split())
    wi, vi = map(int, input().split())
    dp = [0] * wi + [vi] * (W + 1 - wi)
    for _ in range(1, N):
        wi, vi = map(int, input().split())
        dp[wi:] = [max(i + vi, j) for i, j in zip(dp, dp[wi:])]
    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,c = map(int,raw_input().split())

wt =[]
val =[]

for _ in range(n):
    w,v = map(int,raw_input().split())
    wt.append(w)
    val.append(v)
    

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

    
for i in range(n+1):
    for j in range(c+1):
        if i == 0 or j == 0:
            dp[i][j] = 0
        elif  wt[i-1] <= j:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-wt[i-1]]+val[i-1])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[n][c])

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
array = [[0] * (W+1) for i in range((N+1))]
for i in range(N):
  wei,V = map(int,input().split())
  for j in range(W):
    if(wei<=j+1):
      new=array[i][j-wei+1]+V
      if(array[i][j] < new):
        array[i+1][j+1]=new
      else:
        array[i+1][j+1]=array[i][j+1]
    else:
      array[i+1][j+1]=array[i][j+1]
print(array[N][W])

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
array = [[0] * (W+1) for i in range((N+1))]
for i in range(N):
  wei,V = map(int,input().split())
  for j in range(W):
    if(wei<=j+1):
      if(array[i][j] < array[i][j-wei+1]+V):
        array[i+1][j+1]=array[i][j-wei+1]+V
      else:
        array[i+1][j+1]=array[i][j+1]
    else:
      array[i+1][j+1]=array[i][j+1]
print(array[N][W])

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, W = map(int, readline().split())
tmp = map(int, read().split())
wv = tuple(zip(tmp, tmp))

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
num,weight=map(int,input().split())
lv=[]
lw=[]
for i in range(num):
  a,b=map(int,input().split())
  lv.append(b)
  lw.append(a)
dp=[[-1 for i in range(weight+1)] for j in range(num)]
for i in range(weight+1):
  if i<lw[0]:
    dp[0][i]=0
  else:
    dp[0][i]=lv[0]
def nap(n,w):
  if dp[n][w]!=-1:
    return dp[n][w]
  else:
    res=0
    if lw[n]>w:
      res=nap(n-1,w)
    else:
      m1=nap(n-1,w)
      m2=nap(n-1,w-lw[n])+lv[n]   
      res=max(m1,m2)
    dp[n][w]=res
    return res
nap(num-1,weight)
print(dp[num-1][weight])

Submission status: Time Limit Exceeded

Solution code:

def main():
    n, maxweight = map(int, input().rstrip().split())
    dp = [0 for i in range(maxweight+1)]

    for wn in range(n):
        weight, value = map(int, input().rstrip().split())
        for w in range(maxweight-weight+1):
            dp[w] = max(dp[w], dp[w+weight] + value)
    print(max(dp))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

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

for i in range(N):
  weight[i], value[i] = map(int, input().split())
  
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[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
N,W=map(int,input().split())

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

for i in range(N):
    w,v=map(int,input().split())
    for index,item in enumerate(l):
        if item!=-1 and W>=index+w:
            dp[index+w]=max(item+v,l[index+w])
    l=dp[:]
print(max(l))

Submission status: Time Limit Exceeded

Solution code:
#メモ化したもの(修正版)
n,w=map(int,input().split())
a=[]
dp=[]
for i in range(n):
   a.append(list(map(int,input().split())))
for k in range(n+1):
   dp.append([])
   for l in range(w+1):
       dp[k].append(-1)
def rec(i,j):
   if dp[i][j]>=0:
       return dp[i][j]
   if i==n:
       res=0
   elif j<a[i][0]:
       res=rec(i+1,j)
   else:
       res=max(rec(i+1,j),rec(i+1,j-a[i][0])+a[i][1])
   dp[i][j]=res
   return res
print(rec(0,w))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

def solve(i, total):
    if dp[i][total] is not None:
        return dp[i][total]

    if i > n-1:
        return 0
    if total > W:
        return 0

    weight, val = w[i], v[i]
    if total + weight <= W:
        chose = val + solve(i+1, total + weight)
        unchose = solve(i+1, total)
        dp[i][total] = max(chose, unchose)
        return dp[i][total]
    else:
        dp[i][total] = solve(i+1, total)
        return dp[i][total]

print(solve(0, 0))

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

dp[0][0] = 0

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
def knapsack(n,w,li):
    #li[i][0]が重さ,li[i][1]が価値
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(w+1):
            if total_w - li[i][0] >= 0:
                dp[i+1][total_w] = max(dp[i][total_w],dp[i][total_w-li[i][0]]+li[i][1])
            else:
                dp[i+1][total_w] = dp[i][total_w]
    return max(dp[-1])
print(knapsack(n,w,li))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import numpy as np

n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
li = np.array(li)

def knapsack(n,w,li):
    #li[i][0]が重さ,li[i][1]が価値
    dp = np.zeros((n+1,w+1))
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(li[i][0]-1,w+1):
            if total_w - li[i][0] >= 0:
                dp[i+1][total_w] = max(dp[i][total_w],dp[i][total_w-li[i][0]]+li[i][1])
            else:
                dp[i+1][total_w] = dp[i][total_w]
    return int(dp[-1][-1])
print(knapsack(n,w,li))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import numpy as np

n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
li = np.array(li)

def knapsack(n,w,li):
    #li[i][0]が重さ,li[i][1]が価値
    dp = np.array([[0 for i in range(w+1)]for j in range(n+1)])
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(li[i][0]-1,w+1):
            if total_w - li[i][0] >= 0:
                dp[i+1][total_w] = max(dp[i][total_w],dp[i][total_w-li[i][0]]+li[i][1])
            else:
                dp[i+1][total_w] = dp[i][total_w]
    return dp[-1][-1]
print(knapsack(n,w,li))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
def knapsack(n,w,li):
    #li[i][0]が重さ,li[i][1]が価値
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(w+1):
            if total_w - li[i][0] >= 0:
                dp[i+1][total_w] = max(dp[i][total_w],dp[i][total_w-li[i][0]]+li[i][1])
            else:
                dp[i+1][total_w] = dp[i][total_w]
    return dp[-1][-1]
print(knapsack(n,w,li))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
n,w = [int(x) for x in stdin.readline().rstrip().split()]
nw = [0]*n
nv = [0]*n
for i in range(n):
    nw[i],nv[i] = [int(x) for x in stdin.readline().rstrip().split()]
def knapsack(n,w,nw,nv):
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(w+1):
            if total_w - nw[i] >= 0:
                dp[i+1][total_w] = max(dp[i][total_w],dp[i][total_w-nw[i]]+nv[i])
            else:
                dp[i+1][total_w] = dp[i][total_w]
    return dp[-1][-1]
print(knapsack(n,w,nw,nv))