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:
# DP
def main():
    from builtins import input, int, map, max, min, range

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

    dp = [-1] * (W + 1)
    dp[0] = 0
    max_w = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for j in range(min(max_w, W - w), -1, -1):
            dpj = dp[j]
            if dpj != -1:
                jw = j + w
                if dpj + v > dp[jw]:
                    dp[jw] = dpj + v
                if jw > max_w:
                    max_w = jw
    print(max(dp))


main()

Submission status: Time Limit Exceeded

Solution code:
# DP
def main():
    from builtins import max

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

    dp = [-1] * (W + 1)
    dp[0] = 0
    max_w = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for j in range(min(max_w, W - w), -1, -1):
            dpj = dp[j]
            if dpj != -1:
                jw = j + w
                if dpj + v > dp[jw]:
                    dp[jw] = dpj + v
                if jw > max_w:
                    max_w = jw
    print(max(dp))


main()

Submission status: Time Limit Exceeded

Solution code:
# DP
def main():
    from builtins import max

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

    dp = [-1] * (W + 1)
    dp[0] = 0
    max_w = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for j in range(min(max_w, W - w), -1, -1):
            dpj = dp[j]
            if dpj != -1:
                jw = j + w
                dp[jw] = max(dp[jw], dpj + v)
                max_w = max(max_w, jw)
    print(max(dp))


main()

Submission status: Time Limit Exceeded

Solution code:
# DP
def main():
    from builtins import max

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

    dp = [-1] * (W + 1)
    dp[0] = 0
    max_w = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for j in range(min(max_w, W - w), -1, -1):
            dpj = dp[j]
            if dpj != -1:
                jw = j + w
                dp[jw] = max(dp[jw], dpj + v)
            max_w = max(max_w, jw)
    print(max(dp))


main()

Submission status: Time Limit Exceeded

Solution code:
# DP
def main():
    from builtins import max

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

    dp = [-1] * (W + 1)
    dp[0] = 0
    max_w = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for j in range(min(max_w, W - w), -1, -1):
            if dp[j] != -1:
                dp[j + w] = max(dp[j + w], dp[j] + v)
            max_w = max(max_w, j + w)
    print(max(dp))


main()

Submission status: Time Limit Exceeded

Solution code:
# DP
def main():
    N, W = map(int, input().split())

    dp = [-1] * (W + 1)
    dp[0] = 0
    max_w = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for j in range(min(max_w, W - w), -1, -1):
            if dp[j] != -1:
                dp[j + w] = max(dp[j + w], dp[j] + v)
            max_w = max(max_w, j + w)
    print(max(dp))


main()

Submission status: Time Limit Exceeded

Solution code:
# DP
def main():
    N, W = map(int, input().split())

    dp = [-1] * (W + 1)
    dp[0] = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for j in range(W - w, -1, -1):
            if dp[j] != -1:
                dp[j + w] = max(dp[j + w], dp[j] + v)
    print(max(dp))


main()

Submission status: Time Limit Exceeded

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

dp = [-1] * (W + 1)
dp[0] = 0
max_w = 0
for i in range(N):
  w, v = map(int, input().split())
  for j in range(min(max_w, W - w), -1, -1):
    if dp[j] != -1:
      t = j + w
      dp[t] = max(dp[t], dp[j] + v)
      if t > max_w:
        max_w = t
print(max(dp))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
n, W = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dp = [[0 for _ in range(W+1)] for _ in range(n)]
for w in range(W+1):
    if w>=L[0][0]:
        dp[0][w] = L[0][1]

#print(dp)
for i in range(1, n):
    for w in range(W+1):
        if w <L[i][0]: #そもそも加えられないとき
            dp[i][w] = dp[i-1][w] #前回の状態を代入。
        else: #加えようとしたら入るとき
            dp[i][w] = max(dp[i-1][w-L[i][0]] + L[i][1], dp[i-1][w]) #max(加えた時の価値, 前回の状態)
            
#print(dp)
print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N , W = map(int , input().split())
weight = []
value = []
for _ in range(N):
    w , v = map(int , input().split())
    weight.append(w)
    value.append(v)
 
