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 knapsack(N, W, items):
    dp = [[0 for _ in range(N+1)] for _ in range(W+1)]
    for w in range(1, W+1):
        row = dp[w]
        for i in range(1, N+1):
            w_i, v_i = items[i-1]
            if w_i > w:
                for k in range(i, N+1):
                    row[k] = row[i-1]
                continue
            else:
                row[i] = max(row[i-1], dp[w-w_i][i-1]+v_i)
    return dp[-1][-1]

N, W = tuple(map(int, input().split()))
items = [tuple(map(int, input().split())) for _ in range(N)]
items = sorted(items, key=lambda x:x[0])
print(knapsack(N, W, items))

Submission status: Time Limit Exceeded

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

#dp[i+1][w]:=i番目までの荷物を積んだ時、wいかになっているときの最大価値
#Aは　重さ、価値の順
dp=[[0 for i in range(W+1)] for j in range(n+1)]

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

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
W=[]
V=[]
for i in range(n):
    a,b=map(int,input().split())
    W.append(a)
    V.append(b)

dp=[0 for i in range(w+1)]
for q in range(n):
    bq=q
    for i in range(w):
        bi=w-i-1
        if bi+W[bq]<=w:
            dp[bi+W[bq]]=max(dp[bi]+V[bq],dp[bi+W[bq]])
    #print(dp)

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

list1=[]

try:
    list1=list(map(int, input().split()))
except:
    quit();

N=list1[0]
W=list1[1]

inp=[]

for _ in range(N):
    try:
        inp.append(list(map(int, input().split())))
    except:
        quit();

inp=np.array(inp)
inp=inp.T
wlist=inp[0]
vlist=inp[1]

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

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

print(int(dp[N][W]))

Submission status: Time Limit Exceeded

Solution code:
# D - Knapsack 1
N,W=map(int,input().split())
w,v=[],[]
for i in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)

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

for i in range(N):
    for j in range(W+1):
        # 選ぶ場合
        if j-w[i]>=0:
            dp[i+1][j]=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())
wv = []
for _ in range(n):
    data = list(map(int,input().split()))
    wv.append(data)

from functools import lru_cache
@lru_cache(maxsize=None)
def solve(i,j):
    if i>=n:
        return 0

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

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

    return val

print(solve(0,w))

Submission status: Time Limit Exceeded

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

dp = [0]*(w+1)

for _ in range(n):
  wei, v = map(int, input().split())
  dp_1 = dp[:]
  for j in range(w + 1):
    if j - wei >= 0:
      dp[j] = dp_1[j-wei] + v if (dp_1[j-wei] + v) > dp_1[j] else dp[j]
  
print(dp[w])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

ab = []
for _ in range(n):
    a, b= (int(x) for x in input().split())
    ab.append([a, b])

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

Submission status: Time Limit Exceeded

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

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

def do_dp():
  for i,thing in enumerate(things):
    dp_1 = dp[i-1]
    for j in range(1, w + 1):      
      dp[i][j] = dp_1[j-thing[0]] + thing[1]  if (j - thing[0]) >= 0 else dp_1[j]
      dp[i][j] = max(dp[i][j], dp_1[j])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

from functools import lru_cache

def resolve():
    N, W = map(int, input().split())    
    w_v = [list(map(int, input().split())) for _ in range(N)]  # [N][0:weight, 1:value]

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

    #print(dp)
 
    @lru_cache(maxsize=None)
    def dfs(w, i):
        if dp[i][w] >= 0:
            return dp[i][w]
        if i >= N:
            res = 0
        elif w < w_v[i][0]:
            res = dfs(w, i+1)
        else:
            res = max(dfs(w - w_v[i][0], i+1) + w_v[i][1], dfs(w, i+1))

        dp[i][w] = res
        return res

    res = dfs(W, 0)
    print(res)
    
    
if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

from functools import lru_cache

def resolve_by_dfs():
    N, W = map(int, input().split())    
    w_v = [list(map(int, input().split())) for _ in range(N)]  # [N][0:weight, 1:value]
 
    @lru_cache(maxsize=None)
    def dfs(w, i):
        if i >= N:
            res = 0
        elif w < w_v[i][0]:
            res = dfs(w, i+1)
        else:
            res = max(dfs(w - w_v[i][0], i+1) + w_v[i][1], dfs(w, i+1))
        return res

    res = dfs(W, 0)
    print(res)
    
if __name__ == "__main__":
    resolve_by_dfs()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

from functools import lru_cache

