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())
w = []
v = []
for _ in range(n):
    ww, vv = map(int, input().split())
    w.append(ww)
    v.append(vv)

# dp[i+1][j]=i番目までの品物から重さの総和がj以下となるように選んだ時の価値の総和の最大値
dp = [[0 for j in range(W+1)] for i in range(n+1)]
for i in range(n):
    for j in range(W+1):
    # ナップザックの容量をjと仮定する
        # とi番目の品物を持てないとき
        if j < w[i]:
            # i番目の品物をスルーする
            dp[i + 1][j] = dp[i][j]
        # i番目の品物を持とうと思えば持てるとき
        else:
            # 1.i番目の品物を持たなかった場合
            # 2.i番目の品物を持った場合
            # 以上2通りの内、価値の総和が最大となる品物の選び方をする
            dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
print(dp[n][W])


# イメージはこんな感じ
# 入力が
# n = 4
# W = 5
# (w, v) = ((2, 3), (1, 2), (3, 4), (2, 2))
# となるとき
# → はナップザックに入ってる品物の重さ(j <= W)の総和
# ↓ はi(i <= n)番目までの品物を順に確認
# (i+1, j)は最初の品物を0番目として数えたときの、
# i番目までの品物から重さの総和がj以下となるように選んだ時の価値の総和の最大値
# i\j  0   1   2   3   4   5
#
#  0   0   0   0   0   0   0
#
#  1   0   0   3   3   3   3
#
#  2   0   2   3   5   5   5
#
#  3   0   2   3   5   6   7
#
#  4   0   2   3   5   6   7

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

Submission status: Time Limit Exceeded

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

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

for i in range(n+1):
    if i == 0:
        continue
    for j in range(weight+1):
        case1 = dp[i-1][j]
        if j - items[i-1][0] < 0:
            dp[i][j] = case1
            continue
        else:
            case2 = dp[i-1][j-items[i-1][0]] + items[i-1][1]
            if case1 >= case2:
                dp[i][j] = case1
            else:
                dp[i][j] = case2

print(max([dp[i][weight] for i in range(n+1)]))

Submission status: Time Limit Exceeded

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

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

for i in range(n+1):
    if i == 0:
        continue
    for j in range(weight+1):
        case1 = dp[i-1][j]
        if j - items[i-1][0] < 0:
            case2 = -1
        else:
            case2 = dp[i-1][j-items[i-1][0]] + items[i-1][1]
        dp[i][j] = max(case1,case2)

print(max([dp[i][weight] for i in range(n+1)]))

Submission status: Time Limit Exceeded

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

n, W = map(int, input().split())
dp = [[0 for i in range(W + 1)] for j in range(n + 1)]
wv = [[int(x) for x in input().split()] for _ in range(n)]

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

Submission status: Time Limit Exceeded

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

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

# i番目以降の品物で、容量がjのときの価値の最大値


def value(i, j):
    # もう品物がない
    if i == n:
        ret = 0
    # 品物が入らない
    elif j < wv[i][0]:
        ret = value(i+1, j)
    # 品物を入れない場合と入れる場合
    else:
        ret = max(value(i+1, j), value(i+1, j-wv[i][0]) + wv[i][1])
    return ret


print(value(0, w))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, lim_w = map(int, input().split())
w, v = [], []

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

# dp[i][j] := i番目までの品物を見たとき, 重さの総和がj以下となるように選んだときの価値の総和の最大値
dp = [ [0]*(lim_w+1) for _ in range(n+1) ]

for i in range(n):
    for j in range(lim_w+1):
        if j < w[i]:
            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][lim_w])

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def knapsack(N, W, weight, value):
  inf = float("inf")
  dp = [[-inf]*(W+1) for _ 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 weight[i] <= j:
        dp[i+1][j] = max(dp[i][j], dp[i][j-weight[i]]+value[i])
      else:
        dp[i+1][j] = dp[i][j]
  return dp[N][W]
  
N, W = map(int, input().split())
weight, value = [], []
for i in range(N):
  w, v = map(int, input().split())
  weight.append(w)
  value.append(v)

print(knapsack(N, W, weight, value))

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
# import scipy as sp
# import sys
# input = sys.stdin.readline
# print(a,b,c,sep="") # 半角スペースなしで出力(abc)
# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=list(map(int, input().split()))  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# a=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# a=[int(input()) for _ in range (n)]  #リスト入力  改行でa1 ... anのとき
# s=[list(map(str,list(input()))) for i in range(h)]  # 文字列の二次元配列入力
# s = [list(map(int, input().split())) for i in range(n)] # 数値の二次元配列入力
# a = b[:], a = [x[:] for x in b] # deepcopy
# chr(ord('a') + 1) # chrのインクリメント
# s.sort(key=lambda x: x[1], reverse=False) # 2番目の要素で昇順にソート（Trueなら降順）

n, w = list(map(int, input().split()))
wl = [0] * n
vl = [0] * n
for i in range(n):
    wl[i], vl[i] = map(int, input().split())


dp = [[0]*(w+1)for _ in range(n+1)]  # h:item w:weight v:value
for i in range(n):
    for j in range(w+1):
        if j+wl[i] <= w:
            dp[i+1][j+wl[i]] = max(dp[i+1][j+wl[i]], dp[i][j]+vl[i])
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])

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

