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:
N,W=map(int,input().split())
w=[]
v=[]
maxV=0
for i in range(N):
    a,b=map(int,input().split())
    if maxV<b:
        maxV=b
    w.append(a)
    v.append(b)
#dp[n個目のアイテムまでで][V以上を達成する]=最小のw
#dp[0][v]=inf ゼロ個でｖは無理なので
#dp[0][0]=0と初期化する
#だからiの時dp[i][v]=min(dp[i-1][v],dp[i-1][V-v[i-1]]+w[i])である<-i-1なのはvとかにはゼロ個とかないので
#V-v[i]<0ならば、とれないので前者になるね！！
#これをi=0(は初期化でする)->nまでおこない、各iについてはとりうる最大のValueを考えるが
#これは最大で各アイテムについて最大のVがあってこれにアイテム数Nを掛けたものである
#つまりdpのサイズはdp[0->N][0->maxV*N]をとればよい

dp=[[float("inf") for i in range(maxV*(N+1))] for j in range(N+1)]
dp[0][0]=0

for i in range(1,N+1):
    for val in range(maxV*N+1):
        tmp1=dp[i-1][val]#とらない
        if val-v[i-1]<0:#この時、iこめの価値がおおきいので、これをとるだけで達成してしまう
            tmp2=w[i-1]#i=1の時、dp[0][val]=inf
        else:#i=1の時val-v[0]>0で無限になるので
            tmp2=dp[i-1][val-v[i-1]]+w[i-1]#
        res=min(tmp1,tmp2)
        dp[i][val]=res
#ここでW以下となるvalの最大値をたんさくする
max=0
for value in range(len(dp[N])):
    if dp[N][value]<=W:
        if value>max:
            max=value
print(max)

Submission status: Time Limit Exceeded

Solution code:
def knap(N,W,weight,value):
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    #各nについて初期化　以下で各ｗについて0この時０とする
    for i in range(W+1):#w+1とは0~w
        dp[0][i]=0
    for i in range(N):#each n 0~N-1
        for w in range(W+1):#w 0~w
            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)
    return dp[N][W]


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)
print(knap(n,W,w,v))

Submission status: Time Limit Exceeded

Solution code:
import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
dp = [collections.defaultdict(int) for _ in range(N+1)] #1_indexed
dp[0][0] = 0
for i in range(1,N+1):
    w,v = wv[i-1]
    for dw,dv in dp[i-1].items():
        dp[i][dw] = max(dp[i][dw],dv)
        if w+dw<=W:
            dp[i][w+dw] = max(dp[i][w+dw],v+dv)
print(max(dp[-1].values()))

Submission status: Time Limit Exceeded

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

dp = [[float("inf") for _ in range(N * v_max + 1)] for _ in range(N + 1)]

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

ans = 0
for i in range(1, N + 1):
    for j in range(N * v_max + 1):
        if j - items[i][1] >= 0:
            dp[i][j] = min(dp[i - 1][j - items[i][1]] + items[i][0], dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]

        if i == N and dp[i][j] <= W:
            ans = max(ans, j)

print(ans)

Submission status: Time Limit Exceeded

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

dp = [[float("inf") for _ in range(N * v_max + 1)] for _ in range(N + 1)]

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

for i in range(1, N + 1):
    for j in range(N * v_max + 1):
        if j - items[i][1] >= 0:
            dp[i][j] = min(dp[i - 1][j - items[i][1]] + items[i][0], dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]

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

Submission status: Time Limit Exceeded

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

dp = [[float("inf") for _ in range(N * v_max + 1)] for _ in range(N + 1)]

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

ans = 0
for i in range(1, N + 1):
    for j in range(N * v_max + 1):
        if j - items[i][1] >= 0:
            dp[i][j] = min(dp[i - 1][j - items[i][1]] + items[i][0], dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]
        if dp[i][j] <= W:
            ans = max(ans, j)

print(ans)

Submission status: Time Limit Exceeded

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

dp = [[float("inf") for _ in range(10 ** 5 + 1)] for _ in range(N + 1)]

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

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

print(ans)

Submission status: Time Limit Exceeded

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

dp = [[float("inf") for _ in range(10 ** 5 + 1)] for _ in range(N + 1)]

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

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

print(ans)

Submission status: Time Limit Exceeded

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

