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: Accepted

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N, W = map(int, input().split())
w = [0] * N
v = [0] * N

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

#dp[i][j]...(i + 1)番目までの品物を考慮し，価値の合計がjとなるときの重さの合計
V = (10 ** 3) * N + 5
Inf = 10 ** 18
dp = [[Inf] * V for _ in range(N)]

#for i in range(v[0], V):
    #dp[0][i] = w[0]
dp[0][0] = 0
dp[0][v[0]] = w[0]

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
# D-Knapsack 1
N,W = map(int,input().split())
Weight = [0 for _ in range(N)]
Value = [0 for _ in range(N)]
for i in range(N):
    Weight[i],Value[i] = map(int,input().split())

MAX_N = 110
MAX_V = 100100

# dp[i+1][v]:= i番目までの品物の中からスコアがv以上になるように選んだときの、重さの総和の最小値
dp = [[10**15 for i in range(MAX_V)] for j in range(MAX_N)]
dp[0][0] = 0

for i in range(N):
    for sum_v in range(MAX_V):
        # i番目を選ぶ場合
        if sum_v - Value[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - Value[i]] + Weight[i])

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

ans = 0
# 重さの総和<=Wである最大スコアを探す
for sum_v in range(MAX_V):
    if dp[N][sum_v] <= W:
        ans = sum_v
print(ans)

Submission status: Accepted

Solution code:
# D-Knapsack 1
N,W = map(int,input().split())
Weight = [0 for _ in range(N)]
Value = [0 for _ in range(N)]
for i in range(N):
    Weight[i],Value[i] = map(int,input().split())

MAX_N = 110
MAX_V = 100100
dp = [[10**15 for i in range(MAX_V)] for j in range(MAX_N)]
dp[0][0] = 0

for i in range(N):
    # あらゆる合計重量sum_wに対して品物iを入れるべきか計算する
    for sum_v in range(MAX_V):
        # i番目を選ぶ場合
        if sum_v - Value[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - Value[i]] + Weight[i])

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


ans = 0
for sum_v in range(MAX_V):
    if dp[N][sum_v] <= W:
        ans = sum_v
print(ans)

Submission status: Accepted

Solution code:
INF = float('inf')
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(N)]
V = 1000*N
dp = [[INF]*(V+1) for _ in range(N+1)]
dp[0][0]=0
for i in range(N):
    for j in range(V+1):
        if j-wv[i][1] >= 0:
            dp[i+1][j] = min(dp[i][j-wv[i][1]]+wv[i][0],dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

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

Submission status: Accepted

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

max_value = 10**5+10
INF = 10**9+1
dp = [[INF for _ in range(max_value)] for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(max_value):
        if j - value[i] >= 0:
            dp[i+1][j] = min(dp[i][j-value[i]]+weight[i], dp[i][j])
        else:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j]) 

ans = 0
for j in range(max_value):
    if dp[N][j] <= W:
        ans = j

print(ans)

Submission status: Accepted

Solution code:
def LI(): return [int(x) for x in input().split()]
def II(): return int(input())

N,W=LI()
INL = [tuple(LI()) for i in range(N)]
DP=[[10**18]*100001 for _ in range(N+1)]
DP[0][0] = 0

for i, (w, v) in enumerate(INL, 1):
    # print(i,w,v)
    for j in range(100001):
        DP[i][j] = min(DP[i-1][j], DP[i][j])
        if (j+v) <= 100000:
            DP[i][j+v] = min(DP[i-1][j+v], DP[i-1][j]+w)

res = 0
for v, w in enumerate(DP[N]):
    if w <= W:
        res = max(res, v)

# print(DP[1][0], DP[1][10])
print(res)

Submission status: Accepted

Solution code:

N,W = map(int,input().split())
max_v = 1000
wv_l= []
for i in range(N):
    wv_l.append(list(map(int,input().split())))
DP = [[10**10]*(max_v*N +1) for i in range(N+1)]
DP[0][0] = 0
for i in range(N):
    for sum_v in range(max_v*N +1):
