Problem:


Score : 100 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

1 \leq N \leq 100

1 \leq W \leq 10^5

1 \leq w_i \leq W

1 \leq v_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

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

Sample Input 1

3 8
3 30
4 50
5 60

Sample Output 1

90

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

Sample Input 2

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

Sample Output 2

5000000000

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

Sample Input 3

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

Sample Output 3

17

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



Sample input:
3 8
3 30
4 50
5 60


Sample output:
90

Submission status: Time Limit Exceeded

Solution code:
def aaa():
    N, W = map(int, input().split())
    
    dp = [0] * (W+1) # DP枠_重さ’0’～'W'まで準備
    
    for i in range(N):
        w, v = map(int, input().split()) # 商品, 各々重さと価値
        tmp =tuple(dp[:]) # ひとつ前の商品までのDP枠を参照用にコピー
        for j in range(1, W+1): # 各商品のDP枠への落とし込み
            if j  >= w and tmp[j] < tmp[j-w] + v: # 商品の重さよりDP枠の重さが重い場合で...
                dp[j] = tmp[j-w] + v # この商品を加え, 合計価値が up する場合は replace
            else: # 商品の重さよりDP枠の重さが軽い場合と, ↑で価値が up しない場合は...
                dp[j] = tmp[j] # ↑ 参照データをそのままコピー
        
    print(dp[-1])

aaa()

Submission status: Time Limit Exceeded

Solution code:
# AC by Pypy not Python
# Pythonで通すためには,  npで配列毎まるっと処理する必要あり

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

dp = [0] * (W+1) # DP枠_重さ’0’～'W'まで準備

for i in range(N):
    w, v = map(int, input().split()) # 商品, 各々重さと価値
    tmp = dp[:] # ひとつ前の商品までのDP枠を参照用にコピー
    for j in range(1, W+1): # 各商品のDP枠への落とし込み
        if j  >= w and tmp[j] < tmp[j-w] + v: # 商品の重さよりDP枠の重さが重い場合で...
            dp[j] = tmp[j-w] + v # この商品を加え, 合計価値が up する場合は replace
        else: # 商品の重さよりDP枠の重さが軽い場合と, ↑で価値が up しない場合は...
            dp[j] = tmp[j] # ↑ 参照データをそのままコピー
    
print(dp[-1])

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:

def knapsack1(N,W,weight,value):
    inf = float("inf")
    DP = [[-inf]*(W+1) for i in range(N+1)]
    for i in range(W+1): DP[0][i]=0

    for i in range(N):
        for j in range(W+1):
            if j-weight[i] >= 0:
                DP[i+1][j] = chmax(DP[i][j],DP[i][j-weight[i]]+value[i])
            else:
                DP[i+1][j] = chmax(DP[i+1][j],DP[i][j])
    return DP[N][W] 

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

if __name__ == '__main__':
    N,W = map(int,input().split())
    weight = [0]*N
    value = [0]*N
    #print(weight,value)
    for i in range(N):   
        lst = list(map(int,input().split()))
        #print(lst)
        weight[i] = lst[0]
        value[i] = lst[1]
        #max_w += lst[0]
    #print(weight,value)
    ans = knapsack1(N,W,weight,value)
    print(ans)
    #print(max(max(ans)))
    #print(max(ans[-1]))

Submission status: Time Limit Exceeded

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

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

d = {(W, 0)}

for w, v in items:
    tmp = set()
    for rw, rv in d:
        tmp.add((rw, rv))
        if rw >= w:
            tmp.add((rw-w, rv+v))
    d = tmp

d = {elm[1] for elm in d}

print(max(d))

Submission status: Time Limit Exceeded

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

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

d = {(W, 0)}

for w, v in items:
    tmp = set()
    for rw, rv in d:
        if rw >= w:
            tmp.add((rw-w, rv+v))
    d |= tmp

d = {elm[1] for elm in d}

print(max(d))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def resolve():
	# N: 品物の個数、W: 容量の上限
	N, W = map(int, input().split())
	# DP配列の宣言: DP[N][W]
	dp = np.empty((N+1, W+1), dtype=np.int64)
	# DP配列の初期化
	dp[0,:] = 0
	for i in range(N):
		w_n, v_n = map(int, input().split())
		dp[i+1, :w_n] = dp[i, :w_n]
		for j in range(w_n, W+1):
			dp[i+1, j] = max(
				dp[i, j-w_n]+v_n,	# バッグに入れた時の価値
				dp[i, j]			# バッグにいれない時の価値
			)
	print(dp[N, W])
resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
	# N: 品物の個数、W: 容量の上限
	N, W = map(int, input().split())
	# DP配列の宣言: DP[N][W] = 0
	dp = [[0] * (W+1) for _ in range(N+1)]
	for i in range(N):
		w_n, v_n = map(int, input().split())
		for j in range(w_n):
			dp[i+1][j] = dp[i][j]
		for j in range(w_n, W+1):
			dp[i+1][j] = max(
				dp[i][j-w_n]+v_n,	# バッグに入れた時の価値
				dp[i][j]			# バッグにいれない時の価値
			)
	print(dp[N][W])
resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
	# DP[i+1][j]: i=品物[0:i]の中から, j: 合計jを超えない範囲で選んだ品物の, value=価値の総和の最大値
	# DP[0][j] = 0
	# DP[i+1][j] = DP[i][j] (if j < w_n)
	# DP[i+1][j] = max( DP[i][j], DP[i][j-w_n] + v_n )

	# N: 品物の個数、W: 容量の上限
	N, W = map(int, input().split())
	# print(f'N={N}, W={W}', file=sys.stderr)
	# DP配列の宣言
	dp = [[0] * (W+1) for _ in range(N+1)]
	# print(f'DP.shape=', np.array(dp).shape, file=sys.stderr)
	# DP初期化: dp[0][w] = 0 -> 済み
	# i = 商品番号
	for i in range(N):
		# w_n: 品物[n]の重さ, v_n: 品物[n]の価値
		w_n, v_n = map(int, input().split())
		# j = バッグに入る残り容量
		for j in range(1, W+1):
			# print(f'{i},{j},{w_n},{v_n}', file=sys.stderr)
			# バッグに入る残り容量が品物[i]の重さw_nより大きい場合
			if j >= w_n:
				dp[i+1][j] = max(
					dp[i][j-w_n]+v_n,	# バッグに入れた時の価値
					dp[i][j]			# バッグにいれない時の価値
				)
			else:
				dp[i+1][j] = dp[i][j]	# バッグに入れない
	# 価値の最大値を出力
	print(dp[N][W])
resolve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, W = map(int, input().split())
dp = np.array([ [0]*(W+1) ] * (N+1))
wv = [[0,0]]
for n in range(1,N+1):
    wv.append( list(map(int, input().split())))
    for w_lim in range(1,W+1):
        if w_lim - wv[n][0] >= 0 :
            dp[n][w_lim] = max( dp[n-1][w_lim], dp[n-1][w_lim-wv[n][0]]+wv[n][1] )
        else :
            dp[n][w_lim] = dp[n-1][w_lim]
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, W = map(int, input().split())
wv = [[0,0]]
for _ in range(N):
    wv.append( list(map(int, input().split())))
# N,W = 3, 8
# wv = [[0,0],[3,30], [4,50], [5,60]]
dp = np.array([ [0]*(W+1) ] * (N+1))
# print(dp.shape)
# print(np.array(dp))

for n in range(1,N+1):
    for w_lim in range(1,W+1):
        # print(n, w_lim)
        # print(np.array(dp))
        # v[n]を追加するとき
        if w_lim - wv[n][0] >= 0 :
            dp[n][w_lim] = max( dp[n-1][w_lim], dp[n-1][w_lim-wv[n][0]]+wv[n][1] )
        else :
            dp[n][w_lim] = dp[n-1][w_lim]

# print('\n',np.array(dp))
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
I = lambda : list(map(int,input().split()))

n,we =I()
v=[0]*(n+1);w=[0]*(n+1)
dp=[[0]*(we+1) for i in range(n+1)]
for i in range(1,n+1):
	w[i],v[i] = I()
for i in range(1,n+1):
	for j in range(1,we+1):
		st = dp[i-1][j]
		dt=0
		if w[i]<=j:
			dt=v[i]+dp[i-1][j-w[i]]
		dp[i][j] = max(st,dt)