dp = [[float("inf") for _ in range(10 ** 5 + 1)] for _ in range(N + 1)]

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

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

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:
import sys
input=sys.stdin.readline
n,w=map(int,input().split())
val=[0]*n
wt=[0]*n
dp=[[0 for x in range(w+1)] for x in range(n+1)] 
for i in range(n):
  a,b=map(int,input().split())
  wt[i]=a
  val[i]=b
for i in range(1,n+1):
    for j in range(1,w+1):
        if(wt[i-1] <= j):
            dp[i][j]=max(val[i-1] + dp[i-1][j-wt[i-1]] , dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
val=[0]*n
wt=[0]*n
dp=[[0 for x in range(w+1)] for x in range(n+1)] 
for i in range(n):
  a,b=map(int,input().split())
  wt[i]=a
  val[i]=b
for i in range(1,n+1):
    for j in range(1,w+1):
        if(wt[i-1] <= j):
            dp[i][j]=max(val[i-1] + dp[i-1][j-wt[i-1]] , dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
waight=[0]
value=[0]
for _ in range(N):
    a,b=map(int,input().split())
    waight.append(a)
    value.append(b)
SUM_v=sum(value)
dp=[[float("inf")]*(SUM_v+1) for _ in range(N+1)]
dp[0][0]=0
ans=0
for i in range(N):
    for sum_v in range(SUM_v+1):
        dp[i+1][sum_v]=min(dp[i][sum_v],dp[i][max(0,sum_v-value[i+1])]+waight[i+1])
        if dp[i+1][sum_v]<=W:
            ans=max(ans,sum_v)
print(ans)

Submission status: Time Limit Exceeded

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

max_sumv = sum(V) 
# Dp[i][sum_v] := i-1 番目までの品物から価値がsum_v以上を達成するように選んだときの、重さの総和の最小値小値
dp = [[10 ** 9] * (max_sumv + 1) for _ in range(n+1)]

dp[0][0] = 0

for i in range(n):
    for sum_v in range(max_sumv + 1):
        # i番目の商品を選ぶ場合
        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])
        # i番目の商品を選ばない場合
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])
ans = 0
for i in range(max_sumv + 1):
    if dp[n][i] <= w:
        ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,w,*wv=map(int,open(0).read().split())
wei=wv[0::2]
val=wv[1::2]
sack=np.array([[0 for i in range(w+1)] for j in range(2)])
for i in range(n):
  t=i&1
  np.maximum(sack[t-1][:-wei[i]]+val[i],sack[t-1][wei[i]:],out=sack[t][wei[i]:])
  sack[t][:wei[i]]=sack[t-1][:wei[i]]
print(sack[(n-1)&1][-1])

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
g = []
for i in range(n):
    g.append(list(map(int, input().split())))