#        print(DP)
#        print(i,sum_w)
        if sum_v-wv_l[i][1] >= 0:
            DP[i+1][sum_v] = min(DP[i+1][sum_v],DP[i][sum_v-wv_l[i][1]] + wv_l[i][0])
        DP[i+1][sum_v] = min(DP[i+1][sum_v],DP[i][sum_v])

#print(DP[N])
ans = -1
for i in range(len(DP[N])):
    if DP[N][i] <= W:
        ans = max(ans,i)
#ans = bisect.bisect_right(DP[N], W)
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

for w, v in WV:
	for i in range(MAX_V - 1, v - 1, -1):
		dp[i] = min(dp[i], dp[i - v] + w)
	#print(dp)

max_v = 0
for v, w in enumerate(dp):
	if w <= W:
		max_v = max(max_v, v)
print(max_v)

Submission status: Accepted

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

w=[]
v=[]

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

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


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

Submission status: Accepted

Solution code:
from subprocess import*
call(('pypy3','-c',"""
I=lambda:list(map(int,input().split()))
n,W=I()
g=[0]+[I()for _ in range(n)]
vm=n*1000+1
dp=[[0]+[10**18]*vm]+[[0]*vm for _ in range(n)]
for i in range(1,n+1):
    w,v=g[i]
    for j in range(vm):
        k=j-v
        if k<0:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=min(dp[i-1][j],dp[i-1][k]+w)
for j in range(vm)[::-1]:
    if dp[n][j]<=W:
        print(j)
        break
"""))

Submission status: Accepted

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

inf = float("inf")

max_v = 1000 * N + 1
dp = [inf for _ in range(max_v)]
dp[0] = 0
sum_v = 0

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

ans = 0
for sum_v in range(max_v):
    if dp[sum_v] <= W:
        ans = sum_v
print(ans)

Submission status: Accepted

Solution code:
#pypy3でAC

import sys
def input():
    return sys.stdin.readline()[:-1]

N, W = map(int, input().split())
w, v = [], []
for i in range(1, N+1):
    _w, _v = map(int, input().split())
    w.append(_w)
    v.append(_v)

V = sum(v)
#i個目までの品物から価値がj以上になるように選んだときの重さの最小値
dp = [[float("inf")]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
"""
i番目を選ぶ場合
dp[i][j] = dp[i-1][j-v] + w
i番目を選ばない場合
dp[i][j] = dp[i-1][j]
"""

for i in range(1, N+1):
    for j in range(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]

# dp[N][j]がW以下であるような最大のjを探す
for j in range(V+1):
    if dp[N][j] <= W:
        ans = j
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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())

n = (N+1)*max(v)

inf = 10**14

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

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

ans = 0
for i in range(n):
    if dp[N][i] <= W:
        ans = i
    else:
        break

print(ans)

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
goods = [list(map(int, input().split())) for _ in range(n)]
dp = [[float("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):
        if 0 <= j - goods[i][1]:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - goods[i][1]] + goods[i][0])
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])


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

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
items=[tuple(map(int,input().split())) for i in range(N)]
items.insert(0, (0,0))

v_max=sum([x[1] for x in items])

dp=[[10**13 for _ in range(v_max+1)] for _ in range(N+1)]
dp[0][0] = 0

for i in range(1,N+1):
    for j in range(v_max+1):
        # print(i,j)
        # take item
        if j-items[i][1]>=0:
            dp[i][j]=dp[i-1][j-items[i][1]]+items[i][0]
        
        dp[i][j]=min(dp[i][j],dp[i-1][j])

# print(dp[N])

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
N,W=map(int,input().split())
w,v=[0]*N,[0]*N

for i in range(N):
    w[i],v[i]=map(int,input().split())
V=sum(v)
dp=[[float('inf')]*(V+1) for i in range(N+1)] #初期化はfor より *の方が早い

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

for j in range(V+1):
    if dp[N][j]<=W:
        res=j
print(res)
# stdinあり

Submission status: Accepted

