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]*n
v = [0]*n

#dp = [[None for i in range(W+1)] for j in range(n+1)]
dp = [[None]*(W+1) for j in range(n+1)]

for i in range(n):
    v1, v2 = map(int, input().split())
#    v2, v1 = map(int, input().split())
    # w.append(v1)
    # v.append(v2)
    w[i] = v1
    v[i] = v2

# i: Index (Tracing all items)
# j: Remaining weight
# Return the sum of value
def knap(i, j):
    # print("\n# i: " + str(i))
    # print("# j: " + str(j))
    if dp[i][j] is not None:
        return dp[i][j]

    res = 0

    if i == n:
#        dp[i][j] = 0
        res = 0
    elif j < w[i]:
        res = knap(i+1, j)
    else:
        # if dp[i][j] is None:
        #     dp[i][j] = dp[i-1][j] + v[i]
        res = max(knap(i+1, j), knap(i+1, j-w[i]) + v[i])

    dp[i][j] = res
    return dp[i][j]
#    return res

print(knap(0, W))

Submission status: Time Limit Exceeded

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

dp = [[None for i in range(W+1)] for j in range(n+1)]

for i in range(n):
    v1, v2 = map(int, input().split())
#    v2, v1 = map(int, input().split())
    # w.append(v1)
    # v.append(v2)
    w[i] = v1
    v[i] = v2

# i: Index (Tracing all items)
# j: Remaining weight
# Return the sum of value
def knap(i, j):
    # print("\n# i: " + str(i))
    # print("# j: " + str(j))
    if dp[i][j] is not None:
        return dp[i][j]

    res = 0

    if i == n:
#        dp[i][j] = 0
        res = 0
    elif j < w[i]:
        res = knap(i+1, j)
    else:
        # if dp[i][j] is None:
        #     dp[i][j] = dp[i-1][j] + v[i]
        res = max(knap(i+1, j), knap(i+1, j-w[i]) + v[i])

    dp[i][j] = res
    return dp[i][j]
#    return res

print(knap(0, W))

Submission status: Time Limit Exceeded

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

for i in range(n):
    v1, v2 = map(int, input().split())
#    v2, v1 = map(int, input().split())
    w.append(v1)
    v.append(v2)

# i: Index (Tracing all items)
# j: Remaining weight
# Return the sum of value
def knap(i, j):
    # print("\n# i: " + str(i))
    # print("# j: " + str(j))
    if dp[i][j] is not None:
        return dp[i][j]

    res = 0

    if i == n:
#        dp[i][j] = 0
        res = 0
    elif j < w[i]:
        res = knap(i+1, j)
    else:
        # if dp[i][j] is None:
        #     dp[i][j] = dp[i-1][j] + v[i]
        res = max(knap(i+1, j), knap(i+1, j-w[i]) + v[i])

    dp[i][j] = res
    return dp[i][j]
#    return res

print(knap(0, W))

Submission status: Time Limit Exceeded

Solution code:
import sys

n, k = map(int, sys.stdin.readline().split())

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


