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^9

1 \leq w_i \leq W

1 \leq v_i \leq 10^3

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

1 1000000000
1000000000 10

Sample Output 2

10

Sample Input 3

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

Sample Output 3

17

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



Sample input:
3 8
3 30
4 50
5 60


Sample output:
90

Submission status: Time Limit Exceeded

Solution code:
dp = {}
wt = []
val = []
def solve(idx, W):
    if W == 0 or idx == 0:
        return 0
    if (idx, W) in dp:
        return dp[(idx, W)]
    if wt[idx-1] > W:
        dp[(idx, W)] = solve(idx-1, W)
        return dp[(idx, W)]
    dp[(idx, W)] = max(val[idx-1]+solve(idx-1,W-wt[idx-1]), solve(idx-1, W))
    return dp[(idx, W)]
n, w = map(int, input().split())
for i in range(n):
    a, b = map(int, input().split())
    wt.append(a)
    val.append(b)
print(solve(n, w))

Submission status: Time Limit Exceeded

Solution code:
n=0
W=0
n,W=map(int,input().split())
dp=[W+1]*(101010)
dp[0]=0
for i in range(n):
    w,v=map(int,input().split())
    j=100000
    while j>=0:
        if dp[j+v]>dp[j]+w:
            dp[j+v]=dp[j]+w
        j-=1
ans=0
for v in range(len(dp)):
    if dp[v]<=W:
        ans=v
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, max_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 for _ in range(max_w+1)] for _ in range(n+2)]

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

print(max(dp[n]))

Submission status: Time Limit Exceeded

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

INF = float('inf')
ww = [0]*n
vv = [0]*n
vm = 1000
dp = [[INF]*(n*vm+1) for _ in range(n+1)]

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

dp[0][0] = 0  
for i in range(1,n+1):
  dp[i][0] = 0
  for j in range(1,n*vm+1):        
    if j < vv[i-1]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = min(dp[i-1][j], dp[i-1][j-vv[i-1]] + ww[i-1])        

ans = 0
for i in range(n*vm+1):
  if dp[n][i]<=w:
    ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
l1 = [list(map(int, input().split())) for i in range(n)]
v = 0
for i in range(n):
  v += l1[i][1]
d = [10 ** 9 + 1] * (v + 1)
d[0] = 0
for i in range(n):
    for j in range(v, -1, -1):
        d[j] = min(d[j], d[j - l1[i][1]] + l1[i][0])
answer = 0
for j in range(v + 1):
    if  w >= d[j]:
        answer = max(answer, j)
print(answer)

Submission status: Time Limit Exceeded

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

# ナップザック問題 典型2
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(N)]
V = sum([v for w, v in wv])

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

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

ans = 0
for i in range(0, V+1):
    if dp[N][i] <= W:
        ans = i

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())
vmax = max(v)
dp = [[0]*(N * vmax + 1) for i in range(N + 1)]
dp[0][0] = 0
for j in range(N * vmax):
    dp[0][j + 1] = float("inf")

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

ans = 0
for j in range(N * vmax + 1):
    if dp[N][j] <= W:
        ans = j
print(ans)

Submission status: Time Limit Exceeded

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

value = [[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(W + 1):
        if j - w >= 0:
            value[i][j] = max(value[i-1][j-w] + v, value[i-1][j])
        else:
            value[i][j] = value[i-1][j]

print(value[N][W])

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
INF = 10 ** 9 + 7
wvLst = [list(map(int, input().split())) for _ in range(N)]
dp = [[INF for i in range(10 ** 5 + 1)] for _ in range(N + 1)]

dp[0][0] = 0
for i in range(N):
    for j in range(10 ** 5 + 1):
        if j - wvLst[i][1] >= 0:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - wvLst[i][1]] + wvLst[i][0])
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
ans = 0
for i in range(10 ** 5 + 1):
    if dp[N][i] <= W:
        ans = i

print(ans)

Submission status: Time Limit Exceeded

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

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

