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:
import sys

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


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np

import bisect

def main():
	N,W=map(int,input().split())
	
	li=[list(map(int,input().split())) for _ in range(N)]
	V=sum(v for w,v in li)
	
	dp=[[10**15]*(V+2) for _ in [0]*(N+1)]
	
	for i in range(N):
		w = li[i][0]
		v = li[i][1]
		dp[i + 1][v] = min(dp[i + 1][v], w)
		for j in range(V+1)[::-1]:
			if j-v>=0:
				dp[i+1][j]=min(dp[i+1][j],dp[i+1][j+1],dp[i][j],dp[i][j-v]+w)
			else:
				dp[i + 1][j] = min(dp[i + 1][j], dp[i + 1][j + 1], dp[i][j])
#	for i in range(N+1):
#		print(dp[i])
	
	print(bisect.bisect_right(dp[-1],W)-1)
	
	
	
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

N, W = [int(item) for item in input().split()]
item = np.array([[int(item) for item in input().split()] for _ in range(N)])


dp = np.full((N+1, 10**5 + 1), 10**12+1)
dp[0][0] = 0

for i in range(N):
    for j in range(10**5 + 1):
        w, v = item[i]
        if j >= v:
            dp[i+1][j] = min(dp[i][j], dp[i][j - v] + w)
        else:
            dp[i+1][j] = dp[i][j]

print(np.where(dp[N] <= W)[0][-1])

Submission status: Time Limit Exceeded

Solution code:
n, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
w = [wv[i][0] for i in range(n)]
v = [wv[i][1] for i in range(n)]
inf = float('inf')
# dp[i][weight] 
# := i-1番目までの品物で重さweightを超えないように選んだときの価値の総和の最大値
dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
for i in range(n):
    for sum_w in range(W+1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[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())
items=[list(map(int,input().split())) for i in range(n)]
weight=[items[i][0] for i in range(n)]
value=[items[i][1] for i in range(n)]

limit=sum(value)
inf=10**9
dp=[[0]+[inf]*limit for i in range(n+1)]
#print(dp)
for i in range(n):
  w=weight[i]
  v=value[i]
  for j in range(limit+1):
    if j>=v:
      dp[i+1][j]=min(dp[i][j],dp[i][j-v]+w)
    else:
      dp[i+1][j]=min(dp[i][j],w)
#print(dp[n])
ans=max([i for i in range(limit+1) if dp[n][i]<=W])
print(ans)

Submission status: Time Limit Exceeded

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

dp=[[0 for i in range(W+1)] for j in range(N+1)] # dpリストを作る。dpの要素の数字は価値を表す。

for i in range(N): # １つ１つの商品について
    for w in range(W+1):
        if w>=list1[i][0]:# 重さ的に選ぶことができる
            dp[i+1][w]=max(dp[i][w],dp[i][w-list1[i][0]]+list1[i][1])
        else: # 重さ的に選べないので一個前のiのときのがそのまま
            dp[i+1][w]=dp[i][w]
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, W = map(int, input().split())
weight = []
value = []
for _ in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)
value_sum = sum(value)
dp = [[float('inf') for _ in range(value_sum + 1)] for _ in range(N + 1)]
dp = np.full((N + 1, value_sum + 1), float('inf'))
dp[0][0] = 0
# print(dp)
for idx in range(N):
    for v in range(value_sum + 1):
        if value[idx] <= v:
            dp[idx + 1][v] = min(dp[idx][v], dp[idx][v - value[idx]] + weight[idx])
        else:
            dp[idx + 1][v] = dp[idx][v]
ans = 0
# print(dp)
for i in range(value_sum + 1):
    if dp[N][i] <= W:
        ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
weight = []
value = []
for _ in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)
value_sum = sum(value)
dp = [[float('inf') for _ in range(value_sum + 1)] for _ in range(N + 1)]
dp[0][0] = 0

for idx in range(N):
    for v in range(value_sum + 1):
        if value[idx] <= v:
            dp[idx + 1][v] = min(dp[idx][v], dp[idx][v - value[idx]] + weight[idx])
        else:
            dp[idx + 1][v] = dp[idx][v]
ans = 0
# print(dp)
for i in range(value_sum + 1):
    if dp[N][i] <= W:
        ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, W = map(int, input().split())