def knapsack():
    dp = [[-1] * (W + 1) for _ in range(N + 1)]
    def solve(i,w):
        if dp[i][w] != -1:
            return dp[i][w]
        if N == i:
            ret_val = 0
        elif w - weight[i] < 0:
            ret_val = solve(i + 1,w)
        else:
            ret_val = max(solve(i + 1, w), solve(i + 1,w - weight[i]) + value[i])
        dp[i][w] = ret_val
        return dp[i][w]
    solve(0,W)
    #print(dp)
    return max(dp[0])
 
if __name__ == "__main__":
    print(knapsack())

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
weight = []
value = []
for _ in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)
def knapsack():
    dp = [[-1] * (W + 1) for _ in range(N + 1)]

    def solve(i, w):
        if dp[i][w] != -1:
            return dp[i][w]
        if N == i:
            ret_val = 0
        elif w - weight[i] < 0:
            ret_val = solve(i + 1, w)
        else:
            ret_val = max(solve(i + 1, w), solve(i + 1, w - weight[i]) + value[i])
        dp[i][w] = ret_val
        return dp[i][w]
    return solve(0, W)
if __name__ == "__main__":
    print(knapsack())

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
N, W = map(int, input().split())
weight = []
value = []
for _ in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)


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

    def solve(i, w):
        if dp[i][w] != -1:
            return dp[i][w]
        if N == i:
            dp[i][w] = 0
        elif w - weight[i] < 0:
            dp[i][w] = solve(i + 1, w)
        else:
            dp[i][w] = max(solve(i + 1, w), solve(i + 1, w - weight[i]) + value[i])
        #dp[i][w] = ret_val
        return dp[i][w]

    solve(0, W)
    # print(dp)
    return max(dp[0])


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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N , W = map(int , input().split())
weight = []
value = []
for _ in range(N):
    w , v = map(int , input().split())
    weight.append(w)
    value.append(v)

def knapsack():
    dp = [[-1] * (W + 1) for _ in range(N + 1)]
    def solve(i,w):
        if dp[i][w] != -1:
            return dp[i][w]
        if N == i:
            ret_val = 0
        elif w - weight[i] < 0:
            ret_val = solve(i + 1,w)
        else:
            ret_val = max(solve(i + 1, w), solve(i + 1,w - weight[i]) + value[i])
        dp[i][w] = ret_val
        return ret_val
    ans = solve(0,W)
    #print(dp)
    return ans

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N , W = map(int , input().split())
weight = []
value = []
for _ in range(N):
    w , v = map(int , input().split())
    weight.append(w)
    value.append(v)

def knapsack():
    dp = [[-1] * (W + 1) for _ in range(N + 1)]
    def solve(i,w):
        if dp[i][w] != -1:
            return dp[i][w]
        if N == i:
            ret_val = 0
        elif w - weight[i] < 0:
            ret_val = solve(i + 1,w)
        else:
            ret_val = max(solve(i + 1, w), solve(i + 1,w - weight[i]) + value[i])
        dp[i][w] = ret_val
        return dp[i][w]
    solve(0,W)
    #print(dp)
    return max(dp[0])

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

Submission status: Time Limit Exceeded

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

def knapsack():
    dp = [[-1] * (W + 1) for _ in range(N + 1)]
    def solve(i,w):
        if dp[i][w] != -1:
            return dp[i][w]
        if N == i:
            ret_val = 0
        elif w - weight[i] < 0:
            ret_val = solve(i + 1,w)
        else:
            ret_val = max(solve(i + 1, w), solve(i + 1,w - weight[i]) + value[i])
        dp[i][w] = ret_val
        return dp[i][w]
    solve(0,W)
    #print(dp)
    return max(dp[0])

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

Submission status: Time Limit Exceeded

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

def knapsack():
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    def solve(i,w):
        if N == i:
            ret_val = 0
        elif w - weight[i] < 0:
            ret_val = solve(i + 1,w)
        else:
            ret_val = max(solve(i + 1, w), solve(i + 1,w - weight[i]) + value[i])
        dp[i][w] = ret_val
        return dp[i][w]
    solve(0,W)
    #print(dp)
    return max(dp[0])

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

Submission status: Time Limit Exceeded

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

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

print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
import os, sys
from io import IOBase, BytesIO
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None
 
    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
 
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()
 
    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')
 
# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'
n,w=map(int,input().split())
val=[]
wt=[]
for i in range(n):
	ww,vv=map(int,input().split())
	val.append(vv)
	wt.append(ww)