print(dp[n][we])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N, W = map(int, input().split())
    dp = [[0] * (W+1) for i in range(N+1)]
    #dp[i][j]  iまでをみてjの重さでの最大価値
    for i in range(1,N+1):
        w, v = map(int, input().split())
        dp[i][:] = dp[i-1][:]
        for j in range(w, W+1):
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
#    print(dp)
    print(dp[N][W])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N, W = map(int, input().split())
    dp = [[0] * (W+1) for i in range(N+1)]
    #dp[i][j]  iまでをみてjの重さでの最大価値
    for i in range(1,N+1):
        w, v = map(int, input().split())
        for j in range(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)
    print(dp[N][W])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
from functools import lru_cache
N,W=map(int,input().split())
weights0,profits0 = [0]*N, [0]*N
for i in range(N):
    weights0[i],profits0[i] = map(int,input().split())
weights0 = tuple(weights0)
profits0 = tuple(profits0)
 
@lru_cache(maxsize=100)
def knapsack_recursive(weights, profits, capacity, currentIndex):
    if capacity <= 0 or currentIndex >= len(profits): return 0
    profit = 0
    if weights[currentIndex] <= capacity:
        profit = profits[currentIndex] + knapsack_recursive(weights, profits, capacity - weights[currentIndex], currentIndex + 1)
    tmp = knapsack_recursive(weights, profits, capacity, currentIndex + 1)
    if tmp > profit:
        profit = tmp  
    return profit
  
def main():
    res = knapsack_recursive(weights0, profits0, W, 0)
    print(res)
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

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

for i in range(n+1):
    for w in range(w+1):
        if i == 0 or w == 0:
            dp[i][w] = 0
        if arr[i-1][0] <= w:
            dp[i][w] = max(arr[i-1][1] + dp[i-1][w-arr[i-1][0]], dp[i-1][w])
        else:
            dp[i][w] = dp[i-1][w]

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

Submission status: Time Limit Exceeded

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

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

for i in range(n+1):
    for w in range(w+1):
        if i == 0 or w == 0:
            dp[i][w] = 0
        if wet[i-1] <= w:
            dp[i][w] = max(val[i-1] + dp[i-1][w-wet[i-1]], dp[i-1][w])
        else:
            dp[i][w] = dp[i-1][w]

print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from  collections import defaultdict

sys.setrecursionlimit(1000000000)

# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

def solve(test):
	n, w = map(int, input().split())
	val = [None] * n
	wgt = [None] * n
	for i in range(n):
		wgt[i], val[i] = map(int, input().split())
	dp = {}
	ans = knapsack(wgt, val, 0, n, dp, w)
	print(ans)

def knapsack(wgt, val, i, n, dp, w):
	if (i, w) in dp:
		return dp[(i, w)]
	elif i >= n:
		return 0
	else:
		dp[(i, w)] = knapsack(wgt, val, i + 1, n, dp, w)
		if wgt[i] <= w:
			dp[(i, w)] = max(dp[(i, w)], val[i] + knapsack(wgt, val, i + 1, n, dp, w - wgt[i]))
		return dp[(i, w)]


if __name__ == "__main__":
	test_cases = 1
	for t in range(1, test_cases + 1):
		solve(t)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from  collections import defaultdict

# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

def solve(test):
	n, w = map(int, input().split())
	val = [None] * n
	wgt = [None] * n
	for i in range(n):
		wgt[i], val[i] = map(int, input().split())
	dp = {}
	ans = knapsack(wgt, val, 0, n, dp, w)
	print(ans)

def knapsack(wgt, val, i, n, dp, w):
	if (i, w) in dp:
		return dp[(i, w)]
	elif i >= n:
		return 0
	else:
		dp[(i, w)] = knapsack(wgt, val, i + 1, n, dp, w)
		if wgt[i] <= w:
			dp[(i, w)] = max(dp[(i, w)], val[i] + knapsack(wgt, val, i + 1, n, dp, w - wgt[i]))
		return dp[(i, w)]


if __name__ == "__main__":
	test_cases = 1
	for t in range(1, test_cases + 1):
		solve(t)

Submission status: Time Limit Exceeded