for i in range(1,n+1):
    w, v = map(int, sys.stdin.readline().split())
    
    for j in range(0, k+1):
        if j >= w:
            dp[i][j] = max(dp[i-1][j-w] + v, dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
            
print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys

n, k = map(int, sys.stdin.readline().split())

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


for i in range(n):
    w, v = map(int, sys.stdin.readline().split())
    
    temp = dp.copy()
    for j in range(k+1):
        if j+w <= k:
            dp[j+w] = max(temp[j+w], temp[j]+v)
            
print(max(dp))

Submission status: Time Limit Exceeded

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

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

# i: Index (Tracing all items)
# j: Remaining weight
# Return the sum of value
def knap(i, j):
    # print("\n# i: " + str(i))
    # print("# j: " + str(j))
    if dp[i][j] is not None:
        return dp[i][j]

    res = 0

    if i == n:
#        dp[i][j] = 0
        res = 0
    elif j < w[i]:
        res = knap(i+1, j)
    else:
        # if dp[i][j] is None:
        #     dp[i][j] = dp[i-1][j] + v[i]
        res = max(knap(i+1, j), knap(i+1, j-w[i]) + v[i])

    dp[i][j] = res
    return dp[i][j]
#    return res

print(knap(0, W))

Submission status: Time Limit Exceeded

Solution code:
w = []
v = []

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

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


def knap(i, j):
    res = 0

    if i == n:
        res = 0
    elif j < w[i]:
        res = knap(i+1, j)
    else:
        res = max(knap(i+1, j), knap(i+1, j-w[i]) + v[i])

    return res

print(knap(0, W))

Submission status: Time Limit Exceeded

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

w = []
v = []

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

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

for i in range(N):
    for j in range(0, W+1):
        if j - w[i] >= 0:  # i 番目の品物が容量 j に対して（他を0個以上捨てれば）入れられる場合
            if dp[i+1][j] < dp[i][j - w[i]] + v[i]:
                dp[i+1][j] = dp[i][j - w[i]] + v[i]

        if dp[i+1][j] < dp[i][j]:
            dp[i+1][j] = dp[i][j] # i 番目の品物を入れた場合と入れなかった場合の比較

print(dp[N][W])

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
        dp[j] = max(dp[j], DP)

print(max(dp))

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 w, v in wv:
    for j in range(W, w-1, -1):
        DP = dp[j-w] + v
        dp[j] = max(dp[j], DP)

print(max(dp))

Submission status: Time Limit Exceeded

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

w = []
v = []

dp = [0] * (W+1)

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

print(max(dp))

Submission status: Time Limit Exceeded

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

w = []
v = []

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

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

for i in range(N):
    for j in range(0, W+1):
        if j - w[i] >= 0:  # i 番目の品物が容量 j に対して（他を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]) # i 番目の品物を入れた場合と入れなかった場合の比較

print(dp[N][W])

Submission status: Time Limit Exceeded

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

IN = list(list(map(int, input().split())) for _ in range(N))
sumw = 0
sumv = 0
for w, v in IN:
    sumw += w
    sumv += v

DP = dict()
DP[sumv] = sumw

def minv(i, v):
    if not DP.get(i):
        DP[i] = v
    else:
        if v < DP[i]:
            DP[i] = v

if sumw <= W:
    ans = sumv
else:
    ans = 0
    for w, v in IN:
        DPpre = DP.copy()
        for i in DPpre:
            answ = i - v
            minv(answ, DPpre[i]-w)
            if answ > ans:
                if DP[answ] <= W:
                    ans = answ
                    continue

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**8)

N, W = map(int, input().split(" "))
WV = [list(map(int, input().split(" "))) for _ in range(N)]

l = [[None for _ in range(W+1)] for _ in range(N+1)]
def dp(i, limit):
    if i == -1:
        return 0
    if l[i][limit] != None:
        return l[i][limit]
    w, v = WV[i]
    if w <= limit:
        l[i][limit] = max(
            dp(i-1, limit),
            dp(i-1, limit-w) + v
        )
    else:
        l[i][limit] = dp(i-1, limit)
    return l[i][limit]

print(dp(N-1, W))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**8)

N, W = map(int, input().split(" "))
WV = [list(map(int, input().split(" "))) for _ in range(N)]

l = [[None for _ in range(W+1)] for _ in range(N+1)]
def dp(i, limit):
    if i == -1:
        return 0
    if l[i][limit] == None:
        w, v = WV[i]
        if w <= limit:
            l[i][limit] = max(
                dp(i-1, limit),
                dp(i-1, limit-w) + v
            )
        else:
            l[i][limit] = dp(i-1, limit)
    return l[i][limit]

print(dp(N-1, W))

Submission status: Time Limit Exceeded

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

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

def knapsack1(dp, lst):
    for i , wv in enumerate(lst, 1):
        w, v = wv
        i_ob = i - 1
        dp[i] = ([0] + [max(dp[i_ob][j], dp[i_ob][j-w] + v) if w <= j 
                  else dp[i_ob][j] for j in range(1, W + 1)])
        
    print(dp[-1][-1])

knapsack1(dp, lst)

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
wv = list(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):
    w,v = wv[i]
    for j in range(1,W+1):
        if j >= w:
            DP[i+1][j] = max(DP[i][j-w]+v,DP[i][j],DP[i+1][j-1])
        else:
            DP[i+1][j] = max(DP[i][j],DP[i+1][j-1])
