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

weights = [None for i in range(N)]
values = [None for i in range(N)]

# dp[i][j] = minimum weight required to get value exactly i, and by using elements 1,...,j

dp = [[float('inf') for i in range(N+1)] for j in range(1000 * N + 1)]

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

for i in range(N+1):
    dp[0][i] = 0
        
for value in range(1000 * N + 1):
    for item in range(1,N+1):
        
        # Case: dont include item
        dp[value][item] = min(dp[value][item],
                              dp[value][item-1])

        # Case: include item
        if value - values[item-1] < 0: continue
        dp[value][item] = min(dp[value][item], dp[value - values[item-1]][item-1] + weights[item-1])

highest_value = 0 
for value in range(1000 * N + 1):
    for item in range(1, N+1):
        if dp[value][item] <= W:
            highest_value = max(highest_value, value)

print(highest_value)

Submission status: Time Limit Exceeded

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

weights = [None for i in range(N)]
values = [None for i in range(N)]

# dp[i][j] = minimum weight required to get at least value i, and by using elements 1,...,j

dp = [[float('inf') for i in range(N+1)] for j in range(1000 * N + 1)]

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

for i in range(N+1):
    dp[0][i] = 0
        
for value in range(1000 * N + 1):
    for item in range(1,N+1):
        
        # Case: dont include item
        dp[value][item] = min(dp[value][item],
                              dp[value][item-1])

        # Case: include item
        if value - values[item-1] < 0: continue
        dp[value][item] = min([dp[value][item]] +
                              [dp[v][item-1] + weights[item-1]
                               for v in range(value-values[item-1],value+1)])

highest_value = 0 
for value in range(1000 * N + 1):
    for item in range(1, N+1):
        if dp[value][item] <= W:
            highest_value = max(highest_value, value)

print(highest_value)

Submission status: Time Limit Exceeded

Solution code:
import sys
from _operator import itemgetter

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

N, W = na()
maxV = 10 ** 5
dp = [[10**9+7] * (maxV+1) for i in range(N+1)]  # dp[i][v] i番目までで価値がvの時の重さの合計の最小値
dp[0][0] = 0
tp = [na() for i in range(N)]
list.sort(tp, key=itemgetter(0))
for i in range(1, N+1):
    wi, vi = tp[i - 1]
    for v in range(1, maxV+1):
        if v - vi >= 0:
            dp[i][v] = min(dp[i - 1][v], dp[i - 1][v - vi] + wi)
        else:
            dp[i][v] = dp[i - 1][v]
ans = -1
for i in range(1, N + 1):
    for v in range(1, maxV+1):
        if dp[i][v] <= W:
            ans = max(ans, v)
print(ans)

Submission status: Time Limit Exceeded

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

weights = [None for i in range(N)]
values = [None for i in range(N)]

# dp[i][j] = maximum value using at most i weight and using elements 1,...,j

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

for i in range(N):
    w, v = map(int, input().split())
    weights[i] = w
    values[i] = v
    
for weight in range(W+1):
    for item in range(1,N+1):

        # Case: dont include item
        dp[weight][item] = max(dp[weight][item],
                               dp[weight][item-1])

        # Case: include item
        dp[weight][item] = max(dp[weight][item],
                               dp[weight-1][item])
        
        if weights[item-1] > weight: continue
 
        # Case: include item
        dp[weight][item] = max(dp[weight][item],
                               values[item-1] + dp[weight - weights[item-1]][item - 1])
    
print(max(dp[-1]))

Submission status: Time Limit Exceeded

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

# dd[idx][v] represents the minimum weight that we can get if total value is v
# and allowed to use the first idx items.
dd = {}
MMAX = n*1000+1

for nn in range(n+1):
    dd[(nn, 0)] = 0

for nn in range(1, n+1):
    www, nu = [int(x) for x in input().split()]
    for v in range(1, MMAX):
        # don't use item nn-1
        cur = None
        item = (nn-1, v)
        if item in dd:
            cur = dd[item]

        # use item nn-1
        if nu <= v:
            rem_v = v - nu
            item = (nn-1, rem_v)
            if item in dd:
                cand = dd[item] + www
                if cand <= w and (cur is None or cand < cur):
                    cur = cand

        if cur is not None:
            dd[(nn, v)] = cur