Solution code:
n, W = map(int, input().split())
dp = [0]*(W+1)
for _ in range(n):
    w, v = map(int, input().split())
    tmp_dp = [max(dp[sum_w], dp[sum_w - w] + v) for sum_w in range(w, W+1)]
    dp[w:] = tmp_dp
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
# key not available ""
n, w = [int(i) for i in input().split()]
weights = []
value = []
for _ in range(n):
    x, y = [int(i) for i in input().split()]
    weights.append(x)
    value.append(y)
dp = [[-1 for i in range(w+1)] for j in range(n)]
def go(i,w):
    if w <= 0 or i < 0:
        return 0
    if dp[i][w] >= 0:
        return dp[i][w]
    if weights[i] <= w:
        dp[i][w] = max(go(i-1, w), go(i-1, w-weights[i])+value[i])
    else:
        dp[i][w] = go(i-1,w)
    return dp[i][w]
print(go(n-1,w))
## 0 1 2 3  4  5  6  7  8
#  0 0 0 30 30 30 30 30 30
#  0 0 0 30 50 50 50 80 80
#  0 0 0 30 50 60 60 80 90

Submission status: Time Limit Exceeded

Solution code:
# key not available ""
n, w = [int(i) for i in input().split()]
weights = []
value = []
for _ in range(n):
    x, y = [int(i) for i in input().split()]
    weights.append(x)
    value.append(y)
dp = [[0 for i in range(w+1)] for j in range(n)]
def go(i,w):
    if w <= 0 or i < 0:
        return 0
    if dp[i][w] >0:
        return dp[i][w]
    if weights[i] <= w:
        dp[i][w] = max(go(i-1, w), go(i-1, w-weights[i])+value[i])
    else:
        dp[i][w] = go(i-1,w)
    return dp[i][w]
print(go(n-1,w))
## 0 1 2 3  4  5  6  7  8
#  0 0 0 30 30 30 30 30 30
#  0 0 0 30 50 50 50 80 80
#  0 0 0 30 50 60 60 80 90

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, W, *wv = map(int, open(0).read().split())
    dp = [-1] * (W + 1)
    dp[0] = 0
    for i in range(n):
        w = wv[i * 2]
        v = wv[i * 2 + 1]
        for j in range(W - w, -1, -1):
            if dp[j] == -1:
                continue
            dp[j + w] = max(dp[j] + v, dp[j + w])
        #print(dp)
    print(max(dp))

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, W, *wv = map(int, open(0).read().split())
    dp = [0] * (W + 1)
    for i in range(n):
        w = wv[i * 2]
        v = wv[i * 2 + 1]
        for j in range(W, w - 1, -1):
            dp[j] = max(dp[j], dp[j - w] + v)
    print(dp[W])

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, W, *wv = map(int, open(0).read().split())
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(n):
        w = wv[i * 2]
        v = wv[i * 2 + 1]
        for j in range(0, w):
            dp[i + 1][j] = dp[i][j]
        for j in range(w, W + 1):
            dp[i + 1][j] = max(dp[i][j], dp[i][j - w] + v)
    print(dp[-1][W])

main()

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

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
class Solution:
	def __init__(self):
		pass
	def knapsack01(self,totalWeight,choices):
		dp=[[0]*totalWeight for _ in choices.keys()]
		keys=sorted(list(choices.keys()))
		for i in range(0,len(dp)):
			#capacity=keys[i]
			for j in range(len(dp[0])):
				if j+1>=keys[i]:
					dp[i][j]=max(choices[keys[i]] + (dp[i-1][j-keys[i]] if j-keys[i]>=0 else 0), dp[i-1][j])
				else:
					dp[i][j]=dp[i-1][j]
		#print(dp)
		return dp[-1][-1]
obj=Solution()
n,w=map(int,input().split())
choices={}
for _ in range(n):
	wi,v=map(int,input().split())
	choices[wi]=max(choices.get(wi,0),v)
#print(choices)
print(obj.knapsack01(w,choices))
#print(obj.knapsack01(8,{5:60,3:30,4:50}))

Submission status: Time Limit Exceeded

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

DP = {0: 0}
for i in range(N):
    wi, vi = map(int, input().split())
    p = {}
    for j in DP:
        if j+wi <= W and DP.get(j+wi, 0) < DP[j]+vi:
            p[j+wi] = DP[j]+vi
    for pi in p:
        DP[pi] = p[pi]
