Problem:


Score : 100 points

Problem Statement

There are N items, numbered 1, 2, \ldots, N.
For each i (1 \leq i \leq N), Item i has a weight of w_i and a value of v_i.

Taro has decided to choose some of the N items and carry them home in a knapsack.
The capacity of the knapsack is W, which means that the sum of the weights of items taken must be at most W.

Find the maximum possible sum of the values of items that Taro takes home.

Constraints

All values in input are integers.

1 \leq N \leq 100

1 \leq W \leq 10^5

1 \leq w_i \leq W

1 \leq v_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

Print the maximum possible sum of the values of items that Taro takes home.

Sample Input 1

3 8
3 30
4 50
5 60

Sample Output 1

90

Items 1 and 3 should be taken.
Then, the sum of the weights is 3 + 5 = 8, and the sum of the values is 30 + 60 = 90.

Sample Input 2

5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

Sample Output 2

5000000000

The answer may not fit into a 32-bit integer type.

Sample Input 3

6 15
6 5
5 6
6 4
6 6
3 5
7 2

Sample Output 3

17

Items 2, 4 and 5 should be taken.
Then, the sum of the weights is 5 + 6 + 3 = 14, and the sum of the values is 6 + 6 + 5 = 17.



Sample input:
3 8
3 30
4 50
5 60


Sample output:
90

Submission status: Time Limit Exceeded

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

# dp[i個目][重さ合計] = 最大価値
dp = [[0 for i in range(w+1)] for _ in range(n+1)]
# print(dp)
for i in range(1, n+1):
	for iw in range(w+1):
		iw_im1 =  iw - wv[i-1][0]
		if not (iw_im1 < 0):
			dp[i][iw] = dp[i-1][iw_im1] + wv[i-1][1]

		dp[i][iw] = max(dp[i][iw], dp[i-1][iw])


print(max(dp[n]))

Submission status: Time Limit Exceeded

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

wv.insert(0, [0, 0]) # 先頭に要素をinsert

# dp[i個目][重さ合計] = 最大価値
dp = [[0 for i in range(w+1)] for _ in range(n+1)]
# print(dp)
for i in range(1, n+1):
	for iw in range(w+1):
		iw_im1 =  iw - wv[i][0]
		if not (iw_im1 < 0):
			dp[i][iw] = dp[i-1][iw_im1] + wv[i][1]

		dp[i][iw] = max(dp[i][iw], dp[i-1][iw])


print(max(dp[n]))

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 w, v in WV:
	for tw in range(W, w - 1, -1):
		dp[tw] = max(dp[tw], dp[tw - w] + v)
	#print(dp)
print(max(dp))

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
I=lambda:list(map(int,input().split()))
n,W=I()
g=[0]+[I()for _ in range(n)]
dp=[[0]*-~W for _ in range(n+1)]
for i in range(1,n+1):
    t=g[i]
    for j in range(W+1):
        if j-t[0]>=0:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[0]]+t[1])
        else:
            dp[i][j]=dp[i-1][j]
print(max(dp[-1]))

Submission status: Time Limit Exceeded

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


n, w = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
# dp = np.zeros((N+1, W+1))  #i個目の品物までで重さw以下のときの価値の最大値 
dp = [[0]*(W+1) for _ in range(N+1)]
"""
dp[i, wi:W+1] = max(i番目の重さwiの品物を入れた場合, 入れなかった場合)
         = np.max(dp[i-1, :W-wi+1] + v, dp[i-1, wi:W+1])
"""

for i in range(1, N+1):
    w, v = map(int, input().split())

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, W = map(int, input().split())
dp = np.zeros((N+1, W+1))  #i個目の品物までで重さw以下のときの価値の最大値 
"""
dp[i, wi:W+1] = max(i番目の重さwiの品物を入れた場合, 入れなかった場合)
         = np.max(dp[i-1, :W-wi+1] + v, dp[i-1, wi:W+1])
"""
for i in range(1, N+1):
    wi, vi = map(int, input().split())
    for k in range(1, i+1):
        tmp = np.maximum(dp[i-k, :W-wi+1] + vi, dp[i-k, wi:W+1])
        dp[i, wi:W+1] = np.maximum(dp[i, wi:W+1], tmp)
    

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