def resolve():
    N, W = map(int, input().split())    
    w_v = [list(map(int, input().split())) for _ in range(N)]  # [N][0:weight, 1:value]
    
    @lru_cache(maxsize=None)
    def dfs(w, v, i):
        if w > W:
            return 0
        if i >= N:
            return v
        return max(dfs(w + w_v[i][0], v + w_v[i][1], i+1), dfs(w, v, i+1))

    res = dfs(0, 0, 0)
    print(res)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

from functools import lru_cache

def resolve():
    N, W = map(int, input().split())    
    w_v = [list(map(int, input().split())) for _ in range(N)]  # [N][0:weight, 1:value]
 
    dp = [0] * W
    memo = [0] * N 
    
    @lru_cache(maxsize=None)
    def dfs(w, v, i):
        if w > W:
            return 0
        if i >= N:
            return v
        return max(dfs(w + w_v[i][0], v + w_v[i][1], i+1), dfs(w, v, i+1))

    res = dfs(0, 0, 0)
    print(res)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    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-1]-1:
                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]
    print(dp[N][W])
    return


# Generated by 1.1.6 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())
wv = []
for _ in range(N):
  wv += list(map(int, input().split()))
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N):
  for w in range(W+1):  
    if w-wv[2*i] >= 0:
      dp[i+1][w] = max(dp[i+1][w], dp[i][w-wv[2*i]]+wv[2*i+1])
    dp[i+1][w] = max(dp[i+1][w], dp[i][w])
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# Knapsack問題

import numpy as np

# input
N,W = map(int, input().split())
w = np.zeros(N, dtype=int)
v = np.zeros(N, dtype=int)
for i in range(N):
  a,b = map(int ,input().split())
  w[i] = a 
  v[i] = b 

# calc
dp = [[0 for _ in range(W+1)] for _ in range(N+2)]
dp = np.array(dp, dtype=int)
for i in np.arange(N):
   for j in np.arange(W+1):
        if w[i] <= j:
            dp[i+1,j] = max(dp[i, j-w[i]]+v[i], dp[i,j])
        else:
            dp[i+1,j] = dp[i,j]

print(dp[N,W])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# Knapsack問題

import numpy as np

# input
N,W = map(int, input().split())
w = np.zeros(N, dtype=int)
v = np.zeros(N, dtype=int)
for i in range(N):
  a,b = map(int ,input().split())
  w[i] = a 
  v[i] = b 

# calc
dp = [[0 for _ in range(W+1)] for _ in range(N+2)]
dp = np.array(dp, dtype=int)
for i in range(N):
   for j in range(W+1):
        if w[i] <= j:
            dp[i+1,j] = max(dp[i, j-w[i]]+v[i], dp[i,j])
        else:
            dp[i+1,j] = dp[i,j]

print(dp[N,W])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, W = map(int, input().split())
wv = []
for _ in range(N):
  wv += list(map(int, input().split()))
wv = np.array(wv).reshape(N,2)
dp = np.zeros((110, 100100))
for i in range(N):
  for w in range(W+1):
    if w - wv[i,0] >= 0:
      dp[i+1,w] = max(dp[i+1,w], dp[i,(w-wv[i,0])]+wv[i,1])
    dp[i+1,w] = max(dp[i+1,w], dp[i, w])
print(int(dp[N,W]))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# Knapsack問題

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

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
WEIGHTS = list(list(map(int, input().split())) for _ in range(N))
M = len(WEIGHTS)

DP = [[0] * M for _ in range(W + 3)]

for i in range(W+1):
    for j, (weight, value) in enumerate(WEIGHTS):
        if i - weight >= 0:
            DP[i+1][j] = max(x if index != j else 0 for index, x in enumerate(DP[max(i - weight + 1, 0)])) + value

print(max(DP[W + 1]))

Submission status: Time Limit Exceeded

Solution code:
def main(n,w,item):
    #dp[i][sum_w]:i-1番目までの品物から重さsum_wを超えないように
    #選択した場合の価値の最大値
    dp = [[0]*(w+1) for _ in range(n+1)]
    for i in range(n):
        for j in range(w+1):
            #選択する場合
            weight, value = item[i]
            if j+weight <= w:
                dp[i+1][j+weight] = max(dp[i+1][j+weight], dp[i][j]+value)
            #選択しない場合
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    return max(dp[-1])

n,w = map(int, input().split())
item = [list(map(int, input().split())) for _ in range(n)]
print(main(n,w,item))

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

Submission status: Time Limit Exceeded

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

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

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

print (dp[W])

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
WV = []
dp = [[0 for i in range(W+1)]for j in range(N+1)]
for i in range(N):
    WV.append(list(map(int,input().split())))
