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 = [list(map(int, input().split())) for i in range(N)]

w = [w_v[i][0] for i in range(N)]
v = [w_v[i][1] for i in range(N)]

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

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

Submission status: Time Limit Exceeded

Solution code:
nw=list(map(int, input().split(" ")))
dp=[[0]*(nw[1]+1) for _ in range(nw[0]+1)]
w=[]
v=[]
i=0
ww=0
for _ in range(nw[0]):
    wv=list(map(int, input().split(" ")))
    w.append(wv[0])
    v.append(wv[1])
for i in range(nw[0]):
    for ww in range(nw[1]+1):
        if w[i] <= ww:
            dp[i+1][ww]=max(dp[i+1][ww], dp[i][ww-w[i]]+v[i])
        dp[i+1][ww]=max(dp[i+1][ww], dp[i][ww])
print(dp[nw[0]][nw[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 = [list([0] * (W+1)) for _ in range(N)]
    dp[0][wv[0][0]] = wv[0][1]

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

    print(max(dp[-1]))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)

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

weight = []
v = []
dp = []

for _ in range(N):
    weight1,v1 = map(int, input().split())
    weight.append(weight1)
    v.append(v1)
    dp.append([-1]*(W+1))

def dfs(n, w):#wの容量でn番目までの商品で最大価値
    global N
    global W
    if n==0:
        if(w-weight[n]>=0):
            return v[n]
        else:
            return 0
    if dp[n][w]!=-1:
        return dp[n][w]

    if (w-weight[n])>=0:
        ret = max(dfs(n-1, w), dfs(n-1, w-weight[n])+v[n])
    else:
        ret = dfs(n-1, w)#選択肢ないので、これを選ばない
    dp[n][w] = ret
    return ret

print(dfs(N-1,W))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)

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

weight = []
v = []

for _ in range(N):
    weight1,v1 = map(int, input().split())
    weight.append(weight1)
    v.append(v1)

def dfs(n, w):#wの容量でn番目までの商品で最大価値
    global N
    global W
    if n==0:
        if(w-weight[n]>=0):
            return v[n]
        else:
            return 0
    if (w-weight[n])>=0:
        ret = max(dfs(n-1, w), dfs(n-1, w-weight[n])+v[n])
    else:
        ret = dfs(n-1, w)#選択肢ないので、これを選ばない
    return ret

print(dfs(N-1,W))

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, W = map(int, input().split())
    wv = [tuple(map(int, input().split())) for i in range(N)]

    dp = [-1]*(W+1)
    dp[0] = 0
    for w, v in wv:
        for j in range(W-w, -1, -1):
            if dp[j] >= 0 and j+w <= W and dp[j+w] < dp[j]+v:
                dp[j+w] = dp[j] + v

    print(max(dp))


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, W = map(int, input().split())
    wv = [tuple(map(int, input().split())) for i in range(N)]

    dp = [-1]*(W+1)
    dp[0] = 0
    for w, v in wv:
        for j in range(W-1, -1, -1):
            if dp[j] >= 0 and j+w <= W and dp[j+w] < dp[j]+v:
                dp[j+w] = dp[j] + v

    print(max(dp))


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, W = map(int, input().split())
    wv = [tuple(map(int, input().split())) for i in range(N)]

    dp = [-1]*(W+1)
    dp[0] = 0
    for w, v in wv:
        for j in range(W-1, -1, -1):
            if dp[j] >= 0 and j+w <= W:
                dp[j+w] = max(dp[j+w], dp[j] + v)

    print(max(dp))


main()

Submission status: Time Limit Exceeded

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

    dp = [-1]*(W+1)
    dp[0] = 0
    for w, v in wv:
        for j in range(W-1, -1, -1):
            if dp[j] >= 0 and j+w <= W:
                dp[j+w] = max(dp[j+w], dp[j] + v)

    print(max(dp))


main()

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

Submission status: Time Limit Exceeded

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

x, y  = map(int, input().split())
li =[]
for i in range(x):
    l = list(map(int, input().split()))
    li.append(l)
dp = [[0]*(y+1) for _ in range(x+1)]
for i in range(x):
    for j in range(1, y+1):
        if j - li[i][0] >= 0:
            dp[i+1][j] = max(dp[i][j],dp[i][j - li[i][0] ]+ li[i][1])
        else:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
print(dp[x][y])

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
import copy
dp = [0]*(W+1)
for _ in range(N):
    dpc = copy.deepcopy(dp)
    w,v = map(int,input().split())
    if w > W:
        continue
    else:
        for j in range(w,W+1):
            if dpc[j] < dpc[j-w]+v:
                dp[j] = dpc[j-w]+v
print(dp[W])

Submission status: Time Limit Exceeded

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

dp = [[0 for _ in range(W)] for _ in range(N + 1)]
weight = []
value = []
for _ in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

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

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
n,W = map(int,input().split())
vw=[list(map(int,input().split())) for i in range(n)]
v=[vw[i][1] for i in range(n)]
w=[vw[i][0] for i in range(n)]
dp = [[0]*(W+1) for j in range(n+1)]

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def rec(n, w, ws, vs, dp):
    if w == 0 or n < 0:
        return 0
    if dp[n][w] > -1:
        return dp[n][w]
    if ws[n] <= w:
        dp[n][w] = max(dp[n][w], rec(n-1, w-ws[n], ws, vs, dp) + vs[n])
    dp[n][w] = max(dp[n][w], rec(n-1, w, ws, vs, dp))
    return dp[n][w]

def resolve():
    n, w = map(int, input().split())
    ws, vs = [0]*n, [0]*n
    for i in range(n):
        ws[i], vs[i] = map(int, input().split())
    dp = [[-1] * (w + 1) for _ in range(n + 1)]
    print(rec(n-1, w, ws, vs, dp))
resolve()

Submission status: Time Limit Exceeded

Solution code:
def rec(n, w, ws, vs, dp):
    if w == 0 or n < 0:
        return 0
    if ws[n] <= w:
        dp[n][w] = max(dp[n][w], rec(n-1, w-ws[n], ws, vs, dp) + vs[n])
    dp[n][w] = max(dp[n][w], rec(n-1, w, ws, vs, dp))
    return dp[n][w]

def resolve():
    n, w = map(int, input().split())
    ws, vs = [0]*n, [0]*n
    for i in range(n):
        ws[i], vs[i] = map(int, input().split())
    dp = [[-1] * (w + 1) for _ in range(n + 1)]
    print(rec(n-1, w, ws, vs, dp))
resolve()

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def solve(ls, n, w):
	dp = [0] * (w + 1)
	for item in range(n):
		for weight in range(w, ls[item][0] - 1, -1):
			dp[weight] = max(dp[weight], dp[weight - ls[item][0]] + ls[item][1])
	return dp[w]


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

print(solve(ls, n, w))

Submission status: Time Limit Exceeded

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

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

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

npsk_1(N, W)

Submission status: Time Limit Exceeded

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

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

npsk_1(N, W)

Submission status: Time Limit Exceeded

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

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

dp = [[0]*(W+1) for _ in range(N+1)]
    
def npsk_1(N, W):
    for i in range(N):
        for j in range(W+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] = dp[i][j]
    
    print(dp[N][W])

npsk_1(N, W)

Submission status: Time Limit Exceeded

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

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

dp = [[0]*(W+1) for _ in range(N+1)]
    
def npsk_1(N, W):
    for i in range(N):
        for j in range(W+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] = dp[i][j]
    
    print(dp[-1][-1])

npsk_1(N, W)

Submission status: Time Limit Exceeded

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

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

npsk_1(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][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())
L = []
for _ in range(N):
    l = list(map(int,input().split()))
    L.append(l)
dp = [[0 for _ in range(W + 10)] for _ in range(N + 10)]
for i in range(N):
    for w in range(W+1):
        if w+L[i][0] <= W:
            dp[i+1][w+L[i][0]] =max(dp[i][w]+L[i][1], dp[i+1][w+L[i][0]])
        dp[i+1][w] = max(dp[i][w], dp[i+1][w])
ans = 0
for w in range(W+1):
    ans = max(ans,dp[N][w])
print(ans)

Submission status: Time Limit Exceeded

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

def solve(w,v):
    dp = [[0]*(W+1) for i in range(N+1)]
    for i in range(1,N+1):
        for j in range(W+1):
            if j < w[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])
    ans = dp[-1][-1]
    return ans