Solution code:
#import sys
#input=sys.stdin.readline
N,W=map(int,input().split())
w,v=[0]*N,[0]*N

for i in range(N):
    w[i],v[i]=map(int,input().split())
V=sum(v)
dp=[[float('inf')]*(V+1) for i in range(N+1)] #初期化はfor より *の方が早い

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

for j in range(V+1):
    if dp[N][j]<=W:
        res=j
print(res)
# stdinなし

Submission status: Accepted

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

N, W = map(int, input().split())
w, v = [0] * N, [0] * N
for i in range(N):
	w[i], v[i] = map(int, input().split())
V = sum(v)
dp = [[float("inf")] * (V + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
	for j in range(V + 1):
		if j - v[i] >= 0:
			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)
# copy

Submission status: Accepted

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

V = sum(v)
dp = [[float("inf")] * (V + 1) for _ in range(N + 1)]
"""
for j in range(V + 1):
	dp[0][j] = 0
"""
dp[0][0] = 0
# dp[i][j]:i番目までの品物から価値がj以上になるよう選んだときの重さの総和の最小値
for i in range(N):
	for j in range(V + 1):
		# i+1番目を選ぶ場合
		if j - v[i] >= 0:
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v[i]] + w[i])
		# i+1番目を選ばない場合
		dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

# print(dp)

# dp[N][j]がW以下であるようなjの最大値が答えになる
ans = 0
for j in range(V + 1):
	if dp[N][j] <= W:
		ans = j

print(ans)

Submission status: Accepted

Solution code:
def main():
    N, W = map(int, input().split())
    MV = 10**5
    dp = [float('INF')] * (MV + 1)
    dp[0] = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(MV, -1, -1):
            if v > i:
                tmp = w
            else:
                tmp = dp[i - v] + w
            dp[i] = min(dp[i], tmp)
    ans = 0
    for v, w in enumerate(dp):
        if W >= w:
            ans = max(ans, v)
        else:
            break
    print(ans)


main()

Submission status: Accepted

Solution code:
def main():
    N, W = map(int, input().split())
    Ws = []
    Vs = []
    for _ in range(N):
        w, v = map(int, input().split())
        Ws.append(w)
        Vs.append(v)
    mv = sum(Vs)
    dp = [[float('INF')] * (mv + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(mv + 1):
            if Vs[i] > j:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = min(dp[i][j], dp[i][j - Vs[i]] + Ws[i])
    for j in range(mv, -1, -1):
        if W >= dp[N][j]:
            print(j)
            break


main()

Submission status: Accepted

Solution code:
def main():
    N, W = map(int, input().split())
    Ws = []
    Vs = []
    for _ in range(N):
        w, v = map(int, input().split())
        Ws.append(w)
        Vs.append(v)
    mv = sum(Vs)
    dp = [[float('INF')] * (mv + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(mv + 1):
            if Vs[i] > j:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = min(dp[i][j], dp[i][j - Vs[i]] + Ws[i])
    ans = 0
    for r in dp:
        for v, w in enumerate(r):
            if W >= w:
                ans = max(ans, v)
    print(ans)


main()

Submission status: Accepted

Solution code:
n,W=map(int, input().split())
a=[]
max_v=0
for _ in range(n):
    w,v=map(int, input().split())
    a.append((w,v))
    max_v+=v

dp=[[float('inf') for j in range(max_v+1)] for i in range(n+1)] # dp[n][v] = min weight using up to n-th items and value = v

for i in range(1,n+1):
    w,v=a.pop()
    for j in range(max_v+1):
        if j-v>=0:
            dp[i][j]=min(
                dp[i-1][j-v]+w # use j-th item (w,v)
                ,dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
    dp[i][v]=min(w,dp[i-1][v])
    
ans=0
for j in range(max_v+1):
    if dp[n][j]<=W:
        ans=j
print(ans)

Submission status: Accepted

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

for i in range(1, N+1):
    weight = wv[i-1][0]
    value = wv[i-1][1]
    for j in range(V_MAX):
        if j < value:
            dp[i][j] = min(dp[i-1][j], weight)
        else:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-value] + weight)

for i in range(V_MAX):
    if dp[N][i] > W:
        print(i-1)
        break
else:
    print(i)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[float('inf')] * (N * 1000 + 1) for _ in range(N+1)]
    dp[0][0] = 0

    for i, (cw, cv) in enumerate(zip(w, v)):
        for j in range(N * 1000 + 1):
            dp[i+1][j] = dp[i][j]
            if 0 <= (j - cv) and (dp[i][j - cv] + cw) <= W:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j - cv] +  cw)

    return max([cv for cv, cw in enumerate(dp[-1]) if isfinite(cw)])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    result = solve(N, W, w, v)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
