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:
import sys
 
def main():
  N, W = map(int, input().split())
  w = [0]*N
  v = [0]*N
  for i in range(N):
          w[i], v[i] = map(int, sys.stdin.readline().split())
 
  #WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]
 
 
  dp = [[0]*(N+1) for j in range(W+1)]
 
  for i in range(1, W+1):
          for j in range(1, N+1):
                  if i - w[j-1]>=0:
                  #if i - WV[j-1][0]>=0:
                          dp[i][j] = max(dp[i-w[j-1]][j-1]+v[j-1], dp[i][j-1])
                          #dp[i][j] = max(dp[i-WV[j-1][0]][j-1]+WV[j-1][1], dp[i][j-1])
                  else:
                          dp[i][j] = dp[i][j-1]
 
  print(dp[W][N])
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

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

#WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]


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

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

print(dp[W][N])

Submission status: Time Limit Exceeded

Solution code:
import sys

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

WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N,W=map(int,input().split())
dp=[[0]*(W+1) for i in range(N+1)]
for i in range(N):
  wi,vi=map(int,input().split())
  for w in range(W+1):
    if w>=wi:
      dp[i+1][w]=max(dp[i][w],dp[i][w-wi]+vi)
    else:
      dp[i+1][w]=dp[i][w]
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
dp = [float('inf') for _ in range(10**5+10)]
w = []
v = []

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

for i in range(N):
    wi,vi = map(int,input().split())

    w.append(wi)
    v.append(vi)

#i番目の荷物を入れるときに、capacity以下になるようにする
def dfs(i, capacity):
    res = 0

    if i == N:
        # 荷物がない
        res = 0
    elif w[i] > capacity:
        # 荷物が入らないから、そのまま次に進む
        dfs(i+1, capacity)
    else:
        # 荷物を入れないとき、荷物を入れるとき。入れるときは価値vが加算される。
        res = max(dfs(i+1,capacity), dfs(i+1, capacity - w[i]) + v[i])

    return res

print(dfs(0,W))

Submission status: Time Limit Exceeded

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

    print(dp[N][W])

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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


dp = [[0 for _ in range(100001)] for _ in range(101)]

for i in range(N):
    for sumW in range(limitW + 1):
        score = dp[i][sumW]
        if W[i] <= sumW:
            score = max(score, dp[i][sumW-W[i]] + V[i])
        dp[i+1][sumW] = score
print(dp[N][limitW])

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

for j in range(w+1):
    if (j-wv[0][0])>=0:
        dp[0][j] = wv[0][1]
    else:
        dp[0][j] = 0

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

ans = dp[n-1][w]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
weight=[0]*N
value=[0]*N
for i in range(N):
    weight[i],value[i]=map(int,input().split())
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]):
            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:
import sys
import numpy as np

input = sys.stdin.readline

# N 品物の数、 W 合計の重さ
n, w = map(int, input().split())

# (W V) W : 品物の重さ V：品物の価値
lst = [list(map(int, input().split())) for ii in range(n)]

# 価値 v を最大にするので、0に初期化
# １次元は品物（インデックス0には ALL0）、２次元は重さの合計
dp = np.zeros([n+1, w+1])

def retmax(a, b):
    if a > b:
        return a
    return b

for i, ln in enumerate(lst):
    # 品物の数分
    for j in range(w+1):
        # 重みの数まで
        # 選ばない。１つ前からセットする。
        dp[i+1, j] = retmax(dp[i+1, j], dp[i, j])
        if j >= ln[0]:
            # 品物を選べる
            dp[i+1, j] = retmax(dp[i+1, j], dp[i, j-ln[0]]+ln[1])
print(int(dp[n, w]))

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

import numpy as np

#import numpy as np
#n, w = map(int, input().split())
#wv = [tuple(map(int, input().split())) for _ in range(n)]
n, w = map(int,readline().split())
m = map(int,read().split())
wv = zip(m,m)

dp = np.zeros((n+1, w+1), np.int64)
#dp = [[0] * (w+1) for _ in range(n+1)]
#print(n, w)
#print(dp)
#for i,  in range(n):
#i = 0
for i, (wi, vi) in enumerate(wv):
    #print(i, wi, vi)
    for sum_w in range(w+1):
        #wi = wv[i][0]
        #vi = wv[i][1]
        if sum_w - wi >= 0:
            dp[i+1][sum_w] = dp[i][sum_w - wi] + vi
        dp[i+1][sum_w] = max(dp[i][sum_w], dp[i+1][sum_w])
    #i += 1