Submission status: Time Limit Exceeded

Solution code:
# EduDPD - Knapsack 1
import sys
input = sys.stdin.readline

n, w = list(map(int, input().rstrip().split()))
arr = [tuple(map(int, input().rstrip().split())) for _ in range(n)]
dp = [0] * (w + 1)
for i in range(n):
    for j in range(w, arr[i][0] - 1, -1):
        dp[j] = max(dp[j], dp[j - arr[i][0]] + arr[i][1])
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n, W = map(int, input().split())
wv = (map(int, input().split()) for _ in range(n))
dp = [0] * (W+1)

for w, v in wv:
    for j in range(W, w-1, -1):
        DP = dp[j-w] + v
        if dp[j] < DP:
            dp[j] = DP
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, W = map(int, input().split())
wv = []
for i in range(n):
    wv.append(list(map(int, input().split())))
dp = [0] * (W+1)

for w, v in wv:
    for j in range(W, w-1, -1):
        DP = dp[j-w] + v
        if dp[j] < DP:
            dp[j] = DP
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, W = map(int, input().split())
wv = []
for i in range(n):
    wv.append(list(map(int, input().split())))
dp = np.zeros(W+1, dtype=np.int64)

for w, v in wv:
    for j in range(W, w-1, -1):
        dp[j] = max(dp[j], dp[j-w]+v)
print(dp[-1])

Submission status: Time Limit Exceeded

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

print(max(dp[N]))

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

Submission status: Time Limit Exceeded

Solution code:
# dp[i][w_sum]: i番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値

N,W=map(int,input().split())
items=[tuple(map(int,input().split())) for i in range(N)]
items.insert(0, (0,0))

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

for i in range(1,N+1):
    for j in range(W+1):
        # take item
        if j-items[i][0]>=0:
            dp[i][j]=dp[i-1][j-items[i][0]]+items[i][1]
        
        dp[i][j]=max(dp[i][j],dp[i-1][j])

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
weight = [0] * 110
value = [0] * 110

for i in range(n):
  weight[i], value[i] = map(int, input().split())

  dp = [[0] * 100100 for _ in range(110)]

  for i in range(n):

    for sum_w in range(1, w + 1):

      if sum_w - weight[i] >= 0:
        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - weight[i]] + value[i])

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

print(max(dp[n]))

Submission status: Time Limit Exceeded

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

value = [0] * (W + 1)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
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 _ in range(n+1)]  

for i in range(n):
  sum_w = 0
  while sum_w <= W:
    if sum_w >= weight[i]:
      dp[i+1][sum_w] = max(dp[i][sum_w - weight[i]] + value[i],
                          dp[i][sum_w])
    else:
      dp[i+1][sum_w] = dp[i][sum_w]
    sum_w += 1
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+1)]

for i in range(1,n+1):
    s,v=map(int,input().split())
    for j in range(w+1):

        if(s>j):
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j-1],dp[i-1][j-s]+v)
print(dp[n][w])

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
items = []
for _ in range(N):
    items.append(tuple(map(int, input().split())))