k=[[0 for x in range(w+1)] for x in range(n+1)] 
  

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, W = list(map(int, input().split()))
WV = []
for _ in range(N):
    WV.append(list(map(int, input().split())))

DP = [[0] * (W+1)]
for n in range(N):
    DP.append([0]*(W+1))


for n in range(N):
    for w in range(W+1):
        if w < WV[n][0]:
            DP[n+1][w] = DP[n][w]
        else:
            DP[n+1][w] = max(DP[n][w-WV[n][0]]+WV[n][1], DP[n][w])

print(DP[N][W])

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int,input().split())
li = []
while True:
    try:
        li.append(list(map(int,input().split())))
    except:
        break

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-li[i-1][0]>=0):
            # 品物がひとつ前で重さは同じ所の価値と品物がひとつ前で重さが加える価値を持し品物の重さ分引いたときの価値にひとつ前の品物の価値を加えたもの
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-li[i-1][0]]+li[i-1][1])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
N,W = list(map(int,input().split()))
wv = [list(map(int,input().split())) for i in range(N)]
w = [0]+[wv[i][0] for i in range(N)]
v = [0]+[wv[i][1] for i in range(N)]
V = sum(v)

dp = [[float('INF') for i in range(V+1)] for i in range(N+1)]
dp[0][0] = 0

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

ans = V
while dp[N][ans] > W:
    ans -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, deque

input = sys.stdin.readline

def chmax(a, b):
    if a > b:
        return a
    else:
        return b

def main():
    N, W = map(int, input().split())
    f_inf = float('inf')
    # DP テーブルを初期化　(最小化問題なので INF に初期化)
    MAX_N = 110000
    dp = [0] * (W + 1)


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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, deque

input = sys.stdin.readline

def chmax(a, b):
    if a > b:
        return a
    else:
        return b

def main():
    N, W = map(int, input().split())
    f_inf = float('inf')
    # DP テーブルを初期化　(最小化問題なので INF に初期化)
    MAX_N = 110000
    dp = [0] * (W + 1)


    for _ in range(N):
        w, v = map(int, input().split())
        for sum_w in range(W, w-1, -1):
            if sum_w - w >= 0:
                dp[sum_w] = chmax(dp[sum_w], dp[sum_w - w] + v)
    print(dp[-1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, deque

input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    f_inf = float('inf')
    # DP テーブルを初期化　(最小化問題なので INF に初期化)
    MAX_N = 110000
    dp = [0] * (W + 1)


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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, W = (int(n) for n in input().split())
w, v = [], []
for _ in range(N):
    w_, v_ = (int(n) for n in input().split())
    w.append(w_)
    v.append(v_)

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
dp = [-1] * (w + 1)
dp[w] = 0
for i in range(n):
    input_w, input_v = map(int, input().split())
    for i in range(input_w, w + 1):
        if dp[i] == -1:
            continue
        if dp[i - input_w] < dp[i] + input_v:
            dp[i - input_w] = dp[i] + input_v
print(max(dp))

Submission status: Time Limit Exceeded

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

# DP用の空行列
dp = [[0 for i in range(W+1)] for j in range(N+1)]

# 「1番荷物(v[0])」......「N番荷物(v[N-1])」から何番目まで使うかの場合分け
# 仮に重量制限が「0」「1」......「W」だった場合の場合分け
for i in range(N):
    for j in range(W+1):
        if w[i] > j: # もしi番目の重さが重量制限を超えている場合
            dp[i][j] = dp[i-1][j]
        else: # その他の重量制限の残り「j-w[i]」を重量制限としてdpから引用
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])

print(max(max(dp)))

Submission status: Time Limit Exceeded

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

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

def func(N, W):
    dp = [0] * (W+1)
    for i in range(N):
        for j in range(W, w[i]-1, -1):
            a = dp[j-w[i]] + v[i]
            if dp[j] < a:
                dp[j] = a
    return dp[W]

print(func(N, W))

Submission status: Time Limit Exceeded

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

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

def func(N, W):
    dp = [0] * (W+1)
    for i in range(N):
        for j in range(W, w[i]-1, -1):
            a = dp[j-w[i]] + v[i]
            if dp[j] < a:
                dp[j] = a
    return dp[W]

print(func(N, W))

Submission status: Time Limit Exceeded

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

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