print(solve(w,v))

Submission status: Time Limit Exceeded

Solution code:

def solve(N, W, arr):
	
	dp = [0] * (W + 1)
	for i in range(1, N + 1):
		dp2 = [0] * (W + 1)
		for j in range(1, W + 1):
			weight, value = arr[i-1]
			if j - weight >= 0:
				dp2[j] = max(value + dp[j-weight], dp[j])
			else:
				dp2[j] = dp[j]
		dp = dp2

	return dp[-1]



N, W = [int(s) for s in input().split()]
arr = []
for _ in range(N):
	arr.append([int(s) for s in input().split()])
print(solve(N, W, arr))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
WV = [tuple(map(int, input().split())) for i in range(n)]
W = [w for w, v in WV]
V = [v for w, v in WV]
DP = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(n):
    for j in range(W[i]):
        DP[i+1][j] = DP[i][j]
    for j in range(W[i], m+1):
        DP[i+1][j] = max(DP[i][j], DP[i][j-W[i]]+V[i])
print(DP[n][m])

Submission status: Time Limit Exceeded

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------

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

#p(WV)

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

#print(dp)

for iN in range(1,N+1):
	w,v = WV[iN]
	for iW in range(W+1):
		
		v0 =     dp[iN-1][iW]
		v1 = v + dp[iN-1][iW-w] if iW-w>=0 else 0
		#p("w,v,v0,v1, ",w,v,v0,v1)
		
		dp[iN][iW] = max(v0, v1)