for i in range(N):
    for sum_w in range(W+1):
        # i 番目の品物を選ぶ場合
        if sum_w >= weight[i]:
            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(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
goods = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i, item in enumerate(goods):
    i += 1
    for w in range(1, W+1):
        if w < item[0]:
            dp[i][w] = dp[i-1][w]
        else:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w-item[0]] + item[1])

print(dp[N][W])

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)
 
inf=float("inf")
dp=[[-inf for i in range(W+1)] for j in range(N+1)]
for i in range(W+1): dp[0][i]=0
 
for n in range(N):
    for w in range(W+1):
        if w>=weight[n]:
            dp[n+1][w] = max(dp[n][w-weight[n]]+value[n], dp[n][w])
        else:
            dp[n+1][w] = dp[n][w]
 
 
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
lwv=[]
for i in range(N):
    lwv.append(list(map(int,input().split())))
ldp=[[float("inf") for j in range(10**5)] for i in range(N)]
for j in range(10**5):
    if lwv[0][1]>=j+1:
        ldp[0][j]=lwv[0][0]
for i in range(1,N):
    for j in range(10**5):
        comp=ldp[i-1][j+1-lwv[i][1]-1]+lwv[i][0] if j+1-lwv[i][1]>0 else lwv[i][0]
        ldp[i][j]=min(ldp[i-1][j],comp)
for j in range(10**5-1,-1,-1):
    if ldp[N-1][j]<=W:
        print(j+1)
        break

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
lwv=[]
for i in range(N):
    lwv.append(list(map(int,input().split())))
#ldp=[[float("inf") for j in range(10**5+1)] for i in range(N)]
ldp=[[float("inf") for j in range(10**5)] for i in range(N)]
#for j in range(10**5+1):
for j in range(10**5):
    #if lwv[0][1]>=j:
    if lwv[0][1]>=j+1:
        ldp[0][j]=lwv[0][0]
for i in range(1,N):
    #for j in range(10**5+1):
    for j in range(10**5):
        #if j-lwv[i][1]>=0:
            #comp=ldp[i-1][j-lwv[i][1]]+lwv[i][0]
            #ldp[i][j]=min(ldp[i-1][j],ldp[i-1][j-lwv[i][1]]+lwv[i][0])
        #else:
            #ldp[i][j]=ldp[i-1][j]
        #comp=ldp[i-1][j-lwv[i][1]]+lwv[i][0] if j-lwv[i][1]>=0 else lwv[i][0]
        comp=ldp[i-1][j+1-lwv[i][1]-1]+lwv[i][0] if j+1-lwv[i][1]>0 else lwv[i][0]
        ldp[i][j]=min(ldp[i-1][j],comp)
#print(ldp[N-1][90])
#print(ldp[N-1][:91])
#print(ldp[0][:91])
#print(ldp[1][:91])

#for j in range(10**5,0,-1):
for j in range(10**5-1,-1,-1):
    if ldp[N-1][j]<=W:
        #print(j)
        print(j+1)
        break

Submission status: Time Limit Exceeded

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

dp = [[float('inf') for i in range(sumv+1)] for j in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
for i in range(N):
    for j in range(sumv+1):
        if j - wv[i][1] >=0 :
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]] + wv[i][0])
        else:
            dp[i+1][j] = dp[i][j]

for i in range(sumv,-1,-1):
    if dp[-1][i] <= W:
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:

N,W = map(int,input().split())
wv = []
for i in range(N):
    a = list(map(int,input().split()))
    wv.append(a)
sumv = sum([i[1] for i in wv])

dp = [[float('inf') for i in range(sumv+1)] for j in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
for i in range(N):
    for j in range(sumv+1):
        if j - wv[i][1] >=0 :
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]] + wv[i][0])
        else:
            dp[i+1][j] = dp[i][j]
maxb = []
for j in range(N+1):
    for i in range(sumv,-1,-1):
        if dp[j][i] <= W:
            maxb.append(i)
            break