weight = []
value = []
for _ in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)
value_sum = sum(value)
dp = []
for _ in range(N + 1):
    dp_val = [float('inf') for _ in range(value_sum + 1)]
    dp.append(dp_val)
dp[0][0] = 0
dp = np.array(dp)
value = np.array(value)
weight = np.array(weight)
for idx in range(N):
    for v in range(value_sum + 1):
        if value[idx] <= v:
            dp[idx + 1][v] = min(dp[idx][v], dp[idx][v - value[idx]] + weight[idx])
        else:
            dp[idx + 1][v] = dp[idx][v]
ans = 0
# print(dp)
for i in range(value_sum + 1):
    if dp[-1][i] <= W:
        ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import pprint
N, W = map(int, input().split())
weight = []
value = []
for _ in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)
value_sum = sum(value)
dp = []
for _ in range(N + 1):
    dp_val = [float('inf') for _ in range(value_sum + 1)]
    dp.append(dp_val)
# print(dp)
dp[0][0] = 0
# for v in range(value_sum):
#     dp[0][v] = 0
for idx in range(N):
    for v in range(value_sum + 1):
        if value[idx] <= v:
            dp[idx + 1][v] = min(dp[idx][v], dp[idx][v - value[idx]] + weight[idx])
        else:
            dp[idx + 1][v] = dp[idx][v]
ans = 0
# print(dp)
for i in range(value_sum + 1):
    if dp[-1][i] <= W:
        ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

def f2(N,W,weights, values):
    @lru_cache(None)
    def f3(i,j):
        if i == 0 and j <= 0:
            return 0
        if j <= 0 or i < 0:
            return 0
        if j - weights[i] >= 0:
            return max(values[i] + f3(i-1, j - weights[i]),f3(i-1,j))
        return f3(i-1,j)
    return f3(N-1,W)


N, W = map(int, input().split())
weights, values = [0]*N, [0]*N
for i in range(N):
    weights[i], values[i] = map(int, input().split())
print(f2(N,W,weights,values))

Submission status: Time Limit Exceeded

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

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

V = N*(10**3)+1
dp = [[float('inf')]*V for _ in range(N+1)]
# dp[i][j]: i個の品物までを見てjの価値を実現する最小のw
dp[0][0] = 0
temp = 0

for i in range(N):
  w = ws[i]
  v = vs[i]
  for k in range(V):
    if k-v>=0:
      dp[i+1][k] = min(dp[i][k-v]+w, dp[i+1][k])
    dp[i+1][k] = min(dp[i][k], dp[i+1][k])

for j in range(V-1, -1, -1):
  if dp[N][j] <= W:
    print(j)
    exit()

Submission status: Time Limit Exceeded

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

for i in range(N):
  w, v = map(int, input().split())
  ws[i] = w
  vs[i] = v
V = sum(vs)+1
  

dp = [[float('inf')]*V for _ in range(N+1)]
# dp[i][j]: i個の品物までを見てjの価値を実現する最小のw
dp[0][0] = 0
temp = 0

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

for j in range(V-1, -1, -1):
  if dp[N][j] <= W:
    print(j)
    exit()

Submission status: Time Limit Exceeded

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

for i in range(N):
  w, v = map(int, input().split())
  ws[i] = w
  vs[i] = v
V = sum(vs)+1
  

dp = [[float('inf')]*(V) for _ in range(N+1)]
# dp[i][j]: i個の品物を使ってjの価値を実現する最小のw
dp[0][0] = 0
temp = 0

for i in range(N):
  w = ws[i]
  v = vs[i]
  for j in range(i, -1, -1):
    for k in range(temp+1):
      dp[j+1][k+v] = min(dp[j][k]+w, dp[j+1][k+v])
  temp += v

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

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
dp = [[float('inf')]*(10**5+1) for _ in range(N+1)]
# dp[i][j]: i個の品物を使ってjの価値を実現する最小のw
dp[0][0] = 0
temp = 0

for i in range(N):
  w, v = map(int, input().split())
  for j in range(i, -1, -1):
    for k in range(temp+1):
      dp[j+1][k+v] = min(dp[j][k]+w, dp[j+1][k+v])
  temp += v

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