items = []
INF = 10**12
for _ in range(N):
    items.append(tuple(map(int, input().split())))
MAX_V = sum([v for _, v in items])
dp = [[INF for j in range(MAX_V+1)] for i in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    w, v = items[i-1]
    for j in range(MAX_V+1):
        if j - v >= 0:
            dp[i][j] = min(dp[i-1][j-v] + w, dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
for v in range(MAX_V, -1, -1):
    if dp[N][v] <= W:
        break
print(v)

Submission status: Accepted

Solution code:
import numpy as np

N, W = map(int, input().split())
items = []
for _ in range(N):
    items.append(tuple(map(int, input().split())))
v_max = sum([i[1] for i in items])
INF = 10**12
dp = np.array([[INF for j in range(v_max+1)] for _ in range(N+1)])
dp[0, 0] = 0
for i in range(1, N+1):
    w, v = items[i-1]
    dp[i, :v] = dp[i-1, :v]
    dp[i, v:] = np.minimum(dp[i-1, :-v] + w, dp[i-1, v:])
ans = 0
for v in range(v_max, -1, -1):
    if dp[N][v] <= W:
        ans = v
        break
print(ans)

Submission status: Accepted

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

#import math
INF = 10 ** 12 # math.inf
V = 10 ** 5 + 10

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

for i, (w, v) in enumerate(WV):
	for n in range(V):
		if v <= n:
			dp[i + 1][n] = min(dp[i + 1][n], dp[i][n - v] + w)
		dp[i + 1][n] = min(dp[i + 1][n], dp[i][n])
"""
for line in dp:
	for cell in line:
		if cell == INF:
			print("  INF", end="")
		else:
			print("{:5d}".format(cell), end="")
	print()
"""
r = 0
for i in range(V):
	if dp[-1][i] <= W:
		r = i
print(r)

Submission status: Accepted

Solution code:
import fileinput


def knapsack(capacity, item_weights, item_values):
    val_limit = sum(item_values) + 1

    prev_vals = [sum(item_weights)] * val_limit
    weight_table = [prev_vals]

    for item_id, item_value in enumerate(item_values):
        current_vals = [0] * val_limit
        for total_val in range(1, val_limit):
            if item_value >= val_limit - total_val:
                current_vals[total_val] = prev_vals[total_val]
            else:
                current_vals[total_val] = min(
                    prev_vals[total_val],
                    prev_vals[total_val + item_value] - item_weights[item_id]
                )

        prev_vals = current_vals
        weight_table.append(prev_vals)

    for val in range(0, val_limit)[::-1]:
        for item in range(1, len(item_weights) + 1):
            if weight_table[item][val] <= capacity:
                return val
    return 0


inp = fileinput.input()

first_line_split = inp.readline().split(" ")

item_count = int(first_line_split[0])
capacity = int(first_line_split[1])

item_weights = []
item_values = []
for _ in range(item_count):
    split = inp.readline().split(" ")
    item_weights.append(int(split[0]))
    item_values.append(int(split[1]))

print(knapsack(capacity, item_weights, item_values))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n, max_w = map(int, input().split())

w = []
v = []
for i in range(n):
    _w, _v = map(int, input().split())
    w.append(_w)
    v.append(_v)

total_v = sum(v)


INF = float('inf')
dp = [[INF] * (total_v + 1) for i in range(n + 1)]
dp[0][0] = 0

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

for j in range(total_v, -1, -1):
    if dp[n][j] <= max_w:
        ans = j
        break

print(ans)

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
w=[]
v=[]
for i in range(N):
    w_,v_=map(int,input().split())
    w.append(w_)
    v.append(v_)
INF=10**9+1
dp=[[INF]*(10**5+1) for i in range(N+1)]#dp[i+1][j] i個目までで価値jのときの最小の価値
#dp[i+1][v]:=min(dp[i][v-vi]+wi,dp[i][v])加えるか加えないか
dp[0][0]=0
for i in range(N):
    for j in range(10**5+1):
        if j-v[i]>=0:
            dp[i+1][j]=min(dp[i][j-v[i]]+w[i],dp[i+1][j])
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])
for j in range(10**5,-1,-1):
    if dp[N][j]<=W:
        ans=j
        break