for i in range(N):
    dp[i+1][0:WV[i][0]] = dp[i][0:WV[i][0]]
    for w in range(WV[i][0],W+1):
        dp[i+1][w] = max(dp[i][w],dp[i][w - WV[i][0]]+WV[i][1])
print(max(max(dp)))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

dp = [[0] * (W + 1) for _ in range(N + 1)]
# dp[i][j](j=0,1,...,W)の値が求まっている状態で、dp[i+1][j]を更新することを考える
for i in range(N):
	for j in range(W + 1):
		# 品物(w[i],v[i])を選ぶとき、j-w[i]>=0に限って、価値v[i]が加算される
		if j - w[i] >= 0:
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i])
		# 品物(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())
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 w in range(W+1):
        if w >= wv[i][0]:
            dp[i+1][w] = max(
                dp[i][w - wv[i][0]] + wv[i][1],
                dp[i][w]
            )
        else:
            dp[i+1][w] = dp[i][w]

print(dp[n][W])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
N, W=map(int, input().split())
WV=[list(map(int, input().split())) for i 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-w] == -1:
            continue
        dp[i] = max(dp[i], dp[i-w] + v)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from itertools import product, permutations, combinations
from bisect import bisect_right,bisect_left
INF = float('inf')
N, W=map(int, input().split())
WV=[list(map(int, input().split())) for i 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-w] == -1:
            continue
        dp[i] = max(dp[i], dp[i-w] + v)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
s = list(map(int, input().split()))
n=s[0]
w=s[1]
dp=[[0]*(w+1) for i in range(n+1)]
weight=[]
value=[]
for i in range(n):
    s = list(map(int, input().split()))
    weight.append(s[0])
    value.append(s[1])

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

# dp[i][w]: i番目の荷物で重さwの状態であるときの最大価値
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

# 配るDPで考える
for nimotsu in range(N):
    # 行取得
    w_weight, w_val = map(int, input().split())
    
    for w in range(W+1):
        # 品物を選ぶとき (上限超えなければ)
        sum_ = w + w_weight
        if sum_ <= W :
            dp[nimotsu+1][sum_] = max(dp[nimotsu+1][sum_], dp[nimotsu][w] + w_val)
            
        # 品物を選ばないとき
        dp[nimotsu+1][w] = max(dp[nimotsu+1][w] ,dp[nimotsu][w])

print(dp[N][W])

Submission status: Time Limit Exceeded

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

# dp[i][w]: i番目の荷物で重さwの状態であるときの最大価値
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

# 配るDPで考える
for nimotsu in range(N):
    # 行取得
    w_weight, w_val = map(int, input().split())
    
    for w in range(W+1):
        # 品物を選ぶとき (上限超えなければ)
        sum_ = w + w_weight
        if sum_ <= W :
            dp[nimotsu+1][sum_] = max(dp[nimotsu+1][sum_], dp[nimotsu][w] + w_val)
            
        # 品物を選ばないとき
        dp[nimotsu+1][w] = max(dp[nimotsu+1][w] ,dp[nimotsu][w])

print(max(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
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=[[-1]*(W+1) for i in range(N+1)]
dp[0][0]=0
for i in range(N):
    for w_sum in range(W+1):
        #品物を入れる場合
        if 0<=w_sum-w[i]<=W and dp[i][w_sum-w[i]]!=-1:
            dp[i+1][w_sum]=max(dp[i+1][w_sum],dp[i][w_sum-w[i]]+v[i])
        #入れない場合
        dp[i+1][w_sum]=max(dp[i+1][w_sum],dp[i][w_sum])
print(max(dp[-1]))
#print(dp)

Submission status: Time Limit Exceeded

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

def dp(f,w):
    global F
    if w < 0:
        return -10**9
    if f == 0:
        if w < F[0][0]:
            return 0
        else:
            return F[0][1]
    return max(dp(f-1,w),dp(f-1,w-F[f][0])+F[f][1])

print(dp(N-1,W))

Submission status: Time Limit Exceeded

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

DP = []
for w,v in F:
    if DP == []:
        DP = [0]*w+[v]*(W-w+1)
    else:
        dp = DP[::]
        for w2 in range(w,W+1):
            dp[w2] = max(DP[w2-w] + v, DP[w2])
        DP = dp
    #print(DP)
print(DP[-1])

Submission status: Time Limit Exceeded

Solution code:
N, WW = map(int, input().split())
W, V = [], []
for _ in range(N):
    _w, _v = list(map(int, input().split()))
    if _w > WW:
        continue
    W.append(_w)
    V.append(_v)

# dp = [[0] * (WW+1) for _ in range(N+1)]
dp = [[0] * (N+1) for _ in range(WW+1)]
for j in range(WW+1):
    # アイテムの数だけ探索する
    for i in range(1, N+1):
        w = W[i-1]
        v = V[i-1]
        if j+w > WW:
            continue
        dp[j+w][i] = max(dp[j+w][i-1], max(dp[j][:i]) + v)

# import numpy as np
# print(np.array(dp))
print(max(dp[WW]))

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

for i in range(N):
    for j in range(w[i]-1,W):
        dp[i][j] = v[i]

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

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
w, v = [0]*(N+1), [0]*(N+1)
for i in range(N):
  w[i+1], v[i+1] = map(int, input().split())
  
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]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(dp[i-1][j-w[i]]+v[i], dp[i-1][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):
  weight, value = map(int, input().split())
  for j in range(w, -1, -1):
    if j == 0 or dp[j] != 0:
      if j+weight <= w:
        dp[j+weight] = max([dp[j+weight], dp[j]+value])

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n, w = (int(x) for x in input().split())
wv = [[0, 0]]
for _ in range(n):
    wv.append([int(x) for x in input().split()])
dp = [[0] * (w + 1) for _ in range(n + 1)]
for i in range(w + 1):
    dp[0][i] = 0
for i in range(1, n + 1):
    for j in range(1, w + 1):
        if j - wv[i][0] >= 0:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wv[i][0]] + wv[i][1])
        else:
            dp[i][j] = dp[i - 1][j]