dp = [[0 for j in range(W+1)] for i in range(N+1)]
for i in range(1, N+1):
    w, v = items[i-1]
    for j in range(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(max(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
items = []
for _ in range(N):
    items.append(tuple(map(int, input().split())))
dp = {i: {j: 0 for j in range(W+1)} for i in range(N+1)}
for i in range(1, N+1):
    w, v = items[i-1]
    for j in range(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(max(dp[N].values()))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[0] * (W + 1) for _ in range(N + 1)]

    for i, (cw, cv) in enumerate(zip(w, v)):
        for j in range(W + 1):
            dp[i+1][j] = dp[i][j]
            if 0 <= j - cw :
                dp[i+1][j] = max(dp[i+1][j], dp[i][j - cw] + cv)
    return max(dp[-1])


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))
    result = solve(N, W, w, v)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
N,W=map(int,input().split())
dp_1=[0]*(W+1)
dp_2=[0]*(W+1)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
N,W=map(int,input().split())
dp=[[0 for i in range(W+1)] for j in range(N+1)]
input=sys.stdin.readline

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n, max_w = map(int, input().split())

dp = [-1 for _ in range(max_w + 1)]
dp[0] = 0

for i in range(n):
    w, v = map(int, input().split())
    queue = list()
    for i in range(max_w, w - 1, -1):
        dp[i] = max(dp[i], dp[i - w] + v)

print(max(dp))

Submission status: Time Limit Exceeded

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

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

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

print(dp[N][Weight])

Submission status: Time Limit Exceeded

Solution code:
import sys
import math 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()

N,W = na()
C,V = [0],[0]
for i in range(N):
    c,v = na()
    C.append(c)
    V.append(v)
#print(W)
dp = [[0]*(W+1) for j in range(N+1)]
#print(dp)

for i in range(1,N+1):
    for sum_w in range(W+1):
        if(sum_w-C[i]>=0):
            dp[i][sum_w] = max(dp[i-1][sum_w],dp[i-1][sum_w-C[i]]+V[i])
        else:
            dp[i][sum_w] = dp[i-1][sum_w]

#print(dp)

print(max(dp[N]))

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

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]
dp = [0]*(1+W)
w,v = WV[0]
dp[w:] = [v]*(W+1-w)
for i in range(1,N):
    dp_t = dp.copy()
    w,v = WV[i]
    for j in range(W+1):
        if j+w>W:
            break
        tmp = dp[j] + v
        dp_t[j+w] = max(dp[j+w], tmp)
    dp = dp_t.copy()
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

input = sys.stdin.readline

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

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

knapsack(N, W)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

input = sys.stdin.readline

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

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

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

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

knapsack(N, W)

Submission status: Time Limit Exceeded

Solution code:
import fileinput


def knapsack(capacity, item_weights, item_values):
    no_current_item_values = [0] * (capacity + 1)
    for i, val in enumerate(item_values):
        with_current_item_values = [0] * (capacity + 1)
        for current_capacity in range(1, capacity + 1):
            if current_capacity < item_weights[i]:
                with_current_item_values[current_capacity] = no_current_item_values[current_capacity]
            else:
                with_current_item_values[current_capacity] = max(
                    no_current_item_values[current_capacity],
                    no_current_item_values[current_capacity - item_weights[i]] + val
                )
        no_current_item_values = with_current_item_values

    return no_current_item_values[-1]


inp = fileinput.input()

first_line_split = inp.readline().split(" ")

item_count = int(first_line_split[0])
capacity = int(first_line_split[1])

item_weights = []
item_values = []
for _ in range(item_count):
    split = inp.readline().split(" ")
    item_weights.append(int(split[0]))
    item_values.append(int(split[1]))

print(knapsack(capacity, item_weights, item_values))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

input = sys.stdin.readline

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

input = sys.stdin.readline

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

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

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

        
print(int(maximum))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

input = sys.stdin.readline

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

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

for i in range(N):
    for w in range(W+1):
        if w >= Weight[i]:
            dp[i+1, w] = dp[i, w - Weight[i]] + V[i]
        else:
            dp[i+1, w] = dp[i, w]
maximum = 0
for i in range(N+1):
    for j in range(W+1):
        if maximum < dp[i,j]:
            maximum = dp[i,j]
print(int(maximum))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
nw = input().split()
N = int(nw[0])
W = int(nw[1])