print(max((DP[x] for x in DP)))

Submission status: Time Limit Exceeded

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

DP = {0: 0}
for i in range(N):
    wi, vi = map(int, input().split())
    DP_dst = DP.copy()
    for j in DP:
        if j+wi <= W:
            DP_dst[j+wi] = max(DP.get(j+wi, 0), DP[j]+vi)
    DP = DP_dst
print(max((DP[x] for x in DP)))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

# 最大化問題なので0で初期化
dp = [[0] * (w + 1) for _ in range(n + 1)]

# 品物iを選ばない場合で更新してから、選べる場合は再更新
for i in range(1, n + 1):
    for j in range(w + 1):
        dp[i][j] = dp[i - 1][j]
        if j - arr[i - 1][0] >= 0:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - arr[i - 1][0]] + arr[i - 1][1])

print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:

#!/usr/bin/python
# -*- coding: utf-8 -*-

import numpy as np

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

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

#f_inf = float("inf")
#dp = [f_inf]*N

# dp[i][w] = "番号 i 以下の商品でバッグの重さが w 以下になるように最適に詰めた場合"
dp = np.array([[0]*(W+1)]*(N+1),dtype=np.int64)

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

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

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

print(dp[W])

Submission status: Time Limit Exceeded

Solution code:
def main():
    def solve(N, W, wv):
        dp = [-1] * (W+1)
        dp[0] = 0

        for i in range(N):
            wi = wv[i][0]
            vi = wv[i][1]

            for j in range(W-wi, -1, -1):
                # print('i, wi, j = {}, {}, {}'.format(i, wi, j))
                if dp[j] == -1:
                    continue
                dp[j+wi] = max(dp[j+wi], dp[j] + vi)
                # print(dp)

        return max(dp)

    N, W = map(int, input().split())
    wv = tuple(tuple(map(int, input().split())) for i in range(N))
    print(solve(N, W, wv))


##########
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np

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

    # DPテーブル
    dp = np.zeros((N+1, W+1), dtype=int)

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

    solve()


##########
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

#!/usr/bin/python
# -*- coding: utf-8 -*-

import numpy as np

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

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

#f_inf = float("inf")
#dp = [f_inf]*N

# dp[i][w] = "番号 i 以下の商品でバッグの重さが w 以下になるように最適に詰めた場合"
dp = np.array([[0]*(W+1)]*(N+1))

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:

#!/usr/bin/python
# -*- coding: utf-8 -*-

import numpy as np

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

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

#f_inf = float("inf")
#dp = [f_inf]*N

# dp[i][w] = "番号 i 以下の商品でバッグの重さが w 以下になるように最適に詰めた場合"
dp = np.array([[0]*(W+1)]*(N+1))

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
def solve(N,W,wv):
    dp=[-1]*(W+1)
    dp[0]=0
    for i in range(N):
        cur_w=wv[i][0]
        cur_v=wv[i][1]
        for j in range(W-cur_w,-1,-1):
            if dp[j]>=0:
                dp[j+cur_w]=max(dp[j+cur_w],dp[j]+cur_v)
    return max(dp)


N,W=map(int,input().split())
wv=tuple(tuple(map(int,input().split())) for _ in range(N))
print(solve(N,W,wv))

Submission status: Time Limit Exceeded

Solution code:
def solve(N,W,wv):
    dp=[-1]*(W+1)
    dp[0]=0
    for i in range(N):
        cur_w=wv[i][0]
        cur_v=wv[i][1]
        for j in range(W-cur_w,-1,-1):
            dp[j+cur_w]=max(dp[j+cur_w],dp[j]+cur_v)
    return max(dp)


N,W=map(int,input().split())
wv=tuple(tuple(map(int,input().split())) for _ in range(N))
print(solve(N,W,wv))

Submission status: Time Limit Exceeded

Solution code:
def solve(N,W,wv):
    dp=[[-1]*(W+1) for _ in range(N+1)]
    dp[0][0]=0
    for i in range(0,N):
        for j in range(W):
            cur_w=wv[i][0]
            cur_v=wv[i][1]
            if dp[i][j]>=0:
                dp[i+1][j]=max(dp[i+1][j],dp[i][j])
                if j+cur_w<=W:
                    dp[i+1][j+cur_w]=max(dp[i+1][j+cur_w],dp[i][j]+cur_v)
    ans=0
    for j in range(W+1):
        if ans < dp[N][j]:
            ans=dp[N][j]
    return ans
            