print(DP[-1][-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 = [[-1]*(W + 1) for _ in range(N+1)]

def DP(n,weight):
    if dp[n][weight] >= 0:
        return dp[n][weight]
    if n == N-1:
        if weight >= WV[n][0]:
            dp[n][weight] = WV[n][1]
        else:
            dp[n][weight] = 0
        return dp[n][weight]
    if weight == 0:
        dp[n][weight] = 0 
        return 0
    if weight >= WV[n][0]:
        dp[n][weight] =  max(DP(n+1,weight - WV[n][0]) + WV[n][1],DP(n+1,weight))
    else:
        dp[n][weight] = DP(n+1,weight)
    return dp[n][weight]
print(DP(0,W))

Submission status: Time Limit Exceeded

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

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

dp = [[0 for i in range(2*100)] for j in range(2*10**5)]

for i in range(N):
    for j in range(W+1):
        if (j - wv[i][0] >= 0):
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-wv[i][0]] + wv[i][1])
        
        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())
lis = [list(map(int,input().split())) for i in range(n)]
knap = {(0,0)}
for weight,value in lis:
    gone = set()
    for num,now in knap:
        if num + weight <= w:gone.add((num+weight,now+value))
    for nn,nu in gone:
        knap.add((nn,nu))
ans = 0

for num,value in knap:
    ans = max(ans,value)
print(ans)

Submission status: Time Limit Exceeded

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

w = []
v = []

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

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

Submission status: Time Limit Exceeded

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


def main():
    n, w = map(int, input().split())
    ws = [0 for _ in range(n)]
    vs = [0 for _ in range(n)]
    dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]

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

    for i in range(n):
        for sum_w in range(w + 1):
            if sum_w - ws[i] >= 0:
                dp[i + 1][sum_w] = max(dp[i + 1][sum_w],
                                       dp[i][sum_w - ws[i]] + vs[i])

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

    print(dp[n][w])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

dp=np.zeros((n+1, W+1), dtype=np.int64)

for i in range(n):
    for j in range(W+1):
        if w[i]>j:
            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())
wvs = [[int(kk) for kk in input().split()] for i in range(N)]

dp = [0]*(W+1)

for w,v in  wvs:
    for i in reversed(range(W+1)):
        #print(i)
        dp[i] = max(dp[i-w]+v,dp[i])
        if i == w:
            break

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

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

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

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)