print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(n)]

#dp = np.zeros((n+1, w+1), np.int64)
dp = [[0] * (w+1) for _ in range(n+1)]

for i in range(n):
    for sum_w in range(w+1):
        wi = wv[i][0]
        vi = wv[i][1]
        if sum_w - wi >= 0:
            #dp[i+1][sum_w] = max(dp[i][sum_w - wi] + vi, dp[i+1][sum_w])
            dp[i+1][sum_w] = dp[i][sum_w - wi] + vi
        dp[i+1][sum_w] = max(dp[i][sum_w], dp[i+1][sum_w])

print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(n)]

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

for i in range(n):
    for sum_w in range(w+1):
        wi = wv[i][0]
        vi = wv[i][1]
        if sum_w - wi >= 0:
            #dp[i+1][sum_w] = max(dp[i][sum_w - wi] + vi, dp[i+1][sum_w])
            dp[i+1][sum_w] = dp[i][sum_w - wi] + vi
        dp[i+1][sum_w] = max(dp[i][sum_w], dp[i+1][sum_w])

print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
#N,W = map(int, input().split())
S=list(map(int,input().split()))
N=S[0]
W=S[1]

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

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

Submission status: Time Limit Exceeded

Solution code:
import copy
N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
f = [0 for m in range(M + 1)]
for n in range(N):
    f_ = copy.copy(f)
    for m in range(M + 1):
        if m >= W[n]:
            f_[m] = max(f[m], f[m - W[n]] + V[n])
    f = f_
print(f[M])

Submission status: Time Limit Exceeded

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


def f(n, m):
    if n == 0 or m <= 0:
        return 0
    elif m < W[n - 1]:
        return f(n - 1, m)
    else:
        return max(f(n - 1, m), f(n - 1, m - W[n - 1]) + V[n - 1])


print(f(N, M))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

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

    # dp[i][j]: 0〜(i-1)まで使ったときの重さjのときの価値の最大値
    dp = [[0]*(W+1) for i in range(N+1)]

    for i in range(1, N+1):
        for w in range(0, W+1):
            # i番目を入れられる場合
            if w - wv[i-1][0] >= 0:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-wv[i-1][0]] + wv[i-1][1])
            else:
                dp[i][w] = dp[i-1][w]

    print(max(dp[N]))

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int,input().split())
wv = [tuple(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(1, w+1):
        if wv[i-1][0] <= j:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-wv[i-1][0]] + wv[i-1][1])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
Wlist=[]
Vlist=[]
for i in range(N):
  w,v=map(int,input().split())
  Wlist+=[w]
  Vlist+=[v]
dp=[[0 for p in range(W+1)] for i in range(N)]
dp[0][Wlist[0]]=Vlist[0]
for i in range(1,N):
  wi=Wlist[i]
  for j in range(W):
    if j+wi<=W:
      dp[i][j+wi]=max(dp[i-1][j]+Vlist[i],dp[i][j+wi])
    dp[i][j]=max(dp[i-1][j],dp[i][j])
print(max(dp[N-1]))

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
Wlist=[]
Vlist=[]
for i in range(N):
  w,v=map(int,input().split())
  Wlist+=[w]
  Vlist+=[v]
dp=[[0 for p in range(W)] for i in range(N)]
for i in range(N):
  wi=Wlist[i]
  if i==0:
    dp[0][Wlist[0]-1]=Vlist[0]
  else:
    for j in range(W):
      if j+wi<W:
        if j==0:
          dp[i][wi-1]=max(Vlist[i],dp[i][wi-1])
        if dp[i-1][j]!=0:
          dp[i][j+wi]=max(dp[i-1][j]+Vlist[i],dp[i][j+wi])
      dp[i][j]=max(dp[i-1][j],dp[i][j])