Submission status: Time Limit Exceeded

Solution code:
n,Capacity=list(int(i) for i in input().split())
maxv=0
W=[]
Values=[]
for i in range(n):
    w,v=list(int(i) for i in input().split())
    if v>maxv:
        maxv=v
    W.append(w)
    Values.append(v)
dp=[[0 for j in range(Capacity+1)]for i in range(n+1)]
for i in range(n+1):
    for w in range(Capacity+1):
        if i==0 or w==0:
            dp[i][w]=0
        elif w>=W[i-1]:
            dp[i][w]=max(dp[i-1][w],Values[i-1]+dp[i-1][w-W[i-1]])
        else:
            dp[i][w]=dp[i-1][w]
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
# D
import numpy as np

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

weight = []
value = []
for i in range(N):
    x, y = list(map(int, input().split()))
    weight.append(x)
    value.append(y)

def knapsack(N,W,weight,value):
    #初期化
    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 weight[i]<=w: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
            dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
          else: #入る可能性はない
            dp[i+1][w]=dp[i][w]
    return dp[N][W]

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

Submission status: Time Limit Exceeded

Solution code:
N, W, *t = map( int, open( 0 ).read().split() )
d = [[ 0 for _ in range( W + 1 ) ] for _ in range( N + 1 ) ]
ans = 0
 
i = 0
for w, v in zip( *[ iter( t )] * 2 ):
  for j in range( 1, W + 1 ):
    d[ i + 1 ][ j ] = d[ i ][ j ]
    if j - w >= 0:
      d[ i + 1 ][ j ] = max( d[ i ][ j - w ] + v, d[ i ][ j ] )
  i += 1
print( d[N][W])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    INF = float('inf')
    N,W = map(int,input().split())
    wv = [list(map(int,input().split())) for _ in range(N)]
    sumv = sum([v for w,v in wv])
    dp = [[INF]*(sumv+1) for _ in range(N+1)]
    dp[0][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]
    ans = 0
    for i in range(sumv+1):
        if dp[N][i] <= W:
            ans = max(ans,i)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

lim=n*10**3+1
dp=[[float('inf') for i in range(lim)] for i in range(n+1)]

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

for i in range(n):
 for sum_v in range(lim):

  if sum_v-l[i][1]>=0:
   dp[i+1][sum_v] = min(dp[i+1][sum_v],dp[i][sum_v-l[i][1]]+l[i][0])

  dp[i+1][sum_v]=min(dp[i+1][sum_v],dp[i][sum_v])

ans=0
for i in range(lim):
 if dp[-1][i]<=w:
  ans=max(ans,i)
print(ans)

Submission status: Time Limit Exceeded

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

dp=[float("inf")]*(10**5+1)
dp[0]=0
for i in range(n):
  for j in range(10**5,A[i][1]-1,-1):
    dp[j]=min(dp[j],dp[j-A[i][1]]+A[i][0])
ans=0
for v,e in enumerate(dp):
  if e<=w:
    ans=v
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/dp/submissions/9817777
N, W = list(map(lambda x: int(x), input().split()))
w = []
v = []
for i in range(N):
    line = input().split()
    w.append(int(line[0]))
    v.append(int(line[1]))

inf = 10 ** 10
M = sum(v) + 1
dp = [[inf] * M for i in range(N)]
for i in range(N):
    dp[i][0] = 0
dp[0][v[0]] = w[0]  # 最初のa行

lim = v[0] + 1
for i in range(1, N):
    k = w[i]
    d = dp[i]
    p = dp[i - 1]
    lim += v[i]
    for val in range(1, lim):
        diff = val - v[i]
        if diff >= 0:
            c = p[diff] + k
        else:
            c = d[val]
        d[val] = min(c, p[val])

# 許されるvの最大値を見つける
for val in reversed(range(M)):
    if dp[N - 1][val] <= W:
        print(val)
        break

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/dp/submissions/9817777
N, W = list(map(lambda x: int(x), input().split()))
w = []
v = []
for i in range(N):
    line = input().split()
    w.append(int(line[0]))
    v.append(int(line[1]))

inf = 10 ** 10
M = sum(v) + 1
dp = [[inf] * M for i in range(N)]
for i in range(N):
    dp[i][0] = 0