m = [[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-g[i][0] < 0:
            m[i+1][j] = m[i][j]
        else:
            m[i+1][j] = max(m[i][j], m[i][j-g[i][0]]+g[i][1])
print(m[n][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 = [[10**9+1]*(10**7) for _ in range(N+2)]
dp[0][0] = 0

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

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
w = []
v = []
max_v = 1000
for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
INF = int(1e9+1)*(N+1)
dp = [INF for _ in range(max_v*N+1)]
max_sum = max_v*N
dp[0] = 0

ans=0

for i in range(N):
  for j in range(max_v*N,v[i]-1,-1):
    res = dp[j-v[i]]+w[i]
    if res > W: continue
    if j > ans:ans=j
    dp[j]=min(dp[j],res)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
w = []
v = []
max_v = 1000
for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
INF = int(1e9)*(N+1)
dp = [INF] * (max_v * N+1)
max_sum = max_v*N
dp[0] = 0

for i in range(N):
  for j in range(max_v*N,v[i]-1,-1):
    res = dp[j-v[i]]+w[i]
    if res > W: continue
    dp[j]=min(dp[j],res)

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

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
w = []
v = []
max_v = 1000
for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
INF = int(1e9)*(N+1)
dp = [[INF] * (max_v * N+1) for _ in range(N+1)]
max_sum = max_v*N
dp[0][0] = 0

for i in range(N):
    for j in range(max_v * N+1):
        if j+v[i] > max_sum:
            break
        dp[i+1][j+v[i]] = min(dp[i+1][j+v[i]], dp[i][j]+w[i])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

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

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)
V=sum(v)

dp=[[float("inf") for i in range(V+1)] for _ in range(110)]
dp[0][0]=0

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

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


ans=0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,W = map(int,input().split())
#N = int(input())
dp =[[0 for i in range(W+1)] for j in range(N+1)]
w = np.zeros(W+1)
v = [0]*N
ndp = np.zeros(W + 1, dtype=np.int64)
for i in range(N):
  w[i],v[i] =  map(int,input().split())
for i in range(N):
  ndp[w[i]:] = np.maximum(ndp[:-w[i]] + v[i], ndp[w[i]:])
print(ndp[W])

Submission status: Time Limit Exceeded

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

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

for h in range(W):
    if h+1>=w[0]:
        dp[0][h]=v[0]

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

for i in range(2**N):
    bit=bin(i)[2:].zfill(N)
    temp=[0,0]
    for j in range(N):
        temp[0]+=int(bit[j])*v[j]
        temp[1]+=int(bit[j])*w[j]
    if temp[1]>W:
        temp[0]=0
    ans.append(temp[0])
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:

N,W = map(int,input().split())
weight = [0]
value = [0]
for i in range(N):
    w,v = map(int,input().split())
    weight.append(w)
    value.append(v)
    
maxValue = sum(value)
dp = [[float("inf") for i in range(maxValue+1)] for j in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
for i in range(1,N+1):
    for v in range(1,maxValue+1):
        dp[i][v] = dp[i-1][v]
        if value[i] <= v:
            dp[i][v] = min(dp[i][v],weight[i] + dp[i-1][v-value[i]])
ans = 0
for x in range(maxValue+1):
    if dp[N][x] <= W:
        ans = x
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
weight = [0]
value = [0]
for i in range(N):
    w,v = map(int,input().split())
    weight.append(w)
    value.append(v)
maxValue = N*1000
dp = [[float("inf") for i in range(maxValue+1)] for j in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0

for i in range(1,N+1):
    for v in range(1,maxValue+1):
        dp[i][v] = dp[i-1][v]
        if value[i] > v: continue;
        dp[i][v] = min(dp[i][v],weight[i] + dp[i-1][v-value[i]])
ans = 0
for x in range(maxValue+1):
    if dp[N][x] <= W:
        ans = x
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,w = map(int,input().split())
array = [0] + [[int(x) for x in input().split()] for x in range(n)]
v_max = 100000
dp = np.ones([n+1,v_max+1],dtype=np.int64)*float("inf")
for v in range(1,v_max+1):
    for i in range(1,n+1):
        if(array[i][1]>=v):
            dp[i][v] = min(dp[i-1][v],array[i][0])
        else:
            dp[i][v] = min(dp[i-1][v],array[i][0]+dp[i-1][v-array[i][1]])
for v in range(v_max+1):
    if(dp[n][v] <= w):
        ans = v
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,w = map(int,input().split())
array = [[int(x) for x in input().split()] for x in range(n)]
v_max = 100000
dp = [[float("inf") for x in range(v_max+1)] for x in range(n+1)]
for v in range(1,v_max+1):
    for i in range(1,n+1):
        if(array[i-1][1]>=v):
            dp[i][v] = min(dp[i-1][v],array[i-1][0])
        else:
            dp[i][v] = min(dp[i-1][v],array[i-1][0]+dp[i-1][v-array[i-1][1]])
ans = 0
for v in range(v_max+1):
    if(dp[n][v] <= w):
        ans = v
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,w = map(int,input().split())
array = [[int(x) for x in input().split()] for x in range(n)]
if(n == 1):
    v_max = array[0][1]
else:
    v_max = max(array[:][1])*n
dp = [[float("inf") for x in range(v_max+1)] for x in range(n+1)]
for v in range(1,v_max+1):
    for i in range(1,n+1):
        if(array[i-1][1]>=v):
            dp[i][v] = min(dp[i-1][v],array[i-1][0])
        else:
            dp[i][v] = min(dp[i-1][v],array[i-1][0]+dp[i-1][v-array[i-1][1]])
ans = 0
for v in range(v_max+1):
    if(dp[n][v] <= w):
        ans = v
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = input().split()
N = int(a[0])
W = int(a[1])
wv_list = []
for i in range(N):
    b = input().split()
    w = int(b[0])
    v = int(b[1])

    wv_list.append([w, v])

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

if wv_list[0][0] <= W:
    n_list[wv_list[0][0]] = wv_list[0][1]
import copy
for i in range(1, N):
    n_list1=copy.deepcopy(n_list)
    for j in range(W):
        s = j + wv_list[i][0]
        if s <= W:
            n_list[s] = max(n_list1[j] + wv_list[i][1], n_list[s])

        n_list[j] = max(n_list1[j], n_list[j])

print(max(n_list))

Submission status: Time Limit Exceeded

Solution code:
a=input().split()
N=int(a[0])
W=int(a[1])
wv_list=[]
for i in range(N) :
  b=input().split()
  w=int(b[0])
  v=int(b[1])

  wv_list.append([w,v])

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


if wv_list[0][0]<=W :
    n_list[0][wv_list[0][0]]=wv_list[0][1]

for i in range(1,N) :
    for j in range(W) :
        s=j+wv_list[i][0]
        if s<=W :
            n_list[i][s]=max(n_list[i-1][j]+wv_list[i][1],n_list[i][s])

        n_list[i][j] = max(n_list[i - 1][j],n_list[i][j])

print(max(n_list[-1]))

Submission status: Time Limit Exceeded

Solution code:
n,w = map(int, input().split())
wv = []
vsum=0
for _ in range(n):
    tmp = list(map(int,input().split()))
    wv.append(tmp)
    vsum += tmp[1]

INF = 1 << 30

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

for i in range(1,n+1):
    now_w,now_v =wv[i-1]
    for v in range(vsum+1):
        dp[i][v] = dp[i-1][v]
        if v - now_v >= 0:
            dp[i][v] = min(dp[i][v],dp[i-1][v-now_v] + now_w)

ans=0
for val in range(len(dp[-1])):
    if dp[-1][val] <= w:
        ans=val
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
c = []
for i in range(n):
    s = list(map(int, input().split()))
    c.append(s)
dp = [[0 for j in range(w+1)]for i in range(n)]
c.sort(key=lambda x: x[0])
for i in range(c[0][0], w+1):
    dp[0][i] = c[0][1]
for i in range(1, n):
    for j in range(w+1):
        if  j-c[i][0] >= 0:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i][0]] + c[i][1])
        if dp[i][j] == 0:
            dp[i][j] = dp[i-1][j]
print(dp[n-1][w])

Submission status: Time Limit Exceeded

Solution code:
n,wmax=map(int,input().split())
v=[0]*n
w=[0]*n
for i in range(n):
    w[i],v[i]=list(map(int,input().split()))
sv=sum(v)+1
dp=[[float('inf')]*sv for _ in range(n)]
dp[0][v[0]-1]=w[0]
for i in range(n):
    dp[i][0]=0
for i in range(n):
    for j in range(sv):
        dp[i][j]=min(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
        if dp[i][j]>wmax:
            dp[i][j]=float('inf')
ans=float('inf')
for p in range(sv-1,-1,-1):
    if dp[n-1][p]!=ans:
        ans=p
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# python3だとTLE,pypy3だとAC
def main():
    N, W = map(int, input().split())
    w = [None for _ in range(N)]
    v = [None for _ in range(N)]
    for i in range(N):
        w[i], v[i] = map(int, input().split())
    MAX_V = sum(v)
    dp = [[10**9 for _ in range(MAX_V+1)] for _ in range(N)]
    dp[0][0] = 0
    for i in range(N-1):
        if i == 0:
            for sum_v in range(1, v[i]+1):
                dp[i][sum_v] = w[i]
        for sum_v in range(MAX_V+1):
            if sum_v - v[i+1] >= 0:
                dp[i+1][sum_v] = min(w[i+1] + dp[i]
                                     [sum_v-v[i+1]], dp[i][sum_v])
            else:
                dp[i+1][sum_v] = min(w[i+1], dp[i][sum_v])
    print(len(list(filter(lambda sum_v: sum_v <= W, dp[-1])))-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, W = map(int, readline().split())
things = []
vsum = 0
for i in range(N):
    weight, value = map(int, readline().split())
    things.append((weight, value))
    vsum += value


INF = 1 << 62


def solve():
    dp = [INF] * (vsum + 1)
    w0, v0 = things[0]
    dp[0] = 0
    dp[v0] = w0
    for i in range(1, N):
        dn = list(dp)
        w, v = things[i]
        for j in range(vsum - v + 1):
            w2 = dp[j] + w
            if j + v <= vsum and w2 <= W:
                dn[j + v] = min(dn[j + v], w2)
        dp = dn
    for i in range(vsum, -1, -1):
        w = dp[i]
        if w <= W:
            return i
    return 0  # nothing is available


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

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())
max_v = max(v)


# dp[i][j] = i番目までの荷物をいくつか選んで価値をjぴったりにしたときの重さの最小値
dp = [[10**18]*(n*max_v+1) for i in range(n)]
# 価値を0ぴったりにする重さの最小値は0
for i in range(n) :
    dp[i][0] = 0

for i in range(n) :
    for j in range(n*max_v+1) :
        if j-v[i] >= 0 : # i番目の荷物を選んで価値をjぴったりにできる場合
            dp[i][j] = min(dp[i][j], dp[i-1][j-v[i]]+w[i])
        dp[i][j] = min(dp[i][j], dp[i-1][j])

for j in range(n*max_v,-1,-1) :
    if dp[n-1][j] <= W :
        print(j)
        break

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以上となるときの重さの総和の最小値
INF = float('inf')
dp = [[INF for j in range(max(v)*N+1)] for i in range(N+1)]
dp[0][0] = 0

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

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

Submission status: Time Limit Exceeded

Solution code:
from sys import maxint
 
N, W = map(int,raw_input().split())
 
weights, values = [], []

for n in range(N) :
  w, v = map(int,raw_input().split())
  weights.append(w)
  values.append(v)

mxValue = sum(values)
dp = [[None for n in range(N)] for i in range(mxValue+1)] 

def solve(curValue, curItem) :
  if curValue <= 0 : return 0
  if curItem == N : return maxint
  if dp[curValue][curItem] is not None : return dp[curValue][curItem]
 
  dp[curValue][curItem] = min(
    solve(curValue, curItem+1), 
    solve(curValue - values[curItem], curItem+1) + weights[curItem]
  )
 
  return dp[curValue][curItem]

ans = 0
for val in range(mxValue, -1, -1) :
  if solve(val, 0) <= W :
    ans = val
    break
 
print ans

Submission status: Time Limit Exceeded

Solution code:
from sys import maxint

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

mxValue = N*1000

weights, values = [], []
dp = [[None for n in range(N)] for i in range(mxValue+1)] 

for n in range(N) :
  w, v = map(int,raw_input().split())
  weights.append(w)
  values.append(v)

def solve(curValue, curItem) :
  if curValue <= 0 : return 0
  if curItem == N : return maxint
  if dp[curValue][curItem] is not None : return dp[curValue][curItem]

  dp[curValue][curItem] = min(
    solve(curValue, curItem+1), 
    solve(curValue - values[curItem], curItem+1) + weights[curItem]
  )

  return dp[curValue][curItem]

ans = 0
for val in range(mxValue, -1, -1) :
  if solve(val, 0) <= W :
    ans = val
    break

print ans

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,W = map(int,input().split())
wv = [map(int,input().split()) for _ in range(N)]
w,v = [list(i) for i in zip(*wv)]
max_v,max_w = 0,0
for i,j in zip(w,v):
    max_w += i
    max_v += j
dp = [[float("inf")]*(max_v+1) for _ in range(N+1)]
dp[0][0] = 0#初期値
for i in range(1,N+1):
    for j in range(max_v+1):
        if j - v[i-1] >= 0:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i-1]]+w[i-1])
        else:
            dp[i][j] = dp[i-1][j]