N,W=map(int,input().split())
wv=tuple(tuple(map(int,input().split())) for _ in range(N))
print(solve(N,W,wv))

Submission status: Time Limit Exceeded

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

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
def solve(arr,n,w):
    dp=[[0 for i in range(w+1)]for j in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,w+1):
            if arr[i-1][0]>j:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=max(arr[i-1][1]+dp[i-1][j-arr[i-1][0]],dp[i-1][j])
                
    return dp[-1][-1]
                

value=[int(i) for i in input().split()]
n,w=value[0],value[1]
a1=[[int(i) for i in input().split()]for j in range(n)]
print(solve(a1,n,w))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,w = map(int, input().split())
high = np.array([[0]*(w+1)]*(n+1),np.int)
for i in range(1,n+1):
    weight, value = map(int, input().split())
    for j in range(w+1):
        if j < weight:
            high[i][j] = high[i-1][j]
        else:
            high[i][j] = max([high[i-1][j-weight]+value, high[i-1][j]])
print(high[n][w])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

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

w = []
v = []

for x in range(n):
    peso,valor = map(int,input().split())
    w.append(peso)
    v.append(valor)

dp = [0] * (W+1)

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


resposta = 0

for x in dp:
    resposta = max(x,resposta)

print(resposta)

Submission status: Time Limit Exceeded

Solution code:
n ,c = map(int,input().split())
wt =[]; val=[]

for _ in range(n):
  wi , vi = map(int,input().split())
  wt.append(wi)
  val.append(vi)
  
# dp [n][c+1] = 0 
dp = [[0 for i in range(c+1)]for j in range(n)]

for w in range(c+1):
  wi = wt[0]
  if wi<=w:
    dp[0][w]=val[0]
  else:
    dp[0][0]=0

for i in range(1,n):
  wi = wt[i];vi = val[i]
  for w in range(1,c+1):
    if wi<=w:
      dp[i][w] = max(vi+dp[i-1][w-wi] , dp[i-1][w])
    else:
      dp[i][w] = dp[i-1][w]

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

Submission status: Time Limit Exceeded

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

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
def recur(n,w):
    if n==0 or w==0:
        return 0
    elif (n,w) in dp:
        return dp[(n,w)]
    elif l[n-1][0]<=w:
        k=max(recur(n-1,w-l[n-1][0])+l[n-1][1],recur(n-1,w))
        dp[(n,w)]=k
        return k
    else:
        k=recur(n-1,w)
        dp[(n,w)]=k
        return k
n,w=map(int,input().split())
l=[]
for _ in range(n):
    a,b=map(int,input().split())
    l.append((a,b))
dp=dict()
print(recur(n,w))

Submission status: Time Limit Exceeded

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

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

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

print(max(dp[-1]))

Submission status: Time Limit Exceeded

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

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:




def knapsack2(n,w,arr):
	dp=[0]*(w+1)
	for i in arr:
		for j in range(w,i[0]-1,-1):
			dp[j]=max(dp[j],dp[j-i[0]]+i[1])

		# print(i[0],dp)
	return dp[w]

# k=input()
# d=int(input())

# res=degit_sum(k,d)
# print(res)
n,w=map(int,input().split())
arr=[]
for i in range(n):
	arr.append(tuple(map(int,input().split())))
res=knapsack2(n,w,arr)
print(res)

Submission status: Time Limit Exceeded

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

N,W = map(int, readline().split())
w=[];v=[]
for _ in range(N):
  a,b = map(int, readline().split())
  w.append(a)
  v.append(b)
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 >= w[i]:
      dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i])
    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())
X = [0] + [-1] * W

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

print(max(X))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n,k=map(int,input().split())
v=[0 for _ in range(n)]
w=[0 for _ in range(n)]
for i in range(n):
	w[i],v[i] = map(int,input().split())

dp = np.full((n+1, k+1), 0, dtype=np.int64)

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

Submission status: Time Limit Exceeded

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

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

print(dp[N][W])