print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]
dp = [10**12]*(1+10**5)
dp[0] = 0
for i in range(N):
    w,v = WV[i]
    for j in range(len(dp)-1, 0, -1):
        if j-v<=0:
            tmp = w
        else:
            tmp = dp[j-v] + w
        dp[j] = min(dp[j], tmp)
ans = 0
for v,w in enumerate(dp):
    if w<=W:
        ans = max(ans, v)
    else:
        break
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

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

inf = 10**14

dp = defaultdict(lambda : inf)
dp[0] = 0

for _ in range(N):
    w, v = map(int, input().split())
    for dv, dw in dp.copy().items():
        if w + dw <= W:
            dp[dv + v] = min(dp[dv + v], w + dw)
print(max(dp.keys()))

Submission status: Accepted

Solution code:
import numpy as np

N = W = 0
g = []
MAX_V = 100100


def get_input():
    global N, W, g
    N, W = map(int, input().split())
    g = []
    for _ in range(N):
        g.append([int(x) for x in input().split()])


def dpcalc():
    global N, W, g
    # 動的計画法のテーブルを初期化
    dp = np.full((N + 1, MAX_V + 1), 10 ** 11)
    # dp = [[10 ** 11] * (MAX_V + 1) for _ in range(N + 1)]

    # テーブルをiの小さい方から順に計算してゆく
    r = 1
    for i in range(1, N + 1):
        w, v = g[i - 1]
        dp[i][:v + 1] = np.minimum(dp[i - 1][:v + 1], w)
        dp[i][v + 1:v + r] = np.minimum(dp[i - 1][1: r] + w, dp[i - 1][v + 1:v + r] )
        
        r += v
        
    for i in range(MAX_V, -1, -1):
        if dp[N][i] <= W:
            return i
    return 0


get_input()
print(dpcalc())

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n,W = [int(i) for i in input().split()]
wv = [[int(i) for i in input().split()] for j in range(n)] # 縦「n」行
V=10**5
MAX=10**12
dp = [MAX]*(V+1)
dp[0]=0
newdp = [MAX]*(V+1)
for i in range(n):
    w, v = wv[i]
    newdp = dp[:]
    for j in range(V+1):
        if j+v <= V:
            newdp[j+v] = min(dp[j] + w, newdp[j+v])
    newdp, dp = dp, newdp
#    print(dp)

print(max([i for i,c in enumerate(dp) if c <= W]))


#print(dp)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n,W = [int(i) for i in input().split()]
wv = [[int(i) for i in input().split()] for j in range(n)] # 縦「n」行
V=10**5
MAX=10**12
dp = [MAX]*(V+1)
dp[0]=0
newdp = [MAX]*(V+1)
for i in range(n):
    w, v = wv[i]
    for j in range(V+1):
        newdp[j] = dp[j]
    for j in range(V+1):
        if j+v <= V:
            newdp[j+v] = min(dp[j] + w, newdp[j+v])
    newdp, dp = dp, newdp
#    print(dp)

print(max([i for i,c in enumerate(dp) if c <= W]))


#print(dp)

Submission status: Accepted

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

Vmax=sum(V)