#p(dp)

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

Submission status: Time Limit Exceeded

Solution code:
def knapsack(n,w,wts,vals):
    if n==0 or w==0:
        return 0
    inc,exc=-1,-1
    if wts[n-1]<=w:
        inc= vals[n-1]+ knapsack(n-1,w-wts[n-1],wts,vals)
    exc= knapsack(n-1,w,wts,vals)

    return max(inc,exc)

n,w=map(int,input().split())
wts,vals=[],[]
for i in range(n):
    a,b=map(int,input().split())
    wts.append(a)
    vals.append(b)

print(knapsack(n,w,wts,vals))

Submission status: Time Limit Exceeded

Solution code:
def rec(i, j):
    if dp[i][j]:
        return dp[i][j]
    if i == n:
        res = 0
    elif j < w[i]:
        res = rec(i + 1, j)
    else:
        res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i])
    dp[i][j] = res
    return res
n, W = 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] * (W + 1) for i in range(n + 1)]
print(rec(0, 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):
  w,v=map(int,input().split())
  for j in range(1,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:
def main():
    N, W = list(map(int, input().split()))
    DP = [[0 for i in range(W+1)] for j in range(N+1)]
    for i in range(N):
        w, v = list(map(int, input().split()))
        for sum_w in range(W+1):
            if sum_w - w >= 0:
               DP[i+1][sum_w] = max(DP[i][sum_w],DP[i][sum_w-w]+v)
            DP[i+1][sum_w] = max(DP[i+1][sum_w],DP[i][sum_w])
    print(max(DP[-1]))

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

Submission status: Time Limit Exceeded

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

import numpy as np
N,W = map(int,input().split())
WV = [(list(map(int,input().split()))) for _ in range(N)]
DP = np.array([[0]*(W+1) for _ in range(N+1)], dtype=np.int64)

def rec(i,w,v):
    if DP[i][w] != 0:
        return DP[i][w]
    if i == N:
        return v
    if w == 0:
        return v
    else:
        res = rec(i+1,w,v)
        if w-WV[i][0] >= 0:
            res = max(res,rec(i+1,w-WV[i][0],v+WV[i][1]))
        DP[i][w] = res
        return DP[i][w]

rec(0,W,0)
print(np.max(DP))

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
dp = [[0]*(W+1) for _ in range(N+1)]
WV = []
for _ in range(N):
  w,v = map(int,input().split())
  WV.append([w,v])
for i in range(N):
  for w in range(W+1):
    if w >= WV[i][0]:
      dp[i+1][w] = max(dp[i][w -WV[i][0]]+WV[i][1],dp[i][w])
    else:
      dp[i+1][w] = dp[i][w]
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):
  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[-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(n):
    weight,value = map(int,input().split())
    for j in range(w+1):
        if j >= weight:
            dp[i+1][j] = max(dp[i][j-weight]+value,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())
k,l = 0,0
lv = [0] * N
lw = [0] * N
for i in range(N):
    lw[i],lv[i] = map(int,input().split())
V = sum(lv)
dp = [[float("inf") for i in range(V+1)] for j in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for sv in range(V):
        if sv-lv[i] < 0:
            dp[i+1][sv] = dp[i][sv]
            k +=1
        else:
            dp[i+1][sv] = min(dp[i][sv],(dp[i][sv-lv[i]]+lw[i]))
            l += 1
a = V

while a >= 0:
    if dp[-1][a] <= W:
        print(a)
        a = -1
    else:
        a -= 1

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def main():
  N,W = map(int,input().split())  #nは入力回数
  num_list = [list(map(int, input().split())) for _ in range(N)]
  dp=np.zeros((N+1,W+1))
  weight=[row[0] for row in num_list]
  value=[row[1] for row in num_list]
  for i in range(0,N):
    for sum_w in range(0,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])
      #iを選ばない場合
      dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w])
  print(int(dp[N][W]))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