done = False
for v in range(MMAX-1, -1, -1):
    if done:
        break
    for nn in range(n+1):
        item = (nn, v)
        if item in dd:
            print(v)
            done = True
            break

if not done:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
n, w = [int(x) for x in input().split()]
d = []
for _ in range(n):
    ww, nu = [int(x) for x in input().split()]
    d.append((ww, nu))

# dd[idx][v] represents the minimum weight that we can get if total value is v
# and allowed to use the first idx items.
dd = {}
MMAX = n*1000+1
#dd[(0, 0)] = 0
#for v in range(MMAX):
#    dd[0][v] = -1

for nn in range(n+1):
    dd[(nn, 0)] = 0

for nn in range(1, n+1):
    www, nu = d[nn-1]
    for v in range(1, MMAX):
        # don't use item nn-1
        cur = None
        item = (nn-1, v)
        if item in dd:
            cur = dd[item]

        # use item nn-1
        if nu <= v:
            rem_v = v - nu
            item = (nn-1, rem_v)
            if item in dd:
                cand = dd[item] + www
                if cand <= w and (cur is None or cand < cur):
                    cur = cand

        if cur is not None:
            dd[(nn, v)] = cur

done = False
for v in range(MMAX-1, -1, -1):
    if done:
        break
    for nn in range(n+1):
        item = (nn, v)
        if item in dd:
            print(v)
            done = True
            break

if not done:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n, w = [int(x) for x in input().split()]
d = []
for _ in range(n):
    ww, nu = [int(x) for x in input().split()]
    d.append((ww, nu))

# dd[idx][v] represents the minimum weight that we can get if total value is v
# and allowed to use the first idx items.
dd = {}
MMAX = n*1000+1
#dd[(0, 0)] = 0
#for v in range(MMAX):
#    dd[0][v] = -1

for nn in range(n+1):
    dd[(nn, 0)] = 0

for nn in range(1, n+1):
    www, nu = d[nn-1]
    for v in range(1, MMAX):
        # don't use item nn-1
        cur = None
        item = (nn-1, v)
        if item in dd:
            cur = dd[item]

        # use item nn-1
        if nu <= v:
            rem_v = v - nu
            item = (nn-1, rem_v)
            if item in dd:
                cand = dd[item] + www
                if cand <= w and (cur is None or cand < cur):
                    cur = cand

        if cur is not None:
            dd[(nn, v)] = cur

done = False
for v in range(MMAX-1, -1, -1):
    if done:
        break
    for nn in range(n+1):
        item = (nn, v)
        if item in dd:
            print(v)
            done = True
            break

if not done:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
def A(w, v, n,V):
    mem=[0 for i in range(V+1)]
    if n == 0 or V == 0:
        return 0
 
    for i in range(n):
        for j in range(V,w[i]-1,-1):
            m=v[i]+ mem[j - w[i]]
            if m>mem[j]:
                mem[j]=m
    return mem[V]
n,V=input().split()
n,V=int(n),int(V)
 
w=[0]*n
v=[0]*n
for i in range(n):
  x,y=input().split()
  w[i],v[i]=int(x),int(y)
 
print(A(w,v,n,V))

Submission status: Time Limit Exceeded

Solution code:
N,W = list(map(int, input().split()))
m = []
v = []
for i in range(N):
    a,b = map(int, input().split())
    m.append(a)
    v.append(b)
sum_v = sum(v)
dp = [[float('inf') for i in range(sum_v+1001)]for j in range(N+1)]
for i in range(N):
    for j in range(sum_v+1):
        if j == 0:
            dp[i][j] = 0
        if j != float('inf'):
            dp[i+1][j+v[i]] = min(dp[i][j+v[i]],dp[i][j] + m[i])
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])

for i in range(sum(v)+1):
    if  dp[-1][sum(v)-i] <= W:
        print(sum(v)-i)
        break

Submission status: Time Limit Exceeded

Solution code:
N,W = list(map(int, input().split()))
m = []
v = []
for i in range(N):
    a,b = map(int, input().split())
    m.append(a)
    v.append(b)