Submission status: Time Limit Exceeded

Solution code:
n,ww=map(int,input().split())
w=[0]*n
v=[0]*n
for i in range(n):
  w[i],v[i]=map(int,input().split())
k=[[0]*(n+1) for e in range(ww+1)]

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

Submission status: Time Limit Exceeded

Solution code:
import sys


def main():
    input = sys.stdin.readline

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

    WV = (map(int, input().split()) for _ in range(N))

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


main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


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

    WV = (map(int, input().split()) for _ in range(N))

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


main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


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

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

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


main()

Submission status: Time Limit Exceeded

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

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

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


main()

Submission status: Time Limit Exceeded

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

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

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

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

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


main()

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
n, mw = map(int, input().split())
w = []
v = []

for i in range(n):
    ww, vv = map(int, input().split())
    w.append(ww)
    v.append(vv)

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

print(dp[mw])

Submission status: Time Limit Exceeded

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

dp = [[0]*(W+1) for i in range(N+1)]
# dp[i][j] はi-1番目までのものから重さj以下になるように選んだ最大値

for i in range(1,N+1):
    w,v = ls[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)
            #ここでj-wを指定してしまっていいのか-> dp[i-1][j-w]>dp[i-1][j-w-1]であるので良い　j-wはそれ以下の最大値になっている
        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())
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 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:
import numpy as np
def main():
    N,W=map(int,input().split())
    dp=np.zeros((N+1,W+1),dtype=int)
    for i in range(1,N+1):
        w,v=map(int,input().split())
        for j in range(W+1):
            if w<=j:
                can1=max(dp[i-1][k] for k in range(j-w+1))
                can2=max(dp[i-1][k] for k in range(j-w+1,j+1))
                dp[i][j]=max(can1+v,can2)
            else:
                dp[i][j]=dp[i-1][j]
    print(dp[N][W])
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,W=map(int,input().split())
    dp=[0]*(W+1)
    for _ in range(1,N+1):
        w,v=map(int,input().split())
        for i in range(w,W+1)[::-1]:
            can1=dp[i-w]+v
            can2=dp[i]
            dp[i]=max(can1,can2)
    print(max(dp))
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,W=map(int,input().split())
    dp=[0]*(W+1)
    for _ in range(1,N+1):
        w,v=map(int,input().split())
        for i in range(W+1)[::-1]:
            if w<=i:
                can1=dp[i-w]+v
                can2=dp[i]
                dp[i]=max(can1,can2)
            else:
                break
    print(max(dp))
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,W=map(int,input().split())
    dp=[0]*(W+1)
    for _ in range(1,N+1):
        w,v=map(int,input().split())
        for i in range(W+1)[::-1]:
            if w<=i:
                can1=dp[i-w]+v
                can2=max(dp[j] for j in range(i-w+1,i+1))
                dp[i]=max(can1,can2)
            else:
                break
    print(max(dp))
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,W=map(int,input().split())
    dp=[0]*(W+1)
    for _ in range(1,N+1):
        w,v=map(int,input().split())
        for i in range(W+1)[::-1]:
            if w<=i:
                can1=max(dp[j] for j in range(i-w+1))
                can2=max(dp[j] for j in range(i-w+1,i+1))
                dp[i]=max(can1+v,can2)
            else:
                break
    print(dp[-1])
main()

Submission status: Time Limit Exceeded

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

def chk(x):
    s = "{0:b}".format(x)
    s = s[-1::-1]
    w = 0
    v = 0
    for i in range(len(s)):
        if s[i] == '1':
            w += oj[i][0]
            v += oj[i][1]
    return w,v

ans = 0
for i in range(0, 2**N):
    w,v = chk(i)
    if w <= W and v > ans:
        ans = v
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    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):
            if w<=j:
                can1=max(dp[i-1][k] for k in range(j-w+1))
                can2=max(dp[i-1][k] for k in range(j-w+1,j+1))
                dp[i][j]=max(can1+v,can2)
            else:
                dp[i][j]=dp[i-1][j]
    print(dp[N][W])