dp = np.zeros((N+1, W+1), dtype=np.int64)
#dp = [[0]*(W+1) for i in range(N+1)]

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

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

Submission status: Time Limit Exceeded

Solution code:
nw = input().split()
N = int(nw[0])
W = int(nw[1])

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

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

print(max(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
# atcoder DPまとめ
# D_Knapsack1

# def get_inputs():
#     [n, w] = [int(x) for x in input().split()]
#     g = []
#     for _ in range(n):
#         g.append([int(x) for x in input().split()])
#
#     return n, w, g


if __name__ == "__main__":
    
    n, w = map(int, input().split())
    
    #### First Try
    # この方法では後半の問題でTLEになってしまう
    # 二重ループの部分で時間がかかっている
    # # dp[i][w]はi-1個目の品物を加えるか吟味した後、重さw以下で最大の価値
    # dp = [[0] * (w + 1) for _ in range(n + 1)]
    #
    # for i in range(1, n + 1):
    #     for wgt in range(w + 1):
    #         if wgt >= g[i -1][0]:
    #             dp[i][wgt] = max(dp[i - 1][wgt - g[i - 1][0]] + g[i - 1][1], dp[i - 1][wgt])
    #         else:
    #             dp[i][wgt] = dp[i - 1][wgt]
    #
    # print(max(dp[n]))

    ### Second Try
    # 動的計画法の部分で、古いiの情報は不要で一つ前の状態さえあれば解ける
    # そこに着目し、かつ不要な判定や更新を減らすために、あるiの時に、
    # 大きなwから最適値を求めるようにする

    # dp[w]は,現在評価中のiにおいて、重さwの時の最大価値の値


    ### Third Try
    # maxをやめてif文に変更

    ### Fourth Try
    # 最初に荷物の情報をリストに読み込んでいたが、そこが時間がかかているようなので逐次読み込みに修正

    dp = [0] * (w + 1)      # 初期値は０　範囲は0〜wまで

    for i in range(n):      # 品物0からn-1までを評価
        wt, vl = map(int, input().split())
        for j in range(w, wt - 1, -1):
            tmp = dp[j - wt] + vl
            if tmp > dp[j]:
                dp[j] = tmp

    print((dp[w]))

Submission status: Time Limit Exceeded

Solution code:
# atcoder DPまとめ
# D_Knapsack1

def get_inputs():
    [n, w] = [int(x) for x in input().split()]
    g = []
    for _ in range(n):
        g.append([int(x) for x in input().split()])
    
    return n, w, g


if __name__ == "__main__":
    
    n, w, g = get_inputs()
    
    #### First Try
    # この方法では後半の問題でTLEになってしまう
    # 二重ループの部分で時間がかかっている
    # # dp[i][w]はi-1個目の品物を加えるか吟味した後、重さw以下で最大の価値
    # dp = [[0] * (w + 1) for _ in range(n + 1)]
    #
    # for i in range(1, n + 1):
    #     for wgt in range(w + 1):
    #         if wgt >= g[i -1][0]:
    #             dp[i][wgt] = max(dp[i - 1][wgt - g[i - 1][0]] + g[i - 1][1], dp[i - 1][wgt])
    #         else:
    #             dp[i][wgt] = dp[i - 1][wgt]
    #
    # print(max(dp[n]))

    ### Second Try
    # 動的計画法の部分で、古いiの情報は不要で一つ前の状態さえあれば解ける
    # そこに着目し、かつ不要な判定や更新を減らすために、あるiの時に、
    # 大きなwから最適値を求めるようにする

    # dp[w]は,現在評価中のiにおいて、重さwの時の最大価値の値


    ### Third Try
    # maxをやめてif文に変更

    dp = [0] * (w + 1)      # 初期値は０　範囲は0〜wまで

    for i in range(n):      # 品物0からn-1までを評価
        wt, vl = g[i]
        for j in range(w, wt - 1, -1):
            tmp = dp[j - wt] + vl
            if tmp > dp[j]:
                dp[j] = tmp

    print((dp[w]))

Submission status: Time Limit Exceeded

Solution code:
# atcoder DPまとめ
# D_Knapsack1

def get_inputs():
    [n, w] = [int(x) for x in input().split()]
    g = []
    for _ in range(n):
        g.append([int(x) for x in input().split()])
    
    return n, w, g


if __name__ == "__main__":
    
    n, w, g = get_inputs()
    
    #### First Try
    # この方法では後半の問題でTLEになってしまう
    # 二重ループの部分で時間がかかっている
    # # dp[i][w]はi-1個目の品物を加えるか吟味した後、重さw以下で最大の価値
    # dp = [[0] * (w + 1) for _ in range(n + 1)]
    #
    # for i in range(1, n + 1):
    #     for wgt in range(w + 1):
    #         if wgt >= g[i -1][0]:
    #             dp[i][wgt] = max(dp[i - 1][wgt - g[i - 1][0]] + g[i - 1][1], dp[i - 1][wgt])
    #         else:
    #             dp[i][wgt] = dp[i - 1][wgt]
    #
    # print(max(dp[n]))

    ### Second Try
    # 動的計画法の部分で、古いiの情報は不要で一つ前の状態さえあれば解ける
    # そこに着目し、かつ不要な判定や更新を減らすために、あるiの時に、
    # 大きなwから最適値を求めるようにする

    # dp[w]は,現在評価中のiにおいて、重さwの時の最大価値の値
    dp = [0] * (w + 1)      # 初期値は０　範囲は0〜wまで

    for i in range(n):      # 品物0からn-1までを評価
        wt, vl = g[i]
        for j in range(w, wt - 1, -1):
            dp[j] = max(dp[j - wt] + vl, dp[j])

    print(max(dp))

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
# atcoder DPまとめ
# D_Knapsack1

def get_inputs():
    [n, w] = [int(x) for x in input().split()]
    g = []
    for _ in range(n):
        g.append([int(x) for x in input().split()])
    
    return n, w, g


if __name__ == "__main__":
    
    n, w, g = get_inputs()
    
    # dp[i][w]はi-1個目の品物を加えるか吟味した後、重さw以下で最大の価値
    dp = [[0] * (w + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for wgt in range(w + 1):
            if wgt >= g[i -1][0]:
                dp[i][wgt] = max(dp[i - 1][wgt - g[i - 1][0]] + g[i - 1][1], dp[i - 1][wgt])
            else:
                dp[i][wgt] = dp[i - 1][wgt]
    
    print(max(dp[n]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
D - Knapsack 1
https://atcoder.jp/contests/dp/tasks/dp_d

"""
import sys


def solve(N, W, items):
    dp = [0-1] * (W+1)
    dp[0] = 0
    for w, v in items:
        for i in range(W, w-1, -1):
            if dp[i-w] != -1:
                dp[i] = max(dp[i], dp[i-w]+v)
    return max(dp)



def main(args):
    N, W = map(int, input().split())
    items = [[int(i) for i in input().split()] for _ in range(N)]
    ans = solve(N, W, items)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
D - Knapsack 1
https://atcoder.jp/contests/dp/tasks/dp_d

"""
import sys


def solve(N, W, items):
    ans = {0: 0}
    for w, v in items:
        u = dict()
        for x, y in ans.items():
            if x+w <= W and ans.get(x+w, 0) < y+v:
                u[x+w] = y+v
        ans.update(u)
    return max([v for v in ans.values()])


def main(args):
    N, W = map(int, input().split())
    items = [[int(i) for i in input().split()] for _ in range(N)]
    ans = solve(N, W, items)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

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

	dp = [0] * (W + 1)
	for w, v in WV:
		for n in range(W, w - 1, -1):
			dp[n] = max(dp[n], dp[n - w] + v)
		#for t in dp:
		#	print("{:4d}".format(t), end="")
		#print()
	return max(dp)

print(main())

Submission status: Time Limit Exceeded

Solution code:
def chmax(a, b):
	if a < b:
		return b
	return a

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

	dp = [0] * (W + 1)
	for w, v in WV:
		for sumw in range(W, w - 1, -1):
			dp[sumw] = chmax(dp[sumw], dp[sumw - w] + v)
		#for x in dp:
		#	print("{:4d}".format(x), end="")
		#print()
	return max(dp)

print(main())

Submission status: Time Limit Exceeded

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

	dp = [0] * (W + 1)
	for w, v in WV:
		for sumw in range(W, w - 1, -1):
			dp[sumw] = max([dp[sumw], dp[sumw - w] + v])
		#for x in dp:
		#	print("{:4d}".format(x), end="")
		#print()
	return max(dp)

print(main())

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 n in range(N):
#	w, v = WV[n]
for w, v in WV:
	for sumw in range(W, w - 1, -1):
		#dp[sumw] = max([dp[sumw], dp[sumw - w] + v])
		if dp[sumw] < dp[sumw - w] + v:
			dp[sumw] = dp[sumw - w] + v
	#for x in dp:
	#	print("{:4d}".format(x), end="")
	#print()
print(max(dp))

Submission status: Time Limit Exceeded

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

dp = [0] * (W + 1)
for n in range(N):
	w, v = WV[n]
	for sumw in range(W, w - 1, -1):
		#dp[sumw] = max([dp[sumw], dp[sumw - w] + v])
		if dp[sumw] < dp[sumw - w] + v:
			dp[sumw] = dp[sumw - w] + v
	#for x in dp:
	#	print("{:4d}".format(x), end="")
	#print()
print(max(dp))

Submission status: Time Limit Exceeded

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

dp = [0] * (W + 1)
for n in range(N):
	w, v = WV[n]
	for sumw in range(W, w - 1, -1):
		dp[sumw] = max([dp[sumw], dp[sumw - w] + v])
	#for x in dp:
	#	print("{:4d}".format(x), end="")
	#print()
print(max(dp))

Submission status: Time Limit Exceeded

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

dp = [0] * (W + 1)
for n in range(N):
	w, v = WV[n]
	for sumw in range(W, w - 1, -1):
		dp[sumw] = max(dp[sumw], dp[sumw - w] + v)
	#for x in dp:
	#	print("{:4d}".format(x), end="")
	#print()
print(max(dp))

Submission status: Time Limit Exceeded

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

dp = [0] * (W + 1)
for n in range(N):
	w, v = WV[n]
	for sumw in range(W, -1, -1):
		if sumw + w <= W:
			dp[sumw + w] = max(dp[sumw + w], dp[sumw] + v)
	#for x in dp:
	#	print("{:4d}".format(x), end="")
	#print()
print(max(dp))

Submission status: Time Limit Exceeded

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

dp = [[0] * (W + 1) for _ in range(N + 1)]
for n in range(1, N + 1):
	w, v = WV[n - 1]
	for sumw in range(W + 1):
		dp[n][sumw] = max(dp[n][sumw], dp[n - 1][sumw])
		if sumw + w <= W:
			dp[n][sumw + w] = max(dp[n][sumw + w], dp[n - 1][sumw] + v)
"""
for x in dp:
	for y in x:
		print("{:4d}".format(y), end="")
	print()
"""
print(dp[-1][-1])

Submission status: Time Limit Exceeded

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

wV = [list(map(lambda x: int(x), input().split())) for _ in range(N)]

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

for i in range(N):
	for j in range(W + 1):
		if j + wV[i][0] <= W:
			dp[i + 1][j + wV[i][0]] = dp[i][j] + wV[i][1]
		
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
		
print(dp[N][W])