for i in range(1,max_v+2):
    if W >= dp[N][-i]:
        print(max_v+1-i)
        break

Submission status: Time Limit Exceeded

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

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

for i in range(len(dp[-1])):
    if 0 < dp[-1][i]<= M:
        ans = i
    else:
        pass

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import maxsize


def solve(ls, n, w):
	sm_value = 0
	for i in range(n):
		sm_value += ls[i][1]
	dp = [maxsize] * (sm_value + 1)
	dp[0] = 0
	for item in range(n):
		for value in range(sm_value, ls[item][1] - 1, -1):
			dp[value] = min(dp[value], dp[value - ls[item][1]] + ls[item][0])
	ans = -maxsize
	for i in range(sm_value + 1):
		if dp[i] <= w:
			ans = max(ans, i)
	return ans


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

INFTY = -1
MAX_V = 10**5
dp = [[INFTY]*(MAX_V+1) for _ in range(N)]
dp[0][S[0][1]] = S[0][0]

for i in range(1, N):
    w, v = S[i]
    for j in range(v):
        dp[i][j] = dp[i-1][j]

    if dp[i-1][v] == -1:
        dp[i][v] = w
    else:
        dp[i][v] = min(dp[i-1][v], w)

    for j in range(v+1, MAX_V+1):
        if dp[i-1][j] == -1 and dp[i-1][j-v] == -1:
            continue
        elif dp[i-1][j] == -1:
            if dp[i-1][j-v]+w > W:
                continue
            else:
                dp[i][j] = dp[i-1][j-v]+w
        elif dp[i-1][j-v] == -1:
            dp[i][j] = dp[i-1][j]
        else:
            if dp[i-1][j-v]+w > W:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-v]+w)