dp[0][v[0]] = w[0]  # 最初のa行

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

# 許されるvの最大値を見つける
for val in reversed(range(M)):
    if dp[N - 1][val] <= W:
        print(val)
        break

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/dp/submissions/9817777
N, W = list(map(lambda x: int(x), input().split()))
w = []
v = []
for i in range(N):
    line = input().split()
    w.append(int(line[0]))
    v.append(int(line[1]))

inf = 10 ** 10
M = sum(v) + 1
dp = [[inf] * M for i in range(N)]
for i in range(N):
    dp[i][0] = 0
dp[0][v[0]] = w[0]  # 最初のa行

lim = v[0] + 1
for i in range(1, N):
    lim += v[i]
    for val in range(1, lim):
        diff = val - v[i]
        if diff >= 0:
            c = dp[i - 1][diff] + w[i]
        else:
            c = dp[i][val]
        dp[i][val] = min(c, dp[i - 1][val])

# 許されるvの最大値を見つける
for val in reversed(range(M)):
    if dp[N - 1][val] <= W:
        print(val)
        break

Submission status: Time Limit Exceeded

Solution code:
N, W = list(map(lambda x: int(x), input().split()))
w = []
v = []
for i in range(N):
  line = input().split()
  w.append(int(line[0]))
  v.append(int(line[1]))
  
inf = 10**10
M = sum(v)+1
dp = [ [0] + [inf]*(M-1) for i in range(N) ]
dp[0][v[0]] = w[0] #最初の行

lim = v[0]+1
for i in range(1, N):
  lim += v[i]
  for val in range(1, lim):
    if val-v[i]>=0:
      dp[i][val] = dp[i-1][val-v[i]] + w[i]
    dp[i][val] = min(dp[i][val], dp[i-1][val])
    
#許されるvの最大値を見つける
for val in reversed(range(M)):
  if dp[N-1][val]<=W:
    print(val)
    break

Submission status: Time Limit Exceeded

Solution code:
N, W = list(map(lambda x: int(x), input().split()))
w = []
v = []
for i in range(N):
  line = input().split()
  w.append(int(line[0]))
  v.append(int(line[1]))
  
inf = 10**10
M = sum(v)+1
dp = [ [0] + [inf]*(M-1) for i in range(N) ]
dp[0][v[0]] = w[0] #最初の行

for i in range(1, N):
  for val in range(1, M):
    if val-v[i]>=0:
      dp[i][val] = dp[i-1][val-v[i]] + w[i]
    dp[i][val] = min(dp[i][val], dp[i-1][val])
    
#許されるvの最大値を見つける
for val in reversed(range(M)):
  if dp[N-1][val]<=W:
    print(val)
    break

Submission status: Time Limit Exceeded

Solution code:
N, W = list(map(lambda x: int(x), input().split()))
w = []
v = []
for i in range(N):
  line = input().split()
  w.append(int(line[0]))
  v.append(int(line[1]))
  
inf = 10**10
M = 100001
dp = [ [0] + [inf]*(M-1) for i in range(N) ]
dp[0][v[0]] = w[0] #最初の行

for i in range(1, N):
  for val in range(1, M):
    if val-v[i]>=0:
      dp[i][val] = dp[i-1][val-v[i]] + w[i]
    dp[i][val] = min(dp[i][val], dp[i-1][val])
    
#許されるvの最大値を見つける
for val in reversed(range(M)):
  if dp[N-1][val]<=W:
    print(val)
    break

Submission status: Time Limit Exceeded

Solution code:
INF = 10**10 - 1

#指定数分の複数の整数を順番に受けてリストに入力
N,Wmax = map(int, input().split())
w = [0]*(N+1)
v = [0]*(N+1)
Vsum = 0
for i in range(1,N+1):
    w[i],v[i] = map(int, input().split())
    Vsum += v[i]

#dpの初期化
dp = [[INF] * (Vsum+1) for i in range(N+1)]
for i in range(0,N+1):
    dp[i][0] = 0
#print(dp[0])

for i in range(1,N+1):
    for vv in range(1,Vsum+1):
        if v[i] > vv:
            dp[i][vv] = dp[i-1][vv]
        else:
            dp[i][vv] = min(dp[i-1][vv],dp[i-1][vv-v[i]]+w[i])
    #print(dp[i])