print(max(dp[N-1]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Feb 22 22:30:30 2020

@author: matha
"""

#global


def dp(pos, cw):
    if pos>= N or cw > W:
        return 0;
    temp = mem.get((pos, cw), None)
    if temp:
        return temp
    
    w = rec[pos][0]
    
    v1 = 0
    v2 = 0
    
    if(cw+w <= W):
        v1 = rec[pos][1]
        v1 += dp(pos+1, cw + w)
    
    v2 = dp(pos+1, cw)
    
    if(v1>v2):
        mem[(pos, cw)] = v1
        return v1
    else:
        mem[(pos, cw)] = v2
        return v2

rec = []
mem = {}

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

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

print(dp(0, 0))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def knapsack(n,c):
  if dp[n][c]!=-1:
    return dp[n][c]
  
  if n < 0 :
    return 0
  if w[n] > c:
    dp[n][c] = knapsack(n-1,c)
    return dp[n][c]
  else:
    opt1 = v[n] + knapsack(n-1,c-w[n])
    opt2 = knapsack(n-1,c)
    dp[n][c] = max(opt1,opt2)
    return dp[n][c]

n,c = map(int,input().split())
w =[];v=[]
size = n+1
dp = np.full((size,c+1),int(-1))
#print(dp)
for _ in range(n):
  wi , vi= map(int,input().split())
  w.append(wi)
  v.append(vi)

result = knapsack(n-1,c)
print(int(result))

Submission status: Time Limit Exceeded

Solution code:

def knapsack(n,c,w,v,dp):
  if dp[n][c]!=None:
    return dp[n][c]
  
  if n == 0 or c == 0:
    dp[n][c]=0
    return dp[n][c]
  if w[n] > c:
    dp[n][c] = knapsack(n-1,c,w,v,dp)
    return dp[n][c]
  else:
    opt1 = v[n] + knapsack(n-1,c-w[n],w,v,dp)
    opt2 = knapsack(n-1,c,w,v,dp)
    dp[n][c] = max(opt1,opt2)
    return dp[n][c]

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

w = [-1]; v = [-1]
size = n+1
dp = [ [None for i in range(c+1)] for j in range(n+1)]
for _ in range(n):
  wi , vi= map(int,input().split())
  w.append(wi)
  v.append(vi)

result = knapsack(n,c,w,v,dp)
print(result)

Submission status: Time Limit Exceeded

Solution code:

def knapsack(n,c,w,v,dp):
  if dp[n][c]!=None:
    return dp[n][c]
  
  if n == 0 or c == 0:
    return 0
  if w[n] > c:
    dp[n][c] = knapsack(n-1,c,w,v,dp)
    return dp[n][c]
  else:
    opt1 = v[n] + knapsack(n-1,c-w[n],w,v,dp)
    opt2 = knapsack(n-1,c,w,v,dp)
    dp[n][c] = max(opt1,opt2)
    return dp[n][c]

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

w = [-1]; v = [-1]
size = n+1
dp = [ [None for i in range(c+1)] for j in range(n+1)]
for _ in range(n):
  wi , vi= map(int,input().split())
  w.append(wi)
  v.append(vi)

result = knapsack(n,c,w,v,dp)
print(result)

Submission status: Time Limit Exceeded

Solution code:

def knapsack(n,c,w,v):
  if n == 0 or c == 0:
    return n
  if w[n] > c:
    return knapsack(n-1,c,w,v)
  else:
    opt1 = v[n] + knapsack(n-1,c-w[n],w,v)
    opt2 = knapsack(n-1,c,w,v)
    return max(opt1,opt2)


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

w = [-1]; v = [-1]

for _ in range(n):
  wi , vi= map(int,input().split())
  w.append(wi)
  v.append(vi)

result = knapsack(n,c,w,v)
print(result)

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
weights, values = [], []

for _ in range(N):
    x, y = map(int, input().split())
    weights.append(x)
    values.append(y)

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


def dp_rec(item, w):

    if dp[item][w] > -float('inf'):
        return dp[item][w]
    if item == N:
        return 0
    if w-weights[item] >= 0:
        res = max(dp_rec(item+1, w-weights[item]) + values[item], dp_rec(item+1, w))
    else:
        res = dp_rec(item+1, w)

    dp[item][w] = res
    return res


dp_rec(0, W)
print(dp[0][W])

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):
    wi, vi = map(int, input().split())

    for wj in range(w, wi - 1, -1):
        nv = dp[wj - wi] + vi
        if dp[wj] < nv:
            dp[wj] = nv

print(max(dp))

Submission status: Time Limit Exceeded

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

dp = [0] * (w + 1)

for _ in range(n):
    wi, vi = map(int, input().split())

    for wj in range(w, wi - 1, -1):
        nv = dp[wj - wi] + vi
        if dp[wj] < nv:
            dp[wj] = nv

print(max(dp))

Submission status: Time Limit Exceeded

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

dp=[[0]*(w+1) for _ in range(n+1)]
#dp:=i番目以降の商品から重さの総和がj以下となるように選んだ時の価値の総和の最大

#初期条件 dpｗｐ0で作ってるのでいらない
for j in range(w):dp[n][j] = 0

#漸化式
#dp[i][j] = dp[i+1][j] (j < w[i])
#           max(dp[i+1][j] , dp[i+1][j-w[i]]+v[i]) (otherwise)
for i in reversed(range(n)):
    for  j in range(w+1):
        if j < l[i][0]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j] , dp[i+1][j - l[i][0]] + l[i][1] )

print(dp[0][w])

Submission status: Time Limit Exceeded

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

dp=[[0]*(w+1) for _ in range(n+1)]
#dpテーブル

def rec(i,j):#再帰　i:何個目の商品を見てるか　j:残りのナップサックの容量
    if dp[i][j] != 0:#メモされてればそれを返す
        return dp[i][j]
    res = 0
    if i == n:#すべての商品を調べ終えた
        return res
    else:
        if j - l[i][0] < 0:#容量が足りない
            ans = rec(i+1,j)
        else:
            #品物を入れるときと入れないとき両方調べる
            ans = max(rec(i+1,j),rec(i+1,j-l[i][0]) + l[i][1])
    dp[i][j] = ans#メモして返す
    return dp[i][j]

print(rec(0,w))

Submission status: Time Limit Exceeded

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

lstw, lstv = [], []
for i in range(n):
    w_,v_ = map(int,input().split())
    lstw.append(w_)
    lstv.append(v_)

#dp[i+1][j] := i番目までの商品で重さの総和がj以下の最大価値
dp = [[0 for i in range(w+1)] for _ in range(n+1)]

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

Submission status: Time Limit Exceeded

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

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

print(max(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int,input().split())
wv = [[0]*2 for _ in range(n)]
for i in range(n):
    wv[i] = list(map(int,input().split())) 
inf=float('inf')
dp = [[-inf]*(w+1) for _ in range(n+1)]
for j in range(w+1):
    dp[0][j]=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(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
"""memo
    numpyでやるときは配列を一気に更新するが(numpy使いたくないのでやらない)，
    このやり方は後ろの方から更新することで後の更新に影響を与えない(考え方すごい)．
    (参考#9889377)
"""

import sys
input = sys.stdin.readline

def main():
    #1:初期化
    N,W = map(int,input().split())
    dp = [0]*(W+1)

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

    #3:dp実行部(貰うDP)
    for i in range(N):
        w, v = map(int,input().split())
        for i in range(W, w-1, -1):
            if (dp[i] < (dp[i-w] + v)):
                dp[i] = dp[i-w] + v
        #print(dp,sep="\n")

    #4:出力
    print(max(dp))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:


import sys
input = sys.stdin.readline

import numpy as np

def main():
    #1:初期化
    N,W = map(int,input().split())
    wv = []
    for _ in range(N):
        wv.append(list(map(int,input().split())))
    dp = np.zeros((N+1,W+1), dtype=np.int64)
    #dp = [[0]*(W+1) for i in range(N+1)]

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

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

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import numpy as np

def main():
    #1:初期化
    N,W = map(int,input().split())
    wv = []
    for _ in range(N):
        wv.append(list(map(int,input().split())))
    dp = np.zeros((N+1,W+1), dtype=int)
    #dp2 = [[0]*(W+1) for i in range(N+1)]

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

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

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque
import copy

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

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

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

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
item = []
for i in range(N):
    item.append(tuple(map(int, input().split())))
    
def f(N, W, item):
	dp = [[0]*(W+1) for i in range(N+1)]
	for i in range(1, N+1):
		for j in range(1, W+1):
			w = j - item[i-1][0]
			dp[i][j] = max((dp[i-1][w]+item[i-1][1])*(w>=0), dp[i-1][j])
	return dp[N][W]

print(f(N, W, item))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

#i番目までを使ってjの重さで入れたときの価値の最大値を記録する
dp = np.zeros((N+1,W+1))
for j in range(1,W+1):
    for i in range(1,N+1):
        if j < wv[i-1][0]:
            dp[i,j] = dp[i-1,j]
        else:
            dp[i,j] = max(dp[i-1,j-wv[i-1][0]] + wv[i-1][1], dp[i-1,j])
print(int(dp[-1][-1]))

Submission status: Time Limit Exceeded

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

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

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

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

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  num,capacity=map(int,input().split())
  DP=[-1]*(capacity+1)
  DP[0]=0
  for _ in range(num):
    weight,value=map(int,input().split())
    left=capacity-weight
    DP[weight:]=[max(DP[i]+value,DP[i+weight]) for i in range(left,-1,-1)][::-1]
  print(max(DP))
      
if __name__=="__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  from collections import deque
  num,capacity=map(int,input().split())
  DP=[-1]*(capacity+1)
  DP[0]=0
  for _ in range(num):
    weight,value=map(int,input().split())
    left=capacity-weight
    for i in range(left,-1,-1):
      if DP[i]<0:
        continue
      DP[i+weight]=max(DP[i]+value,DP[i+weight])
  print(max(DP))
      
if __name__=="__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  from collections import deque
  num,capacity=map(int,input().split())
  items=deque([list(map(int,sys.stdin.readline().split())) for _ in range(num)])
  DP=[-1]*(capacity+1)
  DP[0]=0
  while(items):
    item=items.popleft()
    weight=item[0]
    value=item[1]
    left=capacity-weight
    for i in range(left,-1,-1):
      if DP[i]<0:
        continue
      DP[i+weight]=max(DP[i]+value,DP[i+weight])
  print(max(DP))
      
if __name__=="__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  num,capacity=map(int,input().split())
  items=tuple([list(map(int,sys.stdin.readline().split())) for _ in range(num)])
  DP=[-1]*(capacity+1)
  DP[0]=0
  for item in items:
    weight=item[0]
    value=item[1]
    left=capacity-weight
    for i in range(left,-1,-1):
      if DP[i]<0:
        continue
      DP[i+weight]=max(DP[i]+value,DP[i+weight])
  print(max(DP))
      
if __name__=="__main__":
  main()

Submission status: Time Limit Exceeded

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

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

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

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

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  
  n,w=map(int,input().split())
  item=[[0,0]]+[list(map(int,input().split())) for _ in range(n)]
  DP=[[0]*(w+1) for _ in range(n+1)]
  for i in range(n+1):
    weight=item[i][0]
    value=item[i][1]
    for j in range(w+1):
      if j<weight:
        DP[i][j]=DP[i-1][j]
      else:
        DP[i][j]=max(DP[i-1][j],DP[i-1][j-weight]+value)
        
  print(DP[n][w])
      
if __name__=="__main__":
  main()

Submission status: Time Limit Exceeded

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

# def main():
#     global n,w,v,dp
#     n = int(input())
#     w,v = [0]*n,[0]*n
#     for i in range(n):
#         w[i],v[i] = map(int,input().split())
#     W = int(input())
#     dp = [[-1]*(W+1) for _ in range(n+1)]
#     print(rec(0,W))

# DP
def main():
    global n,w,v,dp
    n,W = map(int,input().split())
    w,v = [0]*(n),[0]*(n)
    for i in range(n):
        w[i],v[i] = map(int,input().split())
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,W+1):
            if j < w[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])
    print(dp[n][W])


if __name__ == '__main__':
    main()

"""
in
4 5
2 3
1 2
3 4
2 2

out
7
"""

Submission status: Time Limit Exceeded

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

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

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

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

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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])                           
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:
            tmp = row[i-1]
            row[i:-1] = [tmp for _ in range(i, N+1)]
            break
        else:
            row[i] = max(row[i-1], dp[w-w_i][i-1]+v_i)
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
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])                           
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:
            tmp = row[i-1]
            row[i:-1] = [tmp for _ in range(i, N+1)]
            continue
        else:
            row[i] = max(row[i-1], dp[w-w_i][i-1]+v_i)
print(dp[-1][-1])