for i in range(MAX_V, 0, -1):
    if dp[N-1][i] != -1:
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(10e9)


def knapSack(i,w):
    if i<0:
        return 0
    elif dp[i].get(w)!=None:
        return dp[i][w]
    elif wt[i]>w:
        dp[i][w]=knapSack(i-1,w)
    else:
        dp[i][w]=max(val[i]+knapSack(i-1,w-wt[i]),knapSack(i-1,w))
    return dp[i][w]

n,w=mdata()
val=[0]*(n)
wt=[0]*(n)
for i in range(n):
    wt[i],val[i]=mdata()
dp=[{} for i in range(n)]
print(knapSack(n-1,w))

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.full(n*100**3+1,w+1) # dp[j]:価値総和jをちょうど実現できる最小の重さ総和
dp[0]=0
for i in range(n):# i番目までの商品について全ての重さについて調べる
    w_=wv[i][0]
    v_=wv[i][1]
    dp[v_:]=np.minimum(dp[v_:],dp[:-v_]+w_)

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

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())))
maxvalue=n*100**3
dp=np.full(maxvalue+1,w+1) # dp[j]:価値総和jをちょうど実現できる最小の重さ総和
dp[0]=0
for i in range(n):# i番目までの商品について全ての重さについて調べる
    w_=wv[i][0]
    v_=wv[i][1]
    dp[v_:]=np.minimum(dp[v_:],dp[:-v_]+w_)