def rec(i,j):
    res=0
    if(dp[i][j]>=0):
        return dp[i][j]
    if(i==n):
        res=0
    elif(j<w[i]):
        res=rec(i+1,j)
    else:
        res=max(rec(i+1,j),rec(i+1,j-w[i])+v[i])
    dp[i][j]=res
    return res
n,x=map(int,input().split())
dp=[[-1]*(x+10) for i in range(n+10)]
w,v=[],[]
for i in range(n):
    a,b=map(int,input().split())
    w.append(a);v.append(b)
print(rec(0,x))

Submission status: Time Limit Exceeded

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

dp=np.zeros((n+1,w+1),np.int64)
# dp[i][j]:重さjを超えないようにしながらi個目までの商品を取るか取らないか選んだ時の価値の最大
# dp[i][0]=0,dp[0][j]=0,dp[n][inf]=sum(v) 求めるのはdp[n][w]
# 重さの小さい方から探索
for j in range(1,w+1):
      for i in range(1,n+1):
            m1=dp[i-1][j]
            m2=dp[i-1][j-wv[i-1][0]]+wv[i-1][1] if j-wv[i-1][0]>=0 else 0
            dp[i][j]=max(m1,m2)
            
print(dp[n][w])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()

def main():

    # i have too make index as weight and value as value
    size, total_weight = map(int, input().split())
    dp = [0] * (total_weight+1)
    for _ in range(size):
        weight, val = map(int, input().split())
        for i in range(total_weight - weight, -1, -1):
            dp[weight + i] = max(dp[weight + i], dp[i] + val)
    ans = 0
    for i in range(total_weight+1):
        ans = max(ans, dp[i])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#全探索　
N,W = (int(x) for x in input().split())
w_v ={}
for id in range(0, N):
    w_v[id] = tuple(int(x) for x in input().split())  #w,vに名前を付けた。0,1,2・・・N-1