sum_v = sum(v)
dp = [[float('inf') for i in range(sum_v+1)]for j in range(N+1)]
for i in range(N):
    for j in range(sum(v)+1):
        if j == 0:
            dp[i][j] = 0
        if j != float('inf') and sum_v >= j+v[i]:
            dp[i+1][j+v[i]] = min(dp[i][j+v[i]],dp[i][j] + m[i])
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])

for i in range(sum(v)+1):
    if  dp[-1][sum(v)-i] <= W:
        print(sum(v)-i)
        break

Submission status: Time Limit Exceeded

Solution code:
N,W = list(map(int, input().split()))
m = []
v = []
for i in range(N):
    a,b = map(int, input().split())
    m.append(a)
    v.append(b)
    
dp = [[10**50 for i in range(10**10)]for j in range(N+100)]
dp[0][v[0]] = m[0]
for i in range(N):
    for j in range(sum(v)+1):
        if j == 0:
            dp[i][j] = 0
        if dp[i][j] != 10**50:
            dp[i+1][j+v[i]] = min(dp[i+1][j+v[i]],dp[i][j] + m[i])
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])

for i in range(sum(v)+1):
    if  dp[-1][sum(v)-i] <= W:
        print(sum(v)-i)
        break

Submission status: Time Limit Exceeded

Solution code:
N,W = list(map(int, input().split()))
m = []
v = []
dp = [[0 for i in range(W+1)]for j in range(N+1)]
for i in range(N):
    a,b = map(int, input().split())
    m.append(a)
    v.append(b)

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


print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000)

N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for _ in range(N)]
wv.sort()

mem = dict()

def knapsack(i, w) :
    if i == N :
        return 0
    
    if (i, w) in mem :
        return mem[(i, w)]
    
    if w + wv[i][0] <= W :
        mem[(i, w)] = max(knapsack(i+1, w+wv[i][0])+wv[i][1], knapsack(i+1, w))
        return mem[(i, w)]
    else :
        return 0
        
print(knapsack(0, 0))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000)

N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for _ in range(N)]
wv.sort()

def knapsack(i, w) :
    if i == N :
        return 0
        
    if w + wv[i][0] <= W :
        return max(knapsack(i+1, w+wv[i][0])+wv[i][1], knapsack(i+1, w))
    else :
        return 0
        
print(knapsack(0, 0))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000)

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

def knapsack(i, w) :
    if i == N :
        return 0
        
    if w + wv[i][0] <= W :
        return max(knapsack(i+1, w+wv[i][0])+wv[i][1], knapsack(i+1, w))
    else :
        return knapsack(i+1, w)
        
print(knapsack(0, 0))

Submission status: Time Limit Exceeded

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################


# https://qiita.com/drken/items/dc53c683d6de8aeacf5a#e-問題---knapsack-2


# N個の荷物、ナップザックの容量はW
N, W = map(int, input().split())
w = [0] * N
v = [0] * N

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

# 1 <= W <= 10^9なので横軸をWにするとテーブルがでかすぎる
# そのかわりにVの方を横軸にする


# 価値の総合計はまだ不明なので、適当にでかい値にしとく
# 最上部と最左部に0が入るので、その分を+1
V = 10**5
#dp = [ [0 for _ in range(W+1)] for _ in range(N+1) ]
dp = [ [float('inf') for _ in range(V+1)] for _ in range(N+1) ]

# 最小値を求めるので、上記でinfが入ってるので、初期値は0をいれる必要がある
dp[0][0] = 0

# dp[i][sum_v] = これまで(i-1)番目までの品物から価値がsum_v以上になるように選んだときの、重さの総和の最小値
for i in range(N):
    for sum_v in range(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])


# 中身がWなので、W以下であるうちのsum_vの最大値を求めればいい
for sum_v in range(V):
    # 最終行だけ見ればいいので、端からsum_vの最大値をなめるだけ
    if dp[N][sum_v] <= W:
        ans = sum_v

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main2(): 
    N, W = LI()
    things = []
    for i in range(N):
        things.append(LI())

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

    for i, wv in enumerate(things):  # 10**2
        w, v = wv
        if i == 0:
            for weight in range(W+1):  # 10**5
                knapsack_dp[i][weight] = 0 if weight < w else v
        else:
            for weight in range(W+1):
                if weight-w < 0:
                    knapsack_dp[i][weight] = knapsack_dp[i-1][weight]
                else:
                    knapsack_dp[i][weight] = max(knapsack_dp[i-1][weight], knapsack_dp[i-1][weight-w]+v)

    print(knapsack_dp[N-1][W])