main()

Submission status: Time Limit Exceeded

Solution code:
n, mw = map(int, input().split())
w = []
v = []

for i in range(n):
    ww, vv = map(int, input().split())
    w.append(ww)
    v.append(vv)

dp = [[0] * (mw + 1) for i in range(n + 1)]

for i in range(n):
    for j in range(mw + 1):
        if j < w[i]:
            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][mw])

Submission status: Time Limit Exceeded

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

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

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:

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

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

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

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

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)]
    wl, vl = zip(*wv)

    srs = {
        (w, -1): 0 for w in range(W+1)
    }

    def dp(w, i):
        if w - wl[i] < 0:
            return srs[(w, i-1)]
        return max(
            srs[(w - wl[i], i-1)] + vl[i],
            srs[(w, i-1)]
        )
    
    for w in range(W+1):
        for i in range(N):
            srs[(w, i)] = dp(w, i)
    
    print(srs[W, N-1])


main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in [0]*N]
dp = np.zeros((N+1,W+1),dtype = int)
for i in range(1,N+1):
    for j in range(1,W+1):
        if j < wv[i-1][0]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
def main():
    n, w = map(int, input().split())
    item = [list(map(int, input().split())) for _ in range(n)]
    dp = [0]*(w+1)
    item.sort()
    x = 0
    for i in range(n):
        for j in reversed(range(item[i][0], min(w+1, x+item[i][0]+1))):
            dp[j] = max(dp[j-item[i][0]]+item[i][1], dp[j])
        x += item[i][0]
    print(max(dp))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
def main():
    n, w = map(int, input().split())
    item = [list(map(int, input().split())) for _ in range(n)]
    dp = [0]*(w+1)
    item.sort()
    x = 0
    for i in range(n):
        for j in reversed(range(item[i][0], min(w+1, x+item[i][0]+1))):
            dp[j] = max(dp[j-item[i][0]]+item[i][1], dp[j])
        x += item[i][0]
    ans = 0
    for i in reversed(range(w+1)):
        if dp[i] > ans:
            ans = dp[i]
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
def main():
    n, w = map(int, input().split())
    item = [list(map(int, input().split())) for _ in range(n)]
    dp = [0]*(w+1)
    item.sort()
    for i in range(n):
        for j in reversed(range(item[i][0], w+1)):
            dp[j] = max(dp[j-item[i][0]]+item[i][1], dp[j])
    print(dp[w])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
def main():
    n, w = map(int, input().split())
    dp = [[0, 0]]
    item = [list(map(int, input().split())) for _ in range(n)]
    item.sort()
    for i in range(n):
        dp.sort()
        x = len(dp)
        for j in reversed(range(x)):
            p = dp[j][0] + item[i][0]
            q = dp[j][1] + item[i][1]
            if p > w:
                continue
            f = True
            for k in range(j+1, x):
                if dp[k][0] == p:
                    dp[k][1] = max(dp[k][1], q)
                    f = False
            if f:
                dp.append([p, q])
    dp.sort(key=lambda x: x[1], reverse=True)
    print(dp[0][1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, w = map(int, input().split())
    dp = {}
    dp[0] = 0
    item = [list(map(int, input().split())) for _ in range(n)]
    item.sort()
    for i in range(n):
        buf = []
        for v in dp.keys():
            if v + item[i][0] > w:
                continue
            if v + item[i][0] in dp.keys() and dp[v] + item[i][1] > dp[v+item[i][0]]:
                buf.append([v+item[i][0], dp[v] + item[i][1]])
            else:
                buf.append([v+item[i][0], dp[v] + item[i][1]])
        for j in range(len(buf)):
            dp[buf[j][0]] = buf[j][1]
    print(max(dp.values()))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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



def dp(i,w):
     if i >= n:
          return 0
     elif w - wv[i][0] < 0:
          return dp(i+1,w)
     else:
          return max(dp(i+1,w),dp(i+1,w-wv[i][0])+wv[i][1] )
print(dp(0,w))

Submission status: Time Limit Exceeded

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



def dp(i,w):
     if i >= n:
          return 0
     elif w - wv[i][0] < 0:
          return dp(i+1,w)
     else:
          return max(dp(i+1,w),dp(i+1,w-wv[i][0])+wv[i][1] )
print(dp(0,w))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10**7)
n, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]


# i番目の荷物を見たときの価値の最大値
@lru_cache(maxsize=None)
def f(i, r):
    w, v = wv[i]
    if i == 0:
        if w <= r:
            return v
        else:
            return 0
    if w <= r:
        return max(f(i-1, r), f(i-1, r-w) + v)
    else:
        return f(i-1, r)


print(f(n-1, W))