Vmax = 0
for vv in range(1,Vsum+1):
    if dp[N][vv] <= Wmax:
        Vmax = vv
print(Vmax)

Submission status: Time Limit Exceeded

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

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

for i, (wi, vi) in enumerate(x):
    dp_pre = dp[1 - i % 2]
    dp_cur = dp[i % 2]
    for j in range(1, wi):
        dp_cur[j] = dp_pre[j]
    for j in range(wi, w + 1):
        dp_cur[j] = max(dp_pre[j], dp_pre[j - wi] + vi)
print(max(dp_cur))

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N, W = map(int, input().split())
    MAX_V = 100100
    MAX_N = 110
    w = []
    v = []
    for i in range(N):
        tmpw, tmpv = map(int, input().split())
        w.append(tmpw)
        v.append(tmpv)

    dp = [[float('inf') for i in range(MAX_V+1)] for j in range(MAX_N+1)]

    dp[0][0] = 0

    for i in range(N):
        for sum_v in range(MAX_V):
            if sum_v - v[i] >= 0:
                dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - v[i]] + w[i])
            
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])
        
    res = 0
    for sum_v in range(MAX_V+1):
        if dp[N][sum_v] <= W:
            res = sum_v
    print(res)

if __name__ == '__main__':
    solve()

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)

S=sum(v)

DP=[[1000000000000]*(S+1) for i in range(N+1)]
for i in range(N+1):
    DP[i][0]=0



for i in range(N):
    for v1 in range(S+1):
        DP[i+1][v1]=min(DP[i][v1-v[i]]+w[i],DP[i][v1])

for i in range(S,0,-1):
    if DP[N][i]<=W:
        print(i)
        exit()

Submission status: Time Limit Exceeded

Solution code:
import sys 
sys.setrecursionlimit(2147483647)

N,W = map(int,input().split())
A = [list(map(int, input().split())) for i in range(N)]
dp = [[float("inf") for _ in range(100100) ] for _ in range(N + 1)] 

dp[0][0] = 0 
for i in range(0,N): 
    for j in range(100100): 
        if j - A[i][1] >=0:
            res1 = dp[i][j - A[i][1]] + A[i][0]
            dp[i + 1][j] = min(res1,dp[i+1][j])
        dp[i + 1][j] = min(dp[i + 1][j],dp[i][j])
res = 0 
for j in range(100100):
    if dp[N][j]<=W:
        res = j 
print(res)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,W = map(int,input().split())
weight = []
val = []
for i in range(n):
    a,b = map(int,input().split())
    weight.append(a)
    val.append(b)
max_v = sum(val) + 10 # 全部使ったとしてもこれ以上の勝ちにはならない
# point : v < =10^3 でn <= 10^2なので、n**2 vでもOK
# wが使えないときには変数を入れ替える
INF = 10**12+7 #Wより大きな値
dp = [[INF]*(max_v+1) for i in range(n+1)]
#初期化は 価値が0になる最小の重さが0なので、dp[i][0] = 0
# 漸化式：dp[i+1][j] = min(dp[i][j],dp[i][j-v[i]]+w[i])
# i+1　は i番目までの品物を使うとする
# 先にどっちからループを回した方が良い？価値か、品数か
#　品数が全部埋まってから、価値を更新する方が楽そう
for i in range(n+1):
    dp[i][0] = 0
for i in range(n):
    for j in range(max_v+1):
        if j-val[i] >= 0:
            #print("yes")
            dp[i+1][j] = min(dp[i][j],dp[i][j-val[i]]+ weight[i])
        else: dp[i+1][j] = dp[i][j]
    if i == n-1:
        #print("Yes")
        #print(dp[i+1])
        #大きい方から見ていく
        for j in range(1,max_v+1):
            #print(j)
            if dp[i+1][-j] <= W:
                print(max_v - j + 1)
                break

Submission status: Time Limit Exceeded