def main():
    N, W = LI()
    things = []
    for i in range(N):
        things.append(LI())

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

    # knapsack_dp[考慮した品物][その重さピッタリの重さ] = 価値 とする。
    for i, wv in enumerate(things):  # 10**2
        w, v = wv
        if i == 0:
            for weight in range(W+1):  # 10**5
                knapsack_dp[i][weight] = 0 if weight != w else v
        else:
            for weight in range(W+1):
                if weight-w < 0:
                    knapsack_dp[i][weight] = knapsack_dp[i-1][weight]
                else:
                    knapsack_dp[i][weight] = max(knapsack_dp[i-1][weight], knapsack_dp[i-1][weight-w]+v)

    print(max(knapsack_dp[N-1]))

main()

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


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

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
#N,W = [3,8]
wvlist = [list(map(int,input().split())) for _ in range(N)]
INF = 10**15
ans = INF
#初期条件
dp = [[INF for _ in range(N*1000+1)] for i in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for v in range(N*1000+1):
        if v-wvlist[i][1]>=0:
            dp[i+1][v] = min(dp[i+1][v],dp[i][v-wvlist[i][1]]+wvlist[i][0])
        dp[i+1][v] = min(dp[i+1][v],dp[i][v])
        
for i in range(N*1000+1):
    if W >= dp[N][i]:
        ans = i
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    N, W = map(int, input().split())
    dp = np.zeros(W+1, dtype=np.int16)
    for _ in range(N):
        w, v = map(int, input().split())
        np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
    print(dp[-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, w = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(n)]
table = np.zeros(w+1, dtype=np.int16)

for i in range(n):
    l = table[:-wv[i][0]]
    r = table[wv[i][0]:]
    np.maximum(l + wv[i][1], r, out = r)

print(table[w])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
from copy import *

N, W = map(int, input().split())
MV = N * 10**3 + 1
INF = float('inf')
dp1 = [INF] * MV
dp1[0] = 0
for i in range(N):
    dp2 = [INF] * MV
    w, v = map(int, input().split())
    for j in range(MV):
        dp2[j] = min(dp1[j], dp1[j-v]+w)
    dp1 = deepcopy(dp2)
for i in range(MV-1, -1, -1):
    if dp1[i] <= W:
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:
#E
n,W = list(map(int,input().split()))
w = [0]*(n+1)
v = [0]*(n+1)
for i in range(1,n+1):
    w[i],v[i]=list(map(int,input().split()))
V = n*max(v)

dp = [[float('inf') for i in range(V+1)] for j in range(n+1)]
#i番目(1:n)の品物までを使って価値の総和がjになるようなときの重さの最小値
dp[0][0] = 0
for i in range(1,n+1):
    for j in range(V+1): #価値
        if j-v[i]>=0:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
        else:
            dp[i][j] = dp[i-1][j]
# for i in range(n+1):
#     print(dp[i])
print(max([j for j in range(V+1) if dp[n][j]<=W]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from functools import lru_cache

@lru_cache(None)
def solve(i,w):
    if i<0:
        return 0
    if w<WV[i][0]:
        return solve(i-1,w)
    return max(solve(i-1,w),solve(i-1,w-WV[i][0])+WV[i][1])

n,w=map(int,input().split())
WV=[tuple(map(int,input().split())) for _ in range(n)]
print(solve(n-1,w))

Submission status: Time Limit Exceeded

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

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

for i in range(1, N+1):
    for v in range(0, 100001):
        weight = WV[i-1][0]
        value = WV[i-1][1]
        dp[i][v] = min(dp[i-1][v], dp[i-1][v-value]+weight)
res = 0
for v, w in enumerate(dp[-1]):
    if w <= W: res = v

print(res)

Submission status: Time Limit Exceeded

Solution code:
def knapsack_rec(target, W, V): # target=knapsack weight
    P = {}
    P[target] = 0 # default + max
    max_ = 0

    for vi in range(len(V)):
        we = W[vi]
        va = V[vi]
        for i in list(P.keys()):
            if i >= we:
                prev = P[i-we] if (i-we) in P else -1
                piva = P[i] + va
                if prev < piva:
                    P[i - we] = piva
                    if piva > max_:
                        max_ = piva

    return max_

assert knapsack_rec(15, [6, 5, 6, 6, 3, 7], [5, 6, 4, 6, 5, 2]) == 17

if __name__ == "__main__":
    import sys
    n, w, *r = map(int, sys.stdin.read().split())
    W, V = r[::2], r[1::2]
    ans = knapsack_rec(w, W, V)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def knapsack_rec(target, W, V): # target=knapsack weight
    P = {}
    P[target] = 0 # default + max
    max_ = 0

    for vi in range(len(V)):
        we = W[vi]
        va = V[vi]
        for i in range(we, target + 1):
            if i in P:
                prev = P.get(i - we, -1)
                if prev < P[i] + va:
                    P[i - we] = P[i] + va
                    max_ = max(P[i - we], max_)

    return max_

assert knapsack_rec(15, [6, 5, 6, 6, 3, 7], [5, 6, 4, 6, 5, 2]) == 17

if __name__ == "__main__":
    import sys
    n, w, *r = map(int, sys.stdin.read().split())
    W, V = r[::2], r[1::2]
    ans = knapsack_rec(w, W, V)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def knapsack_rec(target, W, V): # target=knapsack weight
    P = {}
    P[target] = 0 # default + max

    for vi in range(len(V)):
        we = W[vi]
        va = V[vi]
        for i in range(we, target + 1):
            if i in P:
                prev = P.get(i - we, -1)
                if prev < P[i] + va:
                    P[i - we] = P[i] + va

    return max(P.values())

assert knapsack_rec(15, [6, 5, 6, 6, 3, 7], [5, 6, 4, 6, 5, 2]) == 17

if __name__ == "__main__":
    import sys
    n, w, *r = map(int, sys.stdin.read().split())
    W, V = r[::2], r[1::2]
    ans = knapsack_rec(w, W, V)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
"""解説
https://qiita.com/drken/items/dc53c683d6de8aeacf5a#e-%E5%95%8F%E9%A1%8C---knapsack-2

・まず制約を見る
Wの最大値が10**9なので、dp[i][w] みたいにすると、間に合わない

N=100, viの最大値が10**3 なので、N+max(vi) = 10**5 なので、viを使うといけそう

dp[i][v] := i番目までを選んだ時の、価値がv以上のときの、重さの総和の最小値


・DPテーブル
      i   =   0      1      2      3      4      5
例: (w,v) = (2,3), (1,2), (3,6), (2,1), (1,3), (5,85)

i/v | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | ...
----------------------------------------------------------------------
0   | 0 | 2 | 2 | 2 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞  | ∞  | ∞  | ∞  | ... 
1   | 0 | 1 | 1 | 2 | 3 | 3 | ∞ | ∞ | ∞ | ∞ | ∞  | ∞  | ∞  | ∞  | ...
2   | 0 | 1 | 1 | 2 | 3 | 3 | 3 | 4 | 4 | 5 | 6  | 6  | ∞  | ∞  | ...
3   |
4   |
5   |

     i    =    0        1        2        3
例: (w,v) = (1,100), (1,100), (1,100), (1,100)

i/v | 0 | 1 |...|100|101|...|200|201|...|300|301|...|400|401|...|500|501|...
----------------------------------------------------------------------------
0   | 0 | 1 | 1 | 1 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ 
1   | 0 | 1 | 1 | 1 | 2 | 2 | 2 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞
2   | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞
3   | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 4 | 4 | 4 | ∞ | ∞ | ∞ | ∞ | ∞

"""

def solve():
    N, W = list(map(int, input().split()))
    Ws, Vs = [], []
    """
    for i in range(N):
        w, v = list(map(int, input().split()))
        Ws.append(w)
        Vs.append(v)
    """
    M = (10**3) * N
    
    # dp[i][v] := i番目までを選んだ時の、価値がv以上のときの、重さの総和の最小値
    dp = [[float("inf") for _ in range(0, M+1)] for __ in range(0, N)]

    # 初期値
    for i in range(0, N):
        dp[i][0] = 0 # 価値0の重さの最小値は0
    
    noww, nowv = list(map(int, input().split()))
    for v in range(1, M+1):
        if v <= nowv:
            dp[0][v] = noww
    
    # dpを埋める
    for i in range(1, N):
        noww, nowv = list(map(int, input().split()))
        for v in range(0, M+1):  
            if v-nowv >= 0:
                dp[i][v] = min(dp[i-1][v], dp[i-1][v-nowv]+noww)
            else:
                dp[i][v] = min(dp[i-1][v], noww)
            
            """
            if v-Vs[i] >= 0:
                dp[i][v] = min(dp[i][v], dp[i-1][v-Vs[i]]+Ws[i])  # 選んだとき
            dp[i][v] = min(dp[i][v], dp[i-1][v])
            """

    # 答えを出す
    for v in range(M, -1, -1):
        if dp[N-1][v] <= W:
            ans = v
            break
    """
    for v in range(0, 10**5+1):
        if dp[N-1][v] <= W:
            ans = v
    """
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
"""解説
https://qiita.com/drken/items/dc53c683d6de8aeacf5a#e-%E5%95%8F%E9%A1%8C---knapsack-2

・まず制約を見る
Wの最大値が10**9なので、dp[i][w] みたいにすると、間に合わない

N=100, viの最大値が10**3 なので、N+max(vi) = 10**5 なので、viを使うといけそう

dp[i][v] := i番目までを選んだ時の、価値がv以上のときの、重さの総和の最小値


・DPテーブル
      i   =   0      1      2      3      4      5
例: (w,v) = (2,3), (1,2), (3,6), (2,1), (1,3), (5,85)

i/v | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | ...
----------------------------------------------------------------------
0   | 0 | 2 | 2 | 2 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞  | ∞  | ∞  | ∞  | ... 
1   | 0 | 1 | 1 | 2 | 3 | 3 | ∞ | ∞ | ∞ | ∞ | ∞  | ∞  | ∞  | ∞  | ...
2   | 0 | 1 | 1 | 2 | 3 | 3 | 3 | 4 | 4 | 5 | 6  | 6  | ∞  | ∞  | ...
3   |
4   |
5   |

     i    =    0        1        2        3
例: (w,v) = (1,100), (1,100), (1,100), (1,100)

i/v | 0 | 1 |...|100|101|...|200|201|...|300|301|...|400|401|...|500|501|...
----------------------------------------------------------------------------
0   | 0 | 1 | 1 | 1 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ 
1   | 0 | 1 | 1 | 1 | 2 | 2 | 2 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞
2   | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞
3   | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 4 | 4 | 4 | ∞ | ∞ | ∞ | ∞ | ∞

"""

def solve():
    N, W = list(map(int, input().split()))
    Ws, Vs = [], []
    for i in range(N):
        w, v = list(map(int, input().split()))
        Ws.append(w)
        Vs.append(v)
    M = (10**3) * N
    
    # dp[i][v] := i番目までを選んだ時の、価値がv以上のときの、重さの総和の最小値
    dp = [[float("inf") for _ in range(0, M+1)] for __ in range(0, N)]

    # 初期値
    for i in range(0, N):
        dp[i][0] = 0 # 価値0の重さの最小値は0
    
    for v in range(1, M+1):
        if v <= Vs[0]:
            dp[0][v] = Ws[0]
    
    # dpを埋める
    for i in range(1, N):
        for v in range(0, M+1):
            
            if v-Vs[i] >= 0:
                dp[i][v] = min(dp[i-1][v], dp[i-1][v-Vs[i]]+Ws[i])
            else:
                dp[i][v] = min(dp[i-1][v], Ws[i])
            
            """
            if v-Vs[i] >= 0:
                dp[i][v] = min(dp[i][v], dp[i-1][v-Vs[i]]+Ws[i])  # 選んだとき
            dp[i][v] = min(dp[i][v], dp[i-1][v])
            """

    # 答えを出す
    for v in range(M, -1, -1):
        if dp[N-1][v] <= W:
            ans = v
            break
    """
    for v in range(0, 10**5+1):
        if dp[N-1][v] <= W:
            ans = v
    """
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
"""解説
https://qiita.com/drken/items/dc53c683d6de8aeacf5a#e-%E5%95%8F%E9%A1%8C---knapsack-2

・まず制約を見る
Wの最大値が10**9なので、dp[i][w] みたいにすると、間に合わない

N=100, viの最大値が10**3 なので、N+max(vi) = 10**5 なので、viを使うといけそう

dp[i][v] := i番目までを選んだ時の、価値がv以上のときの、重さの総和の最小値


・DPテーブル
      i   =   0      1      2      3      4      5
例: (w,v) = (2,3), (1,2), (3,6), (2,1), (1,3), (5,85)

i/v | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | ...
----------------------------------------------------------------------
0   | 0 | 2 | 2 | 2 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞  | ∞  | ∞  | ∞  | ... 
1   | 0 | 1 | 1 | 2 | 3 | 3 | ∞ | ∞ | ∞ | ∞ | ∞  | ∞  | ∞  | ∞  | ...
2   | 0 | 1 | 1 | 2 | 3 | 3 | 3 | 4 | 4 | 5 | 6  | 6  | ∞  | ∞  | ...
3   |
4   |
5   |

     i    =    0        1        2        3
例: (w,v) = (1,100), (1,100), (1,100), (1,100)

i/v | 0 | 1 |...|100|101|...|200|201|...|300|301|...|400|401|...|500|501|...
----------------------------------------------------------------------------
0   | 0 | 1 | 1 | 1 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ 
1   | 0 | 1 | 1 | 1 | 2 | 2 | 2 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞
2   | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞
3   | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 4 | 4 | 4 | ∞ | ∞ | ∞ | ∞ | ∞

"""

def solve():
    N, W = list(map(int, input().split()))
    Ws, Vs = [], []
    for i in range(N):
        w, v = list(map(int, input().split()))
        Ws.append(w)
        Vs.append(v)
    
    # dp[i][v] := i番目までを選んだ時の、価値がv以上のときの、重さの総和の最小値
    dp = [[float("inf") for _ in range(0, 10**5+1)] for __ in range(0, N)]

    # 初期値
    for i in range(0, N):
        dp[i][0] = 0 # 価値0の重さの最小値は0
    
    for v in range(1, 10**5+1):
        if v <= Vs[0]:
            dp[0][v] = Ws[0]
    
    # dpを埋める
    for i in range(1, N):
        for v in range(0, 10**5+1):
            
            if v-Vs[i] >= 0:
                dp[i][v] = min(dp[i-1][v], dp[i-1][v-Vs[i]]+Ws[i])
            else:
                dp[i][v] = min(dp[i-1][v], Ws[i])
            
            """
            if v-Vs[i] >= 0:
                dp[i][v] = min(dp[i][v], dp[i-1][v-Vs[i]]+Ws[i])  # 選んだとき
            dp[i][v] = min(dp[i][v], dp[i-1][v])
            """

    # 答えを出す
    for v in range(10**5, -1, -1):
        if dp[N-1][v] <= W:
            ans = v
            break
    """
    for v in range(0, 10**5+1):
        if dp[N-1][v] <= W:
            ans = v
    """
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, wn = map(int, input().split())
    w = [0 for _ in range(n)]
    v = w[:]
    for i in range(n):
        w[i], v[i] = map(int, input().split())
    dp = [[0 for _ in range(wn + 1)] for _ in range(n)]  # dp[n][wn + 1]を定義
    for i in range(w[0], wn + 1):
        dp[0][i] = v[0]
    for i in range(1, n):
        for j in range(wn + 1):
            if j < w[i]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
    print(max(dp[n - 1]))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

v_total = sum([x[1] for x in wv])
dp = [0] + [float("inf")]*v_total

for i in range(n):
    for j in range(v_total, wv[i][1]-1, -1):
        dp[j] = min(dp[j], dp[j-wv[i][1]]+wv[i][0])

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

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
wt = [0] * (n)
vl = [0] * (n)
for x in range(n):
    wt[x], vl[x] = map(int, input().split())

dp = [[0 for y in range(w + 1)] for x in range(n + 1)]

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

dp = [[10**15 for sum_v in range(10**5+100)] for i in range(N+100)]

for i in range(N):
    for sum_v in range(10**5+50):

        dp[0][0] = 0

        # i-1番目の品物を選ぶ場合
        if sum_v-items[i][1] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v],
                                 dp[i][sum_v-items[i][1]]+items[i][0])

        # i-1番目の品物を選ばない場合
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])

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