print(maxb[-1])

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
N,W = map(int,input().split())
wv = []
for i in range(N):
    a = list(map(int,input().split()))
    wv.append(a)
sumv = sum([i[1] for i in wv])

dp = [[float('inf') for i in range(sumv+1)] for j in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
for i in range(N):
    for j in range(sumv+1):
        if j - wv[i][1] >=0 :
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]] + wv[i][0])
        else:
            dp[i+1][j] = dp[i][j]
maxb = []
for j in range(N+1):
    for i in range(sumv,-1,-1):
        if dp[j][i] <= W:
            maxb.append([j,i])
            break
print(maxb[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
WV = [[0,0]] + [list(map(int,input().split())) for _ in range(N)]
vrng = (10**3)*N+1
dp = [[float('inf') for _ in range(vrng)] for _ in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
  tmpw, tmpv = WV[i]
  for j in range(vrng):
    if j-tmpv>=0:
      dp[i][j] = min(dp[i-1][j],dp[i-1][j-tmpv]+tmpw)
    else:
      dp[i][j] = dp[i-1][j]

ans = -float('inf')
for row in dp:
  for j,w in enumerate(row):
    if w<=W and ans<j:
      ans = j
print(ans)

Submission status: Time Limit Exceeded

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

def knapsack(W, wt, val, n):
    # Base Case 
    if n == 0 or W == 0 : 
        return 0
  
    # If weight of the nth item is more than Knapsack of capacity 
    # W, then this item cannot be included in the optimal solution 
    if (wt[n-1] > W): 
        return knapsack(W , wt , val , n-1) 
  
    # return the maximum of two cases: 
    # (1) nth item included 
    # (2) not included 
    else: 
        return max(val[n-1] + knapsack(W-wt[n-1] , wt , val , n-1), 
                   knapsack(W , wt , val , n-1))
def main():
    lines = []
    for line in sys.stdin:
        lines.append([int(i) for i in line.strip().split(' ')])
    n = lines[0][0]
    w = lines[0][1]
    
    wt = np.array(lines[1:])[:,0]
    val = np.array(lines[1:])[:,1]
    print(knapsack(w, wt, val, n))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

dp = [0] + [float("inf")]*(10**5)
for i in range(n):
    for j in range(10**5,wv[i][1]-1,-1):
        dp[j] = min(dp[j],dp[j-wv[i][1]]+wv[i][0])

res = 0
for v,e in enumerate(dp):
    if e <= w:
        res = v
print(res)

Submission status: Time Limit Exceeded

Solution code:
# Knapsack_2
N, W = map(int, input().split())
w,v = [],[]
for i in range(N):
	wi,vi = map(int, input().split())
	w.append(wi)
	v.append(vi)
	
def mymin(a,b):
	if a < b:
		return a
	else:
		return b
		
total_val = sum(v)

INF = 1e+9
dp = [[INF]*(total_val+1) for i in range(N+1)]

for i in range(N+1):
	dp[i][0] = 0
	
for vi in range(1, total_val+1):
	for i in range(1,N+1):
		if vi >= v[i-1]:
			dp[i][vi] = mymin(dp[i-1][vi], dp[i-1][vi-v[i-1]]+w[i-1])
		else:
			dp[i][vi] = dp[i-1][vi]

ans = 0
for vi in range(1,total_val+1):
	if dp[N][vi] <= W:
		ans = vi
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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[i][j]:i番目まで選んで、価値がj以上となる最小の重さ
dp=[[10**10]*(sum(v)+1) for i in range(n+1)]
dp[0][0]=0
for i in range(n):
    for j in range(sum(v)+1):
        if j>=v[i]:
            dp[i+1][j]=min(dp[i][j-v[i]]+w[i],dp[i][j])
        else:
            dp[i+1][j]=dp[i][j]
ans=[]
for i in range(sum(v)+1):
    if dp[n][i]<=W:
        ans.append(i)
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    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())
    v_max = sum(v)
    dp = [[0 if i == 0 else float("inf") for i in range(v_max+1)] for _ in range(N)]
    dp[0][v[0]] = w[0]
    for i in range(1,N):
        for j in range(v_max+1):
            if j<v[i]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
    ans = 0
    for i in range(v_max+1):
        if dp[-1][i]<=W:
            ans = i
        else:
            pass
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    # input
    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())
    
    # init dp
    v_max = sum(v)
    dp = [[float("inf") for i in range(v_max+1)] for _ in range(N)]
    dp[0][v[0]] = w[0]
    for i in range(N):
        dp[i][0] = 0

    for i in range(1,N):
        for j in range(v_max+1):
            if j<v[i]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
    ans = 0
    for i in range(v_max+1):
        if dp[-1][i]==float("inf"):
            pass
        elif dp[-1][i]<=W:
            ans = i
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    # input
    N,W = map(int,input().split())
    w,v = [0 for _ in range(N)],[0 for _ in range(N)]
    for i in range(N):
        w[i],v[i] = map(int,input().split())
    
    # init dp
    v_max = sum(v)
    dp = [[float("inf") for i in range(v_max+1)] for _ in range(N)]
    dp[0][v[0]] = w[0]
    for i in range(N):
        dp[i][0] = 0

    for i in range(1,N):
        for j in range(v_max+1):
            if j<v[i]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
    ans = 0
    for i in range(v_max+1):
        if dp[-1][i]==float("inf"):
            pass
        elif dp[-1][i]<=W:
            ans = i
        else:

            pass
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    # input
    N,W = map(int,input().split())
    w,v = [0 for _ in range(N)],[0 for _ in range(N)]
    for i in range(N):
        w[i],v[i] = map(int,input().split())
    
    # init dp
    v_max = 10**5
    dp = [[float("inf") for i in range(v_max+1)] for _ in range(N)]
    dp[0][v[0]] = w[0]
    for i in range(N):
        dp[i][0] = 0

    for i in range(1,N):
        for j in range(v_max+1):
            if j<v[i]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
    ans = 0
    for i in range(v_max+1):
        if dp[-1][i]==float("inf"):
            pass
        elif dp[-1][i]<=W:
            ans = i
        else:

            pass
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# # Educational DP Contest E
# 方針：dp[i][v] := i-1番目までの物の中から，価値v以上を達成するように選んだ時の重さの最小値

# 入力
N, W = map(int, input().split())
weight = [0] * N
value = [0] * N
for i in range(N):
    w, v = map(int, input().split())
    weight[i] = w
    value[i] = v

# DPテーブル
max_v = sum(value)
dp = [[float("inf")] * (max_v + 1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for v in range(max_v+1):
        if v >= value[i]:       # i番目の物を選ぶ時
            dp[i+1][v] = min(dp[i][v - value[i]] + weight[i], dp[i][v])
        else:
            dp[i+1][v] = dp[i][v]

for v in range(max_v, -1, -1):
    if dp[N][v] <= W:
        ans = v
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
dp = [[float("inf")] * (10**5 + 1) for i in range(N+1)]
dp[0][0] = 0

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

ans = 0
for i in range(10**5 + 1):
  if dp[-1][i] <= W:
    ans = i
print(ans)

Submission status: Time Limit Exceeded

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

  #DP
  for i in range(N):
    for w in range(W+1):
      if wv[i][0]<=w: #dp[i][w-wv[i][0]]の状態にi番目の荷物が入る可能性がある
        dp[i+1][w]=max(dp[i][w-wv[i][0]]+wv[i][1], dp[i][w])
      else: #入る可能性はない
        dp[i+1][w]=dp[i][w]
  return dp[N][W]

if __name__ == "__main__":
  N, W = map(int, input().split())
  wv = [list(map(int, input().split())) for i in range(N)]
  ans = knapsack(N, W, wv)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
inf=float("inf")
DP=[[-inf for i in range(W+1)] for j in range(N+1)]
for i in range(W+1):DP[0][i]=0
for i in range(N):
    wi,v=map(int,input().split())
    for w in range(W+1):
        if wi<=w:DP[i+1][w]=max(DP[i][w-wi]+v,DP[i][w])
        else:
            DP[i+1][w]=DP[i][w]
print(DP[N][W])

Submission status: Time Limit Exceeded

Solution code:
import math


def inputIntList():
    return [int(s) for s in input().split()]


def inputInt():
    return int(input())


def main():
    N, capacity = inputIntList()
    w = [0 for _ in range(N)]
    v = [0 for _ in range(N)]
    for i in range(N):
        w[i], v[i] = inputIntList()

    dp = [[float("inf") for _ in range(N * 1000 + 1)] for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(N * 1000 + 1):
            if j < v[i]:
                dp[i + 1][j] = min(dp[i][j], dp[i + 1][j])
            else:
                dp[i + 1][j] = min(dp[i][j - v[i]] + w[i], dp[i][j])
    ret = 0
    for value, weight in enumerate(dp[N]):
        if weight <= capacity:
            ret = max(ret, value)

    return ret


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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

dp = defaultdict(int)
dp[0] = 0
idx2check = {0}
for _ in range(N):
    w, v = map(int, input().split())
    new_idx2check = set()
    for k in idx2check:
        dp[k + w] = max(dp[k + w], dp[k] + v)
        new_idx2check.add(k+w)

    idx2check |= new_idx2check

ans = 0
for k, v in dp.items():
    if k <= W:
        ans = max(ans, v)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

dp = defaultdict(int)
dp[0] = 0
idx2check = [0]
for _ in range(N):
    w, v = map(int, input().split())
    new_idx2check = []
    for k in idx2check:
        dp[k + w] = max(dp[k + w], dp[k] + v)
        new_idx2check.append(k+w)

    idx2check += new_idx2check

ans = 0
for k, v in dp.items():
    if k <= W:
        ans = max(ans, v)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

dp = defaultdict(int)
dp[0] = 0
idx2check = [0]
ans = 0
for _ in range(N):
    w, v = map(int, input().split())
    new_idx2check = []
    for k in idx2check:
        if k + w <= W:
            dp[k + w] = max(dp[k + w], dp[k] + v)
            ans = max(ans, dp[k + w])
            new_idx2check.append(k+w)

    idx2check += new_idx2check


print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

dp = defaultdict(int)
dp[0] = 0
ans = 0
for _ in range(N):
    w, v = map(int, input().split())
    for k in list(dp.keys()):
        if k + w <= W:
            dp[k + w] = max(dp[k + w], dp[k] + v)
            ans = max(ans, dp[k + w])


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

def inputIntList():
    return [int(s) for s in input().split()]


def inputInt():
    return int(input())


def main():
    N, capacity = inputIntList()
    w = [0 for _ in range(N)]
    v = [0 for _ in range(N)]
    for i in range(N):
        w[i], v[i] = inputIntList()

    dp = [[0 for _ in range(capacity + 1)] for _ in range(N + 1)]
    for i in range(N):
        for j in range(capacity + 1):
            if j < w[i]:
                dp[i + 1][j] = dp[i][j]
            else:

                dp[i + 1][j] = max(dp[i][j - w[i]] + v[i], dp[i][j])
            # print(dp)

    return dp[N][capacity]


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

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
INF = 10**12
V = 1000 * N
Data = []
Data.append([0,0])
for _ in range(N):
    Data.append(list(map(int,input().split())))

#DP[n][v]: n番目までの品物で 価値vの品物を選んだ場合の重さの最小
DP = [[INF]*(V+1) for _ in range(N+1)]
for n in range(N+1):
    DP[n][0] = 0

for n in range(1,N+1):
    for v in range(1,V+1):
        wi,vi = Data[n]
        if v >= vi:
            DP[n][v] = min(DP[n][v],DP[n-1][v-vi]+wi)
        DP[n][v] = min(DP[n][v],DP[n-1][v])

ans = 0
for  v in range(V+1):
    if DP[N][v] <= W:
        ans = v
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

# import numpy as np

"""
20191120
D問題のコピペ
"""


def main():
    N, W = map(int, input().split())
    ws = [None for _ in range(N)]
    vs = [None for _ in range(N)]
    for i in range(N):
        ws[i], vs[i] = map(int, input().split())

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

    for n in range(N):
        for w in range(W+1):
            if w >= ws[n]:
                dp[n][w] = max(dp[n-1][w-ws[n]]+vs[n], dp[n-1][w])  # use or not use
            else:
                dp[n][w] = dp[n-1][w]  # not use

    return max(dp[-1])


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

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 for i in range(W+1)] for j in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j>=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:
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 for i in range(W+1)] for j in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j>=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:
import sys

import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# 数と価値で配列を作る
# 値は価値の最大値


def main():
    N, W = map(int, readline().split())
    WV = np.array([[int(x) for x in readline().split()] for _ in range(N)])
    U = np.sum(WV[:, 1])

    dp = np.full([N+1, U+1], U, np.int64)
    dp[0, 0] = 0

    for w, v in WV:
        p_dp = dp.copy()
        np.minimum(dp[1:, v:], p_dp[:-1, :-v] + w, out=dp[1:, v:])

    print(max(list(zip(*np.where(dp <= W))))[1])


main()

Submission status: Time Limit Exceeded

Solution code:
#EDP-E
import sys
n,W = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
dp = [[ float('inf') for i in range(100001)] for _ in range(n)]


dp[0][L[0][1]] = L[0][0]

for i in range(1, n):
    for vb in range(100001):
        if dp[i-1][vb] != float('inf'):
            dp[i][vb] = dp[i-1][vb]
            tmp = min(dp[i][vb + L[i][1]], dp[i-1][vb] + L[i][0])
            if tmp <=W:
                dp[i][vb + L[i][1]] = tmp
                #print(vb + v, dp[i][vb+ v])
    dp[i][L[i][1]] = min(dp[i][L[i][1]], L[i][0])

ans =0
for v, w in enumerate(dp[n-1]):
    if w <=W and ans <=v:
        ans = v
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#EDP-E
import sys
n,W = map(int, sys.stdin.readline().split())

dp = [[ float('inf') for i in range(100001)] for _ in range(n)]


w, v = map(int, sys.stdin.readline().split())
dp[0][v] = w

for i in range(1, n):
    w, v = map(int, sys.stdin.readline().split())
    for vb in range(100001):
        if dp[i-1][vb] != float('inf'):
            dp[i][vb] = dp[i-1][vb]
            tmp = min(dp[i][vb + v], dp[i-1][vb] + w)
            if tmp <=W:
                dp[i][vb + v] = tmp
                #print(vb + v, dp[i][vb+ v])
    dp[i][v] = min(dp[i][v], w)

ans =0
for v, w in enumerate(dp[n-1]):
    if w <=W and ans <=v:
        ans = v
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin,stdout
 
def solve(n,w):
	inf=1000000000000007
	v,d=[0]*n,[0]*n
	k=0
	for i in range(n):
		d[i],v[i]=list(map(int,stdin.readline().split()))
		k+=v[i]
	dp=[[inf for j in range(k+2)] for i in range(n+2)]
	dp[0][0],dp[1][0]=0,0
	for i in range(1,n+1):
		for j in range(k+2):
			if(j>=v[i-1]):
				dp[i][j]=min(dp[i][j],dp[i-1][j-v[i-1]]+d[i-1])
			dp[i+1][j]=dp[i][j]
	for j in range(k+2):
		if(dp[n][j]<=w):
			m=j
	print(m)

n,w=[int(i) for i in stdin.readline().split()]
solve(n,w)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin,stdout
 
MAXN=1007
MAXL=100007
inf=1000000000000007
dp=[[inf for j in range(MAXL)] for i in range(MAXN)]

def solve(n,w):
	v,d=[0]*n,[0]*n
	k=0
	for i in range(n):
		d[i],v[i]=list(map(int,stdin.readline().split()))
		k+=v[i]
	dp[0][0]=0
	for i in range(1,n+1):
		for j in range(k+1):
			if(j>=v[i-1]):
				dp[i][j]=min(dp[i][j],dp[i-1][j-v[i-1]]+d[i-1])
			dp[i+1][j]=dp[i][j]
	for j in range(k+1):
		if(dp[n][j]<=w):
			m=j
	print(m)

n,w=[int(i) for i in stdin.readline().split()]
solve(n,w)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin,stdout
 
MAXN=1007
MAXL=100007
inf=1000000000000007
dp=[[inf for j in range(MAXL)] for i in range(MAXN)]

def solve(n,w):
	v,d=[],[]
	k=0
	for i in range(n):
		a,b=[int(j) for j in stdin.readline().split()]
		d.append(a)
		v.append(b)
		k+=b
	dp[0][0]=0
	for i in range(1,n+1):
		for j in range(k+1):
			if(j>=v[i-1]):
				dp[i][j]=min(dp[i][j],dp[i-1][j-v[i-1]]+d[i-1])
			dp[i+1][j]=dp[i][j]
	for j in range(k+1):
		if(dp[n][j]<=w):
			m=j
	return m

n,w=[int(i) for i in stdin.readline().split()]
print(solve(n,w))

Submission status: Time Limit Exceeded

Solution code:
#EDP-D, E
import sys
from collections import defaultdict
n, W = map(int, sys.stdin.readline().split())
dp = [defaultdict(int) for _ in range(n)]
#初期設定
w, v = map(int, sys.stdin.readline().split())
dp[0][w] = v
#print(dp)

for i in range(1, n):
    w, v = map(int, sys.stdin.readline().split())
    dp[i][w] = max(dp[i-1].get(w, 0), v)
    for w1, v1 in dp[i-1].items():
        dp[i][w1] = max(dp[i][w1], v1)
        if w+w1<=W:
            dp[i][w1+w] = max(dp[i][w1+w], v1+v)

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

Submission status: Time Limit Exceeded

Solution code:
INF = 2000000000
n,limit_w = map(int, input().split())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i], v[i] = map(int, input().split())
sum_v = sum(v)
dp = [INF for i in range(sum_v + 1)]
dp[0] = 0
for i in range(n):
    for j in range(sum_v ,-1 ,-1):
        if j >= v[i]:
            dp[j] = min(dp[j], dp[j - v[i]] + w[i])
for i in range(sum_v, -1, -1):
    if dp[i] <= limit_w:
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:
n,W=map(int,input().split())
mv=1
s=[None]*n
for i in range(n):
  s[i]=list(map(int,input().split()))
  mv+=s[i][1]
  
INF=10**9+5
dp=[INF]*mv
dp[0]=0
for i in range(len(s)):
  w=s[i][0]
  v=s[i][1]
  for j in range(len(dp)-v-1,-1,-1):
    if dp[j]+w<dp[j+v]:
      dp[j+v]=dp[j]+w
      
ans=0
for i in range(len(dp)):
  if dp[i]<=W:
    ans=i
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,W=map(int,input().split())
mv=1
s=[None]*n
for i in range(n):
  s[i]=list(map(int,input().split()))
  mv+=s[i][1]
  
INF=10**9+5
dp=[INF]*mv
dp[0]=0
for i in range(len(s)):
  w=s[i][0]
  v=s[i][1]
  for j in range(len(dp)-1,-1,-1):
    if j+v<len(dp):
      dp[j+v]=min(dp[j+v],dp[j]+w)
      
ans=0
for i in range(len(dp)):
  if dp[i]<=W:
    ans=i
    
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())
dp=[[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j<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][W])

Submission status: Time Limit Exceeded

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