# dp[i][v]=i番目の品物までだけを選び価値の合計をvとしたときの必要な重量の最小値
# ただしそのような価値の合計が実現不可能なときはNoneを格納

dp = []
for _ in range(N):
	dp.append([None]*(Vmax+1))

dp[0][0] = 0
dp[0][V[0]] = W[0]

for i in range(1,N):
	# 新しく積めるようになる荷物の価値をV[i]とする
	# このとき価値の合計をvにするのに必要な重量の最小値は
	#	  dp[i-1][v-V[i]]+W[i] と
	#   dp[i-1][v] のうち小さいほう
	for v in range(Vmax+1):
		if v-V[i]<0:
			dp[i][v] = dp[i-1][v]
		else:
			if dp[i-1][v] is not None:
				if dp[i-1][v-V[i]] is not None:
					dp[i][v] = min(dp[i-1][v],dp[i-1][v-V[i]]+W[i])
				else:
					dp[i][v] = dp[i-1][v]
			else:
				if dp[i-1][v-V[i]] is not None:
					dp[i][v] = dp[i-1][v-V[i]]+W[i]

ans = 0
for v in range(Vmax+1):
	try:
		ans = v if dp[-1][v]<=Wmax else ans
	except TypeError:
		pass

print(ans)

Submission status: Accepted