Submission status: Time Limit Exceeded

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

#dp = [[0] * (W+1+max([w for w,v in WV])) for _ in range(N+1)]
dp = [[0] * (W+1) for _ in range(N+1)]

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

print(max(dp[N]))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
def KnapSack(val, wt, n, W): 
      
    # matrix to store final result  
    mat = [[0 for i in range(W + 1)]  
              for i in range(2)] 
    # iterate through all items  
    i = 0
    while i < n: # one by one traverse  
                 # each element  
        j = 0 # traverse all weights j <= W 
          
        # if i is odd that mean till  
        # now we have odd number of  
        # elements so we store result   
        # in 1th indexed row  
        if i % 2 == 0: 
            while j < W: # check for each value  
                j += 1
                if wt[i] <= j: # include element  
                    mat[1][j] = max(val[i] + mat[0][j - 
                                     wt[i]], mat[0][j]) 
                else: # exclude element 
                    mat[1][j] = mat[0][j] 
                      
        # if i is even that mean till  
        # now we have even number  
        # of elements so we store  
        # result in 0th indexed row  
        else: 
            while j < W: 
                j += 1
                if wt[i] <= j: 
                    mat[0][j] = max(val[i] + mat[1][j - 
                                     wt[i]], mat[1][j]) 
                else: 
                    mat[0][j] = mat[1][j] 
        i += 1
    # Return mat[0][W] if n is  
    # odd, else mat[1][W]  
    if n % 2 == 0: 
        return mat[0][W] 
    else: 
        return mat[1][W] 
  
# Driver code
n,W = map(int,input().split())
val = [] 
wt = []  
for i in range(n):
    a,b = map(int,input().split())
    val.append(b)
    wt.append(a)
    
print(KnapSack(val, wt, n, W))

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


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):
        wi = wv[i - 1][0]
        vi = wv[i - 1][1]

        if j - wi >= 0:
            dp[i][j] = max([
                dp[i][j - 1],
                dp[i - 1][j - wi] + vi
            ])
            
        dp[i][j] = max([
            dp[i - 1][j],
            dp[i][j]
        ])

print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
wv = []
for i in range(n):
    wv_ = list(map(int, input().split()))
    wv.append(wv_)
dp = [0]*(w+1)
for i in range(n):
    for j in range(w, wv[i][0]-1, -1):
        dp_ = dp[j - wv[i][0]] + wv[i][1]
        if dp[j] < dp_:
            dp[j] = dp_
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
# def LIST(): return list(map(str, input().split()))
# def LIST(): return list(input())

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, W = MAP()
L = [LIST() for _ in range(N)]

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

print(dp[N][W])

Submission status: Time Limit Exceeded

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

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 i in range(N)]
f_min = 0 
dp = [[f_min] * (W+1) for _ in range(N+1)]
def chmin(a, b):
    if a > b:
        return b
    else:
        return a
def chmax(a,b):
    if a < b:
        return b
    else:
        return a
def main():
    # 初期条件

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

        for sum_w in range(W+1):
            if sum_w - w >= 0:
                dp[i][sum_w] = chmax(dp[i][sum_w], dp[i-1][sum_w-w]+ v)
            
            dp[i][sum_w] = chmax(dp[i][sum_w],dp[i-1][sum_w])
    
    ans = 0
    for i in range(W+1):
        ans = chmax(ans,dp[N][i])
    print(ans)
            

            
 

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N, M = map(int, input().split())
    A = [list(map(int, input().split())) for i in range(N)]
    dp = [[0] * (M+1) for i in range(N+1)]
    
    for i in range(N):
        for s in range(M+1):
            a, b = A[i]
            if s-a >= 0:
                dp[i+1][s] = max(dp[i+1][s], dp[i][s-a] + b)
            dp[i+1][s] = max(dp[i+1][s], dp[i][s])
    return dp[N][M]

print(solve())

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

Submission status: Time Limit Exceeded

Solution code:
def knapsack_1(N, W, lst):
    #N : 品物数
    #W : 重みの総和
    #lst (wi,vi) : 商品iの重みwi、価値vi
    
    #dp[i][j] : i番目の品物から重さの総和がj以下になるように選んだ場合の価値の総和の最大値
    dp = [[0 for i in range(W+1)] for _ in range(N+1)]
    
    for i in range(N):
        for j in range(W+1):
            if j < lst[i][0]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = max(dp[i][j],dp[i][j - lst[i][0]] + lst[i][1])
    return dp[N][W]


n,w = map(int,input().split())
lst = []
for i in range(n):
    w_, v_ =  map(int,input().split())
    lst.append((w_, v_))
print(knapsack_1(n,w,lst))