n,w = (int(x) for x in input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = [[0] * (w+1) for _ in range(n+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 dp[i][j]

print(int(rec(0, w)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(200000)

n,w = (int(x) for x in input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = [[-1] * 100010 for _ in range(110)]

def rec(i, j):
  if dp[i][j] != -1:
    return dp[i][j]
  if i == n:
    return 0
  if 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 dp[i][j]

print(int(rec(0, w)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(200000)

n,w = (int(x) for x in input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = np.full((110, 100010), -1)

def rec(i, j):
  if dp[i][j] != -1:
    return dp[i][j]
  if i == n:
    return 0
  if 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 dp[i][j]

print(int(rec(0, w)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(200000)

n,w = (int(x) for x in input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = np.full((n+1, w+1), -1)

def rec(i, j):
  if dp[i][j] != -1:
    return dp[i][j]
  if i == n:
    res = 0
  elif j == 0:
    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 dp[i][j]

print(int(rec(0, w)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(200000)

n,w = (int(x) for x in input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = np.full((n+1, w+1), -1)

def rec(i, j):
  if dp[i][j] != -1:
    return dp[i][j]
  if i == n:
    res = 0
    dp[i][j] = res
    return dp[i][j]
  elif j < a[i][0]:
    res = rec(i+1, j)
    dp[i][j] = res
    return dp[i][j]
  else:
    res = max(rec(i+1, j), rec(i+1, j - a[i][0]) + a[i][1], 0)
    dp[i][j] = res
    return dp[i][j]

print(int(rec(0, w)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(200000)

n,w = (int(x) for x in input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = np.full((n+1, w+1), -1)

def rec(i, j):
  if dp[i][j] != -1:
    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], 0)
  dp[i][j] = res
  return dp[i][j]

print(int(rec(0, w)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(200000)

n,w = (int(x) for x in input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = np.full((n+1, w+1), -1)

def rec(i, j):
  if dp[i][j] != -1:
    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 dp[i][j]

print(int(rec(0, w)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(200000)

n,w = (int(x) for x in input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = np.zeros((n+1, w+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 dp[i][j]

print(int(rec(0, w)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(200000)

n,w = (int(x) for x in input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = np.zeros((n+1, w+1))

def rec(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 dp[i][j]
    
print(int(rec(0, w)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(200000)

n,w = (int(x) for x in input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = np.zeros((n+1, w+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 dp[i][j]
    
print(int(rec(0, w)))

Submission status: Time Limit Exceeded

Solution code:
inf = float('inf')

N,W = map(int,input().split())
w, v = [], []
for _ in range(N):
    wi, vi = map(int,input().split())
    w.append(wi)
    v.append(vi)

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import math
N,W = list(map(int, input().split(" ")))

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


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


        w,v = items[i]
        if w_sum - w >= 0:
            dp[i + 1][w_sum]  = dp[i][w_sum - w] + v
        # print(dp[i + 1][w],dp[i][w])
        a,b = dp[i + 1][w_sum],dp[i][w_sum]
        dp[i + 1][w_sum] = max(a,b)

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

Submission status: Time Limit Exceeded

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:

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

lis = [ [0] * (W+1) ]


for i in range(N):

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

    new = [0] * (W+1)

    for j in range(W+1):

        new[j] = max(new[j],lis[-1][j])

        if j+w <= W:

            new[j+w] = max(new[j+w],lis[-1][j]+v)

    lis.append(new)

print (lis[-1][W])

Submission status: Time Limit Exceeded

Solution code:

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

for i in range(N):

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

    new = []

    for j in lis[i]:

        if j[0] + w <= W:

            new.append([j[0] + w , j[1] + v])
            
        new.append([j[0] ,j[1]])

    lis.append(new)

ans = 0

for i in lis[-1]:

    ans = max( ans , i[1] )

print (ans)

Submission status: Time Limit Exceeded

Solution code:
n, weightMax = map(int, input().split())
itemList = [[0 for _ in range(weightMax+1)] for _ in range(n+1)]

for i in range(n):
    w,v = list(map(int, input().split()))
    for j in reversed(range(weightMax+1)):
        if j-w >= 0:
            itemList[i+1][j] = max([itemList[i][j],itemList[i][j-w] + v])
        else:
            itemList[i+1][j] = itemList[i][j]
print(max(itemList[n]))

Submission status: Time Limit Exceeded

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

WS = []
VS = []
for _ in range(0,N):
    w,v = map(int, input().split())
    WS.append(w)
    VS.append(v)

# print(WS)
# print(VS)

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

for i in range(0,N):
    w = WS[i]
    v = VS[i]
    for j in reversed(range(0,W+1)):
        if dp[j] >= 0 and j+w <= W:
            dp[j+w] = max(dp[j+w], dp[j]+v)

max_v = 0
for x in dp:
    max_v = max(max_v, x)

print(max_v)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
input=sys.stdin.readline
def intinput():return map(int,input().split())

n,maxw=intinput()
w=[None]*n
v=[None]*n
for i in range(n):
    w[i],v[i]=intinput()

memo={(0,i):0 for i in range(maxw+1)}
def dp(i,we):
    global w,v
    if (i,we) in memo:
        return memo[(i,we)]
    if w[i-1]>we:
        memo[(i,we)]=dp(i-1,we)
    else:
        memo[(i,we)]=max(dp(i-1,we),dp(i-1,we-w[i-1])+v[i-1])
    return memo[(i,we)]

print(dp(n,maxw))

Submission status: Time Limit Exceeded

Solution code:
def rec(depth, w, v):
    if w > maxW:
        return
    WV[depth][w] = max(v, WV[depth][w])
    if depth+1 >= N:
        return
    rec(depth+1, w+W[depth+1], v+V[depth+1])
    rec(depth+1, w, v)


N, maxW = map(int, input().split())
WV = [[-1 for i in range(maxW+1)] for j in range(N)]
W = [0 for i in range(N)]
V = [0 for i in range(N)]
for i in range(N):
    W[i], V[i] = map(int, input().split())
rec(0, 0, 0)
rec(0, W[0], V[0])
print(max(WV[-1]))

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
ws = [x[0] for x in wv]
vs = [x[1] for x in wv]

dp = [{} for _ in range(100)]
def dfs(weight=0, depth=N - 1):
    if dp[depth].get(weight) is not None:
        return dp[depth][weight]

    if depth == -1:
        dp[depth][weight] = 0
        return 0

    if weight + ws[depth] <= W:
        result = max(dfs(weight, depth - 1), dfs(weight + ws[depth], depth - 1) + vs[depth])
    else:
        result = dfs(weight, depth - 1)
    dp[depth][weight] = result
    return result

print(dfs())

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
ws = [x[0] for x in wv]
vs = [x[1] for x in wv]

dp = [{} for _ in range(100)]
def dfs(weight=0, depth=N - 1):
    if dp[depth].get(weight) is not None:
        return dp[depth][weight]

    if depth == -1:
        return 0

    if weight + ws[depth] <= W:
        result = max(dfs(weight + ws[depth], depth - 1) + vs[depth], dfs(weight, depth - 1))
    else:
        result = dfs(weight, depth - 1)
    dp[depth][weight] = result
    return result

print(dfs())

Submission status: Time Limit Exceeded

Solution code:
N, W = [int(i) for i in input().split()]
w, v = [0]*N, [0]*N
 
for i in range(N):
  w[i], v[i] = [int(_) for _ in input().split()]
  
dp = [[0] * (W+1) for _ in range(N+1)]
# dp[i][j] i番目までの荷物で重さがjを超えないように選んだときの価値の最大値
for i in range(N):
  for j in range(W+1):
    if j < w[i]:# i番目の荷物の重さw[i]がjを超えているので，入れる可能性がない
      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:
N, W = [int(i) for i in input().split()]
w, v = [0]*N, [0]*N
 
for i in range(N):
  w[i], v[i] = [int(_) for _ in input().split()]
  
dp = [[0] * (W+1) for _ in range(N+1)]
# dp[i][j] i番目までの荷物で重さがjを超えないように選んだときの価値の最大値
for i in range(N):
  for j in range(W+1):
    dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    if j + w[i] <= W:
      dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]], dp[i][j] + v[i])
      
print(dp[N][W])

Submission status: Time Limit Exceeded

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

for i in range(N):
  w[i], v[i] = [int(_) for _ in 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())
we=[]
va=[]
for j in range(n):
    w1,v=map(int,input().split())
    we.append(w1)
    va.append(v)
dp=[[ 0 for _ in range(w+1)]for _ in range(n+1)]
for i in range(n+1):
    for j in range(w+1):
        if i==0 or j==0:
            dp[i][j]=0
        else:
            if j>=we[i-1]:
                dp[i][j]=max(va[i-1]+dp[i-1][j-we[i-1]],dp[i-1][j])
            else:
                dp[i][j]=dp[i-1][j]
print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
INF = float('inf')
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(N)]

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

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
dp=[[0 for i in range(k+1)] for j in range(n)]
for i in range(n):
  a,b=map(int,input().split())
  for j in range(k+1):
    if i==0:
      if j>=a:
        dp[i][j]=b
    else:
      if j<a:
        dp[i][j]=dp[i-1][j]
      else:
        dp[i][j]=max(dp[i-1][j],b+dp[i-1][j-a])
# print(*dp,sep="\n")
print(dp[n-1][k])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[0 for _ in range(W+1)] for _ 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 >= w[i-1]:
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]]+v[i-1])
    print(dp[N][W])


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]" 
    v = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = defaultdict(int)

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


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]" 
    v = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

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)]
#l[i][0]が重さ、l[i][1]が価値
#print(n,w,l)

ans = [[0]*(w+1) for i in range(n)]
#print(ans)

for i in range(n):
  for j in range(0,w+1):
    if i == 0 and j >= l[0][0]:
      ans[0][j] = l[0][1]
    elif i > 0:
      new_w = j + l[i][0]
      if new_w <= w:
        ans[i][new_w] = max(ans[i-1][new_w], ans[i-1][j] + l[i][1])
    if ans[i][j] < ans[i-1][j]:
      ans[i][j] = ans[i-1][j]
        
#print(ans)
print(ans[n-1][w])

Submission status: Time Limit Exceeded

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

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


def coin(arr,value,W,n):
    if n<0 or W==0:
        return 0

    elif arr[n]>W:
#        print(1)
        return coin(arr,value,W,n-1)
    elif n==0 and W>0:
#        print(2)
        return coin(arr,value,W-arr[n],n-1)+value[n] 
    else:
#        print(W)
        return max(coin(arr,value,W-arr[n],n-1)+value[n],coin(arr,value,W,n-1))


print(coin(arr,value,W,N-1))