Solution code:
import sys 
sys.setrecursionlimit(2147483647)

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

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

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
K = 10**5
dp = [[10**100 for i in range(K+1)] for j in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    w,v = map(int,input().split())
    for j in range(K+1):
        dp[i][j] = dp[i-1][j]
        if j < v:
            continue
        else:
            dp[i][j] = min(dp[i-1][j-v] + w,dp[i-1][j])
for i in range(K+1):
    x = dp[N][-i-1]
    if x <= W:
        print(K-i)
        quit()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""


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

#L = sorted([list(map(int,input().split())) for i in range(N)])

M=int(sum(vi))
dp1=[sum(wi)+1]*(M+1)
#dp2=[sum(wi)+1]*(M+1)
dp1[0]=0
   
#L = sorted([list(map(int,input().split())) for i in range(N)])
s=0

for w, v in zip(wi,vi):
    s+=v
    for j in range(min(s,M),v-1,-1):
        if j >= v: 
            if dp1[j] > dp1[j-v]+w: dp1[j]=dp1[j-v]+w
        if dp1[j] > dp1[j]: dp1[j]=dp1[j]
    #print(dp1)
    #print(dp2)
    #dp1=[dp2[i] for i in range(M+1)]    
    
#print(max(dp))
m=0
for i in range(M+1):
    if dp1[i]<=W:
        m=i
print(m)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""


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

M=int(sum(vi))
dp1=[sum(wi)+1]*(M+1)
#dp2=[sum(wi)+1]*(M+1)
dp1[0]=0
   
#L = sorted([list(map(int,input().split())) for i in range(N)])
s=0

for w, v in zip(wi,vi):
    s+=v
    for j in range(min(s,M),-1,-1):
        if j >= v: 
            if dp1[j] > dp1[j-v]+w: dp1[j]=dp1[j-v]+w
        if dp1[j] > dp1[j]: dp1[j]=dp1[j]
    #print(dp1)
    #print(dp2)
    #dp1=[dp2[i] for i in range(M+1)]    
    
#print(max(dp))
m=0
for i in range(M+1):
    if dp1[i]<=W:
        m=i
print(m)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""


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

M=int(sum(vi))
dp1=[sum(wi)+1]*(M+1)
dp2=[sum(wi)+1]*(M+1)
dp1[0]=0
   
#L = sorted([list(map(int,input().split())) for i in range(N)])
s=0

for w, v in zip(wi,vi):
    for j in range(M+1):
        if j >= v: 
            if dp2[j] > dp1[j-v]+w: dp2[j]=dp1[j-v]+w
        if dp2[j] > dp1[j]: dp2[j]=dp1[j]
    #print(dp1)
    #print(dp2)
    dp1=[dp2[i] for i in range(M+1)]    
    
#print(max(dp))
m=0
for i in range(M+1):
    if dp2[i]<=W:
        m=i
print(m)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

N, W = list(map(int, input().split()))
item_list = []

for _ in range(N):
    w, v = list(map(int, input().split()))
    item_list.append((w, v))

max_v = (10 ** 3) * 100
dp_table = [[0] + [float("inf")] * (max_v + 1) for _ in range(N + 1)]
total_v = 0

for i in range(1, N + 1):
    w, v = item_list[i - 1]
    # 品物iまで考慮したときの価値の最大値
    total_v += v
    for j in range(total_v + 1):
        # 品物iを入れない場合
        dp_table[i][j] = dp_table[i - 1][j]
        before_min_weight = dp_table[i - 1][j]
        # dp_table[i][j] = before_min_weight
        # 品物iを入れる場合
        if j - v < 0:
            continue
        weight = dp_table[i - 1][j - v] + w
        min_weight = min(before_min_weight, weight)
        dp_table[i][j] = min_weight
        if i == N:
            if min_weight <= W:
                max_value = j


# max_value = 0
# for i, w in enumerate(dp_table[-1]):
#     if w <= W:
#         max_value = i
ans = max_value
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

N, W = list(map(int, input().split()))
item_list = []

for _ in range(N):
    w, v = list(map(int, input().split()))
    item_list.append((w, v))

max_v = (10 ** 3) * 100
dp_table = [[0] + [float("inf")] * (max_v + 1) for _ in range(N + 1)]
total_v = 0

for i in range(1, N + 1):
    w, v = item_list[i - 1]
    # 品物iまで考慮したときの価値の最大値
    total_v += v
    for j in range(total_v + 1):
        # 品物iを入れない場合
        dp_table[i][j] = dp_table[i - 1][j]
        before_min_weight = dp_table[i - 1][j]
        # dp_table[i][j] = before_min_weight
        # 品物iを入れる場合
        if j - v < 0:
            continue
        weight = dp_table[i - 1][j - v] + w
        min_weight = min(before_min_weight, weight)
        dp_table[i][j] = min_weight

        # if min_weight <= W:
        #     dp_table[i][j] = min_weight
        #     # max_value = j
max_value = 0
for i, w in enumerate(dp_table[-1]):
    if w <= W:
        max_value = i
ans = max_value
print(ans)

Submission status: Time Limit Exceeded

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

for _ in range(N):
    w, v = map(int, input().split())
    items.append((w, v))

def solve(items, w=W, cur_item=0):
    if cur_item >= len(items):
        return 0
    
    cur_w, cur_v = items[cur_item]

    dont_take = solve(items, w, cur_item+1)

    if cur_w <= w:
        take = solve(items, w-cur_w, cur_item+1) + cur_v
    else:
        take = 0
    
    return max(take, dont_take)
        
print(solve(items, W))

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split(" "))
weights = []
values = []