print(np.where(dp<=w)[0][-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())
w=[0 for _ in range(110)]
v=[0 for _ in range(110)]
for i in range(1,N+1):
    w[i],v[i]=map(int,input().split())
dp=[[0 for i in range(110000)] for j in range(110)]
for i in range(1,110000):
    dp[0][i]=10**15

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

ans=0
for V in range(110000):
    if dp[N][V]<=W:
        ans=max(ans,V)

print(ans)

Submission status: Time Limit Exceeded

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

inf = float('inf')
dp = [[inf] * (10 ** 5 + 1) for _ in range(N + 1)]
dp[0][0] = 0

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

ans = -1

for i in range(10 ** 5 + 1):
    if dp[N][i] <= WW:
        ans = i

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

# import numpy as np

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

INF = 10 ** 18


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

    """    
    dp[ i ] : 価値 i における重さの最小値
    　
    品物一つ w,v を見ていくたびに、
    dp[ i ] = (その品物を使うパターン) or (その品物を使わないパターン)
    = min( dp[i -v] + w , dp[ i ] ) 
    を更新していけばよい。
    """

    dp = [0] + [INF] * 10 ** 5

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

    # print(dp[:30])

    ans = 0

    for i, j in enumerate(dp):
        if j <= W:
            ans = i
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

MAX_VALUE = 10 ** 5 + 100

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 = [[float('inf') for _ in range(MAX_VALUE+1)] for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for v in range(MAX_VALUE):
            if v >= goods[i][1]:
                dp[i+1][v] = min(dp[i][v-goods[i][1]]+goods[i][0],dp[i][v])
            else:
                dp[i+1][v] = dp[i][v]
    for v in range(MAX_VALUE):
        if dp[N][v] <= W:
            ans = v
    print(ans)

if __name__ == "__main__":
    main()