print(dp[n][w])

Submission status: Time Limit Exceeded

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

N, W = [int(x) for x in input().split()]
wv = []
for _ in range(N):
    wv.append([int(x) for x in input().split()])

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
n,w=map(int,input().split())
#重さをdpにする
#dp=[[0]*n,[0]*w] #n番目の品,重さ。価値が値として入る
#dp=np.zeros((n+1,w+1))
dp=[[0] * (w+1) for i in range(n+1)]
#print(dp)
#print(len(dp[0]))
#print(len(dp[n][w]))
W=[]
V=[]
for i in range(n):
    a,b=map(int,input().split())
    W+=[a]
    V+=[b]

#print(dp[0][0])
#print(W)
for i in range(n):
    #print(i)
    for sum_w in range(w+1):
        #print(sum_w)
        #足した時に価値が上がるケース
        if sum_w>=W[i]:
            dp[i+1][sum_w]=max(dp[i][sum_w],dp[i][sum_w - W[i]] + V[i])
    
        #選ばない時
        else:
            dp[i+1][sum_w]=dp[i][sum_w]

#print(dp)
print(int(dp[n][w]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,w=map(int,input().split())
#重さをdpにする
#dp=[[0]*n,[0]*w] #n番目の品,重さ。価値が値として入る
dp=np.zeros((n+1,w+1))

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

#print(dp[0][0])
#print(W)
for i in range(n):
    #print(i)
    for sum_w in range(w+1):
        #print(sum_w)
        #足した時に価値が上がるケース
        if sum_w>=W[i]:
            dp[i+1][sum_w]=max(dp[i][sum_w],dp[i][sum_w - W[i]] + V[i])
    
        #選ばない時
        else:
            dp[i+1][sum_w]=dp[i][sum_w]

#print(dp)
print(int(dp[n][w]))

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    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+1)]
    for i in range(1,n+1):
        for j in range(w+1):
            if j-l[i-1][0] >= 0:
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-l[i-1][0]]+l[i-1][1])
            else:
                dp[i][j] = dp[i-1][j]
    print(dp[n][w])
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 j in range(W+1):
    if j<w:
      dp[i][j] = dp[i-1][j]
      continue
    dp[i][j] = max(dp[i-1][j-w]+v, dp[i-1][j])