for _ in range(N):
    w, v = map(int, input().split(" "))
    weights.append(w)
    values.append(v)

dp = []
for i in range(N+1):
    tmp = []
    for j in range(W+1):
        tmp.append(None)
    dp.append(tmp)

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

for i in range(N):
    item_weight = weights[i]
    for j in range(W+1):
        if j >= item_weight:
            dp[i+1][j] = max([dp[i][j-weights[i]] + values[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(" "))
weights = []
values = []

for _ in range(N):
    w, v = map(int, input().split(" "))
    weights.append(w)
    values.append(v)

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

for i in range(N):
    item_weight = weights[i]
    for j in range(W+1):
        if j >= item_weight:
            dp[i+1][j] = max([dp[i][j-weights[i]] + values[i], dp[i][j]])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
def solver():
    N,W = map(int,input().split())
    item = []
    V_MAX = 0
    for _ in range(N):
        w, v = map(int,input().split())
        V_MAX += v
        item.append([w,v])
    dp = [float('inf')]*(V_MAX+1)
    dp[0] = 0
    pos = [0]
    for w,v in item:
        pos_temp = pos.copy()
        for p in pos:
            pos_temp.append(p)
            if (dp[p]+w <= W):
                dp[p+v] = min(dp[p+v], dp[p]+w)
                pos_temp.append(p+v)
        pos = pos_temp
    print(max(pos))

solver()

Submission status: Time Limit Exceeded

Solution code:
def solver():
    N,W = map(int,input().split())
    item = []
    V_MAX = 0
    for _ in range(N):
        w, v = map(int,input().split())
        V_MAX += v
        item.append([w,v])
    dp = [float('inf')]*(V_MAX+1)
    dp[0] = 0
    pos = [0]
    for w,v in item:
        pos_temp = pos.copy()
        for p in pos:
            pos_temp.append(p)
            if (dp[p]+w <= W):
                dp[p+v] = min(dp[p+v], dp[p]+w)
                pos_temp.append(p+v)
        pos = pos_temp
    res = 0
    for i in range(V_MAX + 1):
        if dp[i]<=W and res < i : res = i
    print(res)

solver()

Submission status: Time Limit Exceeded

Solution code:
# E - Knapsack 2
from collections import defaultdict


def main():
    N, W, *WV = map(int, open(0).read().split())
    dp = defaultdict(int)
    dp[0] = 0
    for w, v in zip(*[iter(WV)] * 2):
        for cur_w, cur_v in tuple(dp.items()):
            if w + cur_w <= W:
                dp[w + cur_w] = max(dp[w + cur_w], v + cur_v)
    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 i in range(N) ]

def dp():
  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):
    w = WV[i][0]
    v = WV[i][1]
    for j in range(W+1):
      if w<=j: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
        dp[i+1][j]=max(dp[i][j-w]+v, dp[i][j])
      else: #入る可能性はない
        dp[i+1][j]=dp[i][j]
  return dp[N][W]
print(dp())