def func(N, W):
    dp = [0] * (W+1)
    for i in range(N):
        for j in range(W, w[i]-1, -1):
            a = dp[j-w[i]] + v[i]
            if dp[j] < a:
                dp[j] = a
    return dp[W]

print(func(N, W))

Submission status: Time Limit Exceeded

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

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

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

print(dp[W])

Submission status: Time Limit Exceeded

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

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

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

print(dp[W])

Submission status: Time Limit Exceeded

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

dp = [0] * (W+1)
wv = [tuple(map(int, input().split())) for _ in range(N)]
for i in range(N):
    for j in range(W, wv[i][0]-1, -1):
        dp[j] = max(dp[j], dp[j-wv[i][0]]+wv[i][1])

print(dp[W])

Submission status: Time Limit Exceeded

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

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

print(dp[W])

Submission status: Time Limit Exceeded

Solution code:
n,w = map(int,input().split())
WV = [list(map(int,input().split())) for i in range(n)]
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 >= WV[i][0]:
            dp[i+1][j] = max(dp[i][j],dp[i][j-WV[i][0]]+WV[i][1])
        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())
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):
    wi, vi = wv[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[n][w])

Submission status: Time Limit Exceeded

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

weights = [None for i in range(N)]
values = [None for i in range(N)]

# dp[i][j] = maximum value using at most i weight and using elements 1,...,j

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

for i in range(N):
    w, v = map(int, input().split())
    weights[i] = w
    values[i] = v
    
for weight in range(W+1):
    for item in range(1,N+1):
        if weights[item-1] > weight: continue

        dp[weight][item] = max([dp[weight][item]] + 
                               [values[item-1] + dp[weight - weights[item-1]][j] for j in range(item)])

        dp[weight][item] = max(dp[weight-1][item], dp[weight][item])
    
print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, W = map(int, input().split())
wv = np.array([list(map(int, input().split())) for i in range(n)])

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


def chmax(a, b):
    if a > b:
        return a
    else:
        return b


for i in range(n):
    for sum_w in range(W + 1):
        if sum_w >= wv[i, 0]:
            dp[i + 1][sum_w] = chmax(dp[i + 1][sum_w], dp[i][sum_w - wv[i, 0]] + wv[i, 1])
        dp[i + 1][sum_w] = chmax(dp[i + 1][sum_w], dp[i][sum_w])

print(int(dp[n , W]))

Submission status: Time Limit Exceeded

Solution code:

import numpy as np

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

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


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

print(int(dp[-1].max()))

Submission status: Time Limit Exceeded

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

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

print(max(dp))

Submission status: Time Limit Exceeded

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

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

ans = max(dp)
print(ans)

Submission status: Time Limit Exceeded

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

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

ans = max(dp)
print(ans)

Submission status: Time Limit Exceeded

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

dp = [[0 for _ in range(W+1)] for _ in range(N+1)] # (上から)i個目までの品物の中から重さがsum_w以下となるような価値の最大値をdp[i][w]に格納

for i in range(N): # iは0からN-1
    for w in range(W+1): # wは0からW
        if w - wv[i][0] >= 0: # 新しく追加されたi番目の品物を選ぶ場合
            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(dp)
ans = dp[N][W]
print(ans)

Submission status: Time Limit Exceeded

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

dp = [[0 for _ in range(W+1)] for _ in range(N+1)] # (上から)i個目までの品物の中から重さがsum_w以下となるような価値の最大値をdp[i][sum_w]に格納

for i in range(N): # iは0からN-1
    for sum_w in range(W+1): # sum_wは0からW
        if sum_w - wv[i][0] >= 0: # 新しく追加されたi番目の品物を選ぶ場合
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - wv[i][0]] + wv[i][1])
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

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

Submission status: Time Limit Exceeded

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

print(max(dp[N]))

Submission status: Time Limit Exceeded

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