print(max(dp[N-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(N):
  w, v = wv[i]
  for j in range(W+1):
    if j<w:
      dp[i][j] = dp[i-1][j]
      continue
    dp[i][j] = max(dp[i-1][j-w]+v, dp[i-1][j])
print(max(dp[N-1]))

Submission status: Time Limit Exceeded

Solution code:
N, W = list(map(int, input().split()))
WE = []
V = []
for i in range(N):
    w, v = list(map(int, input().split()))
    WE.append(w)
    V.append(v)

MAX_W = 10 ** 5

# DP[i][j]: i以降の品物で重さj以下のときの価値の最大
DP = []
for i in range(N):
    a = [None] * (MAX_W + 1)
    DP.append(a)
DP.append([0] * (MAX_W+1))

for i in range(N-1, -1, -1):
    for j in range(MAX_W+1):
        if i == N:  # i番目の品物はない
            DP[i][j] == 0
        elif j < WE[i]:  # この重さの品物は入れないから無視
            DP[i][j] = DP[i+1][j]
        else:
            DP[i][j] = max(DP[i+1][j], DP[i+1][j-WE[i]]+V[i])

# for i in range(N):
#     print(DP[i][:10])
print(DP[0][W])

Submission status: Time Limit Exceeded

Solution code:
N, W = list(map(int, input().split()))
WE = []
V = []
for i in range(N):
    w, v = list(map(int, input().split()))
    WE.append(w)
    V.append(v)

# DP[i][j]: i以降の品物で重さj以下のときの価値の最大
DP = []
for i in range(N):
    a = [None] * ((10 ** 5)+1)
    DP.append(a)
# DP.append([0] * ((10 ** 5)+1))

# i以降の荷物を使い、重さj以下で価値を最大にする
def search(i, j):
    if i == N:
        return 0

    if DP[i][j] is not None:
        return DP[i][j]

    if j < WE[i]:
        r = search(i+1, j)
        DP[i][j] = r
        return r

    r = max(search(i+1, j), search(i+1, j-WE[i])+V[i])
    DP[i][j] = r
    return r

search(0, W)

# for i in range(N):
#     print(DP[i][:10])

print(DP[0][W])

Submission status: Time Limit Exceeded

Solution code:
(n, W) = map(int,input().split())
pre = [0] * (W+1)
cur = [0] * (W+1)
#a = [[0] * (W+1) for i in range(n)]
for i in range(0, n):
  (w, v) = map(int,input().split())
  for j in range(w, W + 1):
    cur[j] = max(pre[j], pre[j-w] + v)
  pre = list(cur)
print(cur[W])

Submission status: Time Limit Exceeded

Solution code:
(n, W) = map(int,input().split())
pre = [0] * (W+1)
cur = [0] * (W+1)
#a = [[0] * (W+1) for i in range(n)]
for i in range(0, n):
  (w, v) = map(int,input().split())
  for j in range(w, W + 1):
    cur[j] = max(pre[j], pre[j-w] + v)
  pre = cur[:]
print(cur[W])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,W = map(int,raw_input().split())
mat = []
for _ in range(n):
    mat.append(map(int,raw_input().split()))
    
dp =[[-float("inf") for _ in range(W+1)] for _ in range(n+1)]

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

Submission status: Time Limit Exceeded

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

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

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

dp = [[0] * (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 items[i-1][0] <= j:
            dp[i][j] = max(dp[i][j], dp[i-1][j-items[i-1][0]] + items[i-1][1])

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
def solve(n, w, WV):
    dp = [[0] * (w + 1) for _ in range(n)]
    for w_limit in range(WV[0][0], w + 1):
        dp[0][w_limit] = WV[0][1]
    for i in range(1, n):
        for w_limit in range(1, w + 1):
            dw, dv = WV[i]
            if dw > w_limit:
                dp[i][w_limit] = dp[i - 1][w_limit]
            else:
                dp[i][w_limit] = max(dp[i - 1][w_limit], dp[i - 1][w_limit - dw] + dv)
    return dp[n - 1][w]

_n, _w = map(int, input().split())
_WV = [list(map(int, input().split())) for _ in range(_n)]
print(solve(_n, _w, _WV))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N,W = [int(i) for i in input().split()]
weight = [0] * N
value= [0] * N
for i in range(N) :
    w,v = [int(i) for i in input().split()]
    value[i] = v
    weight[i] = w
dp = [[0] * (W+1) for _ in range(N+1)]
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:
N, W = map(int, input().split())
values = [0 for i in range(W)]
for i in range(N):
#  print(values)
  w, v = map(int, input().split())
  values = values[:w-1] + [max(values[j], v + values[max(0, j-w)]) for j in range(w-1, W)]

print(values[-1])

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int, input().split())
import numpy as np
dp=np.zeros((N+1,W+1),dtype=int)
w=[]
v=[]
for i in range(N):
  a,b=map(int, input().split())
  w.append(a)
  v.append(b)
for weight in range(1,W+1):
  for n in range(N):
    if weight-w[n]>=0:
      dp[n+1][weight]=max(dp[n][weight-w[n]]+v[n],dp[n][weight])
    else:
      dp[n+1][weight]=dp[n][weight]
print(max(dp[:,W]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, W = map(int, input().split())
w, v = [], []
for _ in range(n):
    _w, _v = map(int, input().split())
    w.append(_w)
    v.append(_v)

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

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

print(dp[n][W])