#順列
from itertools import combinations
name_all  =[i for i in range(N)] #全ての名前
mono_kumiawase =set()
w_kumiawase_ok =[]
w_kumiawase_batu =[]
v_kumiawase_ok =[]
for num_in in range(1,N+1):
    for t in combinations(name_all, num_in):
        mono_kumiawase.add(t) #１つ選んだ時の組み合わせ～N個選んだ時の組み合わせ
        #print(len(t),end=" ")
        w_sum =0
        v_sum =0
        for i in t:
            w_sum += w_v[i][0]
            v_sum += w_v[i][1]
        if w_sum <= W:
            w_kumiawase_ok.append(w_sum)
            v_kumiawase_ok.append(v_sum)
        else:
            w_kumiawase_batu.append(w_sum)
print(max(v_kumiawase_ok))

Submission status: Time Limit Exceeded

Solution code:
import sys

def input():
    return sys.stdin.readline().strip()

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

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

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

if __name__ == "__main__":
    main()

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 for _ in range(W+1)] for _ in range(N+1)]

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

Submission status: Time Limit Exceeded

Solution code:
"""
https://qrunch.net/@koralle/entries/QaGGA1m4l6NALqLX
投稿日：2019-12-20   最終更新：2019-12-20
"""
N,W = (int(x) for x in input().split())
wv = [tuple(map(int, input().split())) for i in range(0, N) ]  

def rec(n, uplimit_w):  
  ans = 0  
  if n == N:  
    return 0  

  # n番目の品物を使えない場合   
  elif wv[n][0] > uplimit_w:  
    return rec(n + 1, uplimit_w)  

  # n番目の品物が使える時  
  # -> n番目の品物は使った方がいいのか、使わない方がいいのか...?  
  else:  
    ans = max(  
      rec(n + 1, uplimit_w),  
      rec(n + 1, uplimit_w - wv[n][0]) + wv[n][1]  
    )  
    return ans  

  
print(rec(0, 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(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(dp[N][W])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    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)

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

    for i in range(n):
        for w1 in range(W+1):
            if w1 >= weight[i]:
                dp[i+1][w1] = max(dp[i][w1-weight[i]] + value[i], dp[i][w1])
            else:
                dp[i+1][w1] = dp[i][w1]

    print(dp[n][W])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
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)

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

for i in range(n):
    for w1 in range(W+1):
        if w1 >= weight[i]:
            dp[i+1][w1] = max(dp[i][w1-weight[i]] + value[i], dp[i][w1])
        else:
            dp[i+1][w1] = dp[i][w1]

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

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N, W = map(int, input().split())
    w = [0]
    v = [0]
    for i in range(N):
        weight, value = map(int, input().split())
        w.append(weight)
        v.append(value)

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


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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

        # dp = new_dp

    print(dp[-1])











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


3 8
3 30
4 50
2 60
"""

Submission status: Time Limit Exceeded

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

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

#print(dp)

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


print(dp[-1][-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] * (W + 1) for _ in range(N + 1)]

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
N_W=list(map(int,input().split()))
N=N_W[0]
W=N_W[1]
items=[]
for i in range(N):
	sets=list(map(int,input().split()))
	items.append(sets)
knapsack=[[0 for i in range(W+1)] for j in range(N+1)]

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

Submission status: Time Limit Exceeded

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

# dp用配列
dp=[]
for k in range(N+1):
    dp.append([0]*(W+1))


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

# print(*dp,sep="\n")

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

Submission status: Time Limit Exceeded

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

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

for n in range(1,N+1):
  for w in range(1,W+1):
    if wl[n-1]<=w:
      dp[n][w]=max(dp[n-1][w-wl[n-1]]+vl[n-1],dp[n-1][w])
    else:
      dp[n][w]=dp[n-1][w]

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

Submission status: Time Limit Exceeded

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