def knapsack(N, W, wv):
  inf = float("inf")
  dp = [[-inf for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1):
    dp[0][i] = 0

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

  return dp[N][W]

if __name__ == "__main__":
  print(knapsack(N, W, wv))

Submission status: Time Limit Exceeded

Solution code:
n, W = list(map(int, input().split()))
dp = [0]*(W+1)
for i in range(n):
    weight, value = list(map(int, input().split()))
    for j in range(W-weight, -1, -1):
        dp[j+weight] = max(dp[j+weight], dp[j] + value)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,W = map(int,input().split(' '))

max_list = np.full(W+1,0, dtype=np.int64)
current_list = np.full(W+1,0, dtype=np.int64)

for i in range(N):
    w,v = map(int,input().split(' '))
    
    for j in range(W+1):
        if w > j:
            current_list[j] = max_list[j]
        else:
            new =  v + max_list[j-w] 
            current_list[j] = new if new > max_list[j] else max_list[j]
            
    max_list = current_list
    current_list = np.full(W+1,0, dtype=np.int64)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,W = map(int,input().split(' '))

max_list = np.full(W+1,0, dtype=np.int64)
current_list = np.full(W+1,0, dtype=np.int64)

for i in range(N):
    w,v = map(int,input().split(' '))
    
    current_list[w:] = current_list[w:] + v + max_list[0:-w]
    for j in range(W+1):
        if current_list[j]>max_list[j]:
            max_list[j] = current_list[j]
    
#     max_list = np.stack([current_list,max_list],0).max(0)
    current_list = np.full(W+1,0, dtype=np.int64)

print(max_list[-1])

Submission status: Time Limit Exceeded

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

WV = []

N, W = [int(v) for v in input().strip().split(' ')]

for _ in range(N):
    WV.append([int(v) for v in sys.stdin.readline().split(' ')])


dp = np.zeros((N + 1, W + 1), dtype = 'uint64')
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], WV[i][1] + dp[i][w - WV[i][0]])
        dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])
print(dp[N][W])

Submission status: Time Limit Exceeded

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

WV = []

N, W = [int(v) for v in input().strip().split(' ')]

for _ in range(N):
    WV.append([int(v) for v in input().strip().split(' ')])


dp = np.zeros((N + 1, W + 1), dtype = 'uint64')
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], WV[i][1] + dp[i][w - WV[i][0]])
        dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])
print(dp[N][W])

Submission status: Time Limit Exceeded

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

WV = []

N, W = [int(v) for v in input().strip().split(' ')]

for _ in range(N):
    WV.append([int(v) for v in input().strip().split(' ')])

cache = {}
def find(w, l):   # あとw持てるときの最大価値（lはすでにナップサックに入っているもの）
    if (w, l) in cache:
        return cache[(w, l)]
    mx = 0
    for i in range(N):
        if w - WV[i][0] < 0 or l & (1 << i):
            continue
        mx = max(mx, WV[i][1] + find(w - WV[i][0], l + 1 << i))
    cache[(w, l)] = mx
    return mx

print(find(W, 0))

Submission status: Time Limit Exceeded

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

WV = []

N, W = [int(v) for v in input().strip().split(' ')]

for _ in range(N):
    WV.append([int(v) for v in input().strip().split(' ')])

def memoize(f):
    cache = {}
    def helper(x, y):
        if (x, y) not in cache:
            cache[(x, y)] = f(x, y)
        return cache[(x, y)]
    return helper

@memoize
def find(w, l):   # あとw持てるときの最大価値（lはすでにナップサックに入っているもの）
    mx = 0
    for i in range(N):
        if w - WV[i][0] < 0 or l & (1 << i):
            continue
        mx = max(mx, WV[i][1] + find(w - WV[i][0], l + 1 << i))
    return mx

print(find(W, 0))

Submission status: Time Limit Exceeded

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

WV = []

N, W = [int(v) for v in input().strip().split(' ')]

for _ in range(N):
    WV.append([int(v) for v in input().strip().split(' ')])

def find(w, l):   # あとw持てるときの最大価値（lはすでにナップサックに入っているもの）
    mx = 0
    for i in range(N):
        if w - WV[i][0] < 0 or l & (1 << i):
            continue
        mx = max(mx, WV[i][1] + find(w - WV[i][0], l + 1 << i))
    return mx

print(find(W, 0))

Submission status: Time Limit Exceeded

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

WV = []

N, W = [int(v) for v in input().strip().split(' ')]

for _ in range(N):
    WV.append([int(v) for v in input().strip().split(' ')])

def find(w, l):   # あとw持てるときの最大価値（lはすでにナップサックに入っているもの）
    mx = 0
    for i in range(N):
        if w - WV[i][0] < 0 or i in l:
            continue
        mx = max(mx, WV[i][1] + find(w - WV[i][0], l + [i]))
    return mx

print(find(W, []))