Solution code:
def e():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(N)]
    v = [wv[i][1] for i in range(len(wv))]
    V = sum(v)
    dp = [[10 ** 9] * (V + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(V + 1):
            if j - wv[i][1] >= 0:
                dp[i + 1][j] = min(dp[i + 1][j],
                                   dp[i][j - wv[i][1]] + wv[i][0])
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
    for k, p in enumerate(dp[-1]):
        if p <= W:
            r = k
    return r


if __name__ == '__main__':
    ans = e()
    print(ans)

Submission status: Accepted

Solution code:
def sub():
    N, W = [int(e) for e in input().split()]
    ww = []
    vv = []
    for _ in range(N):
        w, v = [int(e) for e in input().split()]
        ww.append(w)
        vv.append(v)
    
    V = sum(vv)
    INF = 10**12
    dp_table = [[INF for _ in range(V+1)] for _ in range(N+1)]
    dp_table[0][0] = 0
    for i in range(N):
        for j in range(V):
            v_next = vv[i] + j
            w_next = ww[i]
            d = dp_table[i][j]
            if v_next <= V:
                dp_table[i+1][v_next] = min(dp_table[i+1][v_next], d + w_next)
            dp_table[i+1][j] = min(dp_table[i+1][j], d)
    
    # for r in dp_table:
    #     print(r)
    idxx = [i for i, w in enumerate(dp_table[-1]) if w <= W]
    print(idxx[-1])
sub()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def mi(): return map(int, input().split())


def li(): return list(mi())


def li_(): return [int(x) - 1 for x in input().split()]


def lin(n: int): return [input() for _ in range(n)]


def llin(n: int): return [li() for _ in range(n)]


def llin_(n: int): return [li_() for _ in range(n)]


def lli(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def f(): return float(input())


def s(): return input().replace('\n', '')


def main():
    N, W = mi()
    WV = llin(N)
    max_val = 0
    for i in range(N):
        max_val += WV[i][1]
    max_val += 1
    # dp[i][j]:=i番目の品で、価値がj以上になるように選んだときの最小重量
    dp = [[inf] * max_val for i in range(N)]
    for v in range(max_val):
        if v <= WV[0][1]:
            dp[0][v] = WV[0][0]
        else:
            break
    for i in range(1, N):
        for v in range(max_val):
            if v >= WV[i][1]:
                # print(dp[i - 1][v], dp[i - 1]
                #               [v - WV[i][1]] + WV[i][0])
                dp[i][v] = min(dp[i - 1][v], dp[i - 1]
                               [v - WV[i][1]] + WV[i][0])
            else:
                dp[i][v] = dp[i - 1][v]
            if v <= WV[i][1]:
                dp[i][v] = min(dp[i][v], WV[i][0])

    for v in reversed(range(max_val)):
        if dp[N-1][v] <= W:
            print(v)
            exit()


if __name__ == '__main__':
    main()

Submission status: Accepted

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

inf = float('inf')
dp = [[inf] * (V + 1) for i in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V + 1):
        if v[i] > j:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i])
            
ans = 0
for i in range(V + 1):
    if dp[N][i] <= W:
        ans = i
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

MAX_V = 10**5
INF = 10**10
N, W = list(map(int, input().split()))
# dp[i][v]はi番目までの品物を使った際に合計価値がvを超える最小のコストw
dp = [[INF for _ in range(MAX_V+1)] for _ in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    w, v = list(map(int, input().split()))
    for over_v in range(MAX_V+1):
        if over_v - v < 0:
            dp[i][over_v] = dp[i-1][over_v]
            continue
        dp[i][over_v] = min(dp[i-1][over_v-v] + w, dp[i-1][over_v])

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

Submission status: Accepted

Solution code:
import numpy as np

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

w = np.zeros(N+1, dtype = int)
v = np.zeros(N+1, dtype = int)

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

max_v = v.sum()

dp = np.ones((N+1, max_v + 1), dtype =int) * 10**9
dp[0,0] = 0

for i in range(1, N+1):
    dp[i, :v[i]] = dp[i-1, :v[i]]
    dp[i, v[i]:] = np.minimum( dp[i-1, v[i]:], dp[i-1, :max_v+1-v[i]] + w[i] )
#    print(dp[i, :])

ans = 0
for i, j in enumerate(dp[N,:]):
    if j <= W:
        ans = i

print(ans)

Submission status: Accepted

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

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


dp = [[float('inf')] * (100001) for i in range(N)]


for i in range(N):
    for j in range(100001):
        if j == 0:
            dp[i][j] = 0

for i in range(N):
    for sum_v in range(0,100001):
        if sum_v - cost[i][1] >= 0:
            dp[i][sum_v] = min(dp[i-1][sum_v], dp[i-1][sum_v - cost[i][1]] + cost[i][0])
        dp[i][sum_v] = min(dp[i][sum_v], dp[i-1][sum_v])

ans = float('inf')

for j in range(0,100001):
    if dp[N-1][j] <= W:
        ans = j
print(ans)

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
w_list=[0]
v_list=[0]
for i in range(n):
    w,v=map(int,input().split())
    w_list.append(w)
    v_list.append(v)
dp=[]
for i in range(n+1):
    sub_list=[]
    for j in range(100001):
        sub_list.append(0)
    dp.append(sub_list)
for j in range(100001):
    if j==0:
        dp[0][0]=0
    else:
        dp[0][j]=10**10
for i in range(1,n+1):
    for j in range(100001):
        if v_list[i]<=j:
            dp[i][j]=min(dp[i-1][j],dp[i-1][j-v_list[i]]+w_list[i])
        else:
            dp[i][j]=min(dp[i-1][j],dp[i-1][0]+w_list[i])
Max=0
for j in range(100001):
    if dp[n][j]<=W:
        if Max<=j:
            Max=j
print(Max)

Submission status: Accepted

Solution code:
inf = 10 ** 9 + 1
n, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
dp = {0: 0}
for w, v in wv:
    ndp = dp.copy()
    for dv, dw in dp.items():
        nw = w + dw
        if nw > W: continue
        nv = v + dv
        ndp.setdefault(nv, inf)
        if nw < ndp[nv]:
            ndp[nv] = nw
    dp = ndp
print(max(dp.keys()))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import numpy as np

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

dp = np.ones(N * int(1e4)) * int(1e10)
dp[0] = 0
for i in range(N):
    w, v = map(int, input().rstrip().split(' '))
    dp[v:] = np.min(np.vstack([dp[v:], dp[:-v] + w]), axis=0)
    
    
print(1 + np.where(dp[1:] <= W)[0][-1])

Submission status: Accepted

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

for w, v in wv:
    for i in range(maxV, -1, -1):
        dp[i] = min(dp[i], dp[i-v] + w)

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