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

    n,m = map(int,input().split())
    dp = [[float("inf")]*(10**5+1) for i in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        w,v = map(int,input().split())
        for j in range(10**5+1):
            if j-v >= 0:
                dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)
            else:
                dp[i+1][j] = dp[i][j]
    ans = 0

    for i in range(10**5+1):
        if dp[n][i] <= m:
            
            ans = i
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

dp = [[float("inf")]*(10**5+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(1,n+1):
    weight,value = map(int,input().split())
    for j in range(10**5+1):
        if j < value:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-value]+weight)


ans = 0

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

Submission status: Accepted

Solution code:
#制約が違うので価値をfor文にもっていく

n,w=map(int,input().split())
v=n*10**3
dp=[[100000000000] * (v+1) for i in range(n+1)]
#初期条件
dp[0][0]=0

W=[]
V=[]
for i in range(n):
    a,b=map(int,input().split())
    W+=[a]
    V+=[b]

#print(dp[0][0])
#print(W)
for i in range(n):
    #print(i)
    for sum_v in range(v+1):
        #print(sum_v)
        #重さが最小となるケース
        if sum_v>=V[i]:
            dp[i+1][sum_v]=min(dp[i][sum_v],dp[i][sum_v - V[i]] + W[i])
    
        #選ばない時
        else:
            dp[i+1][sum_v]=dp[i][sum_v]

#最適地の抽出
result=0
for i in range(v+1):
    if dp[n][i]<=w:
        result=i
#print(dp[n][:100])
print(result)

Submission status: Accepted

Solution code:
N, W = list(map(int, input().split()))
WE = []
V = []
INF = float('inf')
for i in range(N):
    w, v = list(map(int, input().split()))
    WE.append(w)
    V.append(v)

MAX_V = (10 ** 3) * 100 + 1

# DP[i+1][j]: i番目までの品物から価値の総和がjとなるように選んだときの、重さの総和の最小値
DP = []
for i in range(N+1):
    a = [INF] * (MAX_V + 1)
    DP.append(a)

DP[0][0] = 0

for i in range(N):
    for j in range(MAX_V):
        if j < V[i]:  # 作りたい価値の総和よりも、価値が大きい
            DP[i+1][j] = DP[i][j]
        else:
            DP[i+1][j] = min(DP[i][j], DP[i][j-V[i]] + WE[i])

r = 0
for i in range(MAX_V+1):
    if DP[N][i] <= W:
        r = i

print(r)

# for i in range(N+1):
    # print(DP[i][:20])

Submission status: Accepted

Solution code:
import numpy as np
N, Limit = map(int, input().split())

dp = np.zeros(10 ** 5 + 1) + 10 ** 10
dp[0] = 0

for _ in range(N):
    w, v = map(int, input().split())
    np.minimum(dp[v:], dp[:-v] + w, out=dp[v:])

dp_meet_index = [i for i, v in enumerate(dp) if v <= Limit]

print(dp_meet_index[-1])

Submission status: Accepted

Solution code:
import bisect
N, W = map(int, input().split())
min_w = []
for i in range(N):
  w, v = map(int, input().split())
  l = [w] * v + [i + w for i in min_w]
  min_w = [min(min_w[i], l[i]) for i in range(len(min_w))] + l[len(min_w):]
#  print(min_w, len(min_w))
print(bisect.bisect_right(min_w, W))

Submission status: Accepted

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

sv = sum(v)
dp = [[float("inf")]*(sv+1) for _ in range(n+1)]
dp[0][0] = 0

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

ans = 0
for i, v in enumerate(dp[n]):
    if v <= W:
        ans = i
print(ans)

Submission status: Accepted

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

V = sum([v for _, v in data])
dp = [[float("inf")] * (V + 1) for i in range(n + 1)]
dp[0][0]= 0

for i in range(1, n+1):
    w, v = data[i-1]
    for j in range(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]

print(max([i for i, x in enumerate(dp[-1]) if x != "inf" and x <= W]))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

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

n, W = na()
vmax = 10**5
inf = 10**11
dp = [[inf] * (vmax+1) for _ in range(n)]
#dp[ni][vi] viを超える最小のweight
w, v = na()
for i in range(0, v+1):
    dp[0][i] = w
for i in range(1, n):
    w, v = na()
    for j in range(v+1):
        dp[i][j] = min(dp[i-1][j], w) #選ぶor選ばない
    for j in range(v+1, vmax+1):
        dp[i][j] = min(dp[i-1][j], dp[i-1][j-v] + w) #選ぶor選ばない
#print(dp[n-1][:20])
ans = 0
for i, w in enumerate(dp[n-1]):
    if w <= W:
        ans = max(ans, i)
print(ans)

Submission status: Accepted

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

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


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

    for i in range(N):
        w, v = item[i]
        np.minimum(dp[v:], dp[:-v] + w, out=dp[v:])

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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


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

    for i in range(N):
        w, v = item[i]
        np.minimum(dp[v:], dp[:-v] + w, out=dp[v:])

    print(np.max(np.where(dp <= W)))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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


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

    for i in range(N):
        w, v = item[i]
        np.minimum(dp[v:], dp[:-v] + w, out=dp[v:])

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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


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

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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


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

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

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

Submission status: Accepted

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

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

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

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

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

print(res)

Submission status: Accepted

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

INF = 10**9+1000
SUM_V = sum([A[1] for A in WV])
dp = [[INF]*(SUM_V+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N+1):
    dp[i][0] = 0

for n in range(0, N):
    for v in range(0, SUM_V+1):
        if v >= WV[n][1]:
            dp[n+1][v] = min(dp[n][v-WV[n][1]] + WV[n][0], dp[n][v])
        else:
            dp[n+1][v] = dp[n][v]

for n in range(0, N+1):
    for v in range(0, SUM_V+1):
        if dp[n][v] <= W:
            dp[n][v] = -1

print(max([max([i for i,v in enumerate(dd) if v == -1]) for dd in dp]))

Submission status: Accepted

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

sv = sum(v)
dp = [[float("inf")]*(sv+1) for _ in range(n+1)]
dp[0][0] = 0

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

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

print(ans)

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[i][j]:i番目までの品物から価値がj以上になるよう選んだときの重さの総和の最小値
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):
		# 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])

# 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:
import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = sys.stdin.readline

def main():
    n, w = map(int, input().split())
    WVs = [list(map(int, input().split())) for i in range(n)]
    Vs = [_[1] for _ in WVs]
    sum_v = sum(Vs)
    
    dp = [[10**11]*(sum_v+1) for i in range(n+1)]
    dp[0][0] = 0
    
    # dp[i+1][j] := i個目までの商品を見たときに，価値の総和がjを超えるように選んだたときの重さの最小値

    for i in range(n):
        for j in range(sum_v+1):
            vi = Vs[i]
            wi = WVs[i][0]
            

            if j-vi >= 0:
                dp[i+1][j] = min([dp[i][j-vi] + wi, dp[i][j]])
            else:
                dp[i+1][j] = dp[i][j]

    
    # print(dp[n])
    for k in reversed(range(sum_v+1)):
        # print(k)
        if dp[n][k] <= w:
            
            print(k)
            exit()

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# atcoderのテスト用
# ./iunput/input.txt に入力を書き込む
n, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
w = [wv[i][0] for i in range(n)]
v = [wv[i][1] for i in range(n)]
inf = float('inf')
V = max(v)
vmax = 10**5+1
# dp[i][sum_v] 
# := i-1番目までの品物で価値がsum_vを超えないように選んだときの重さの総和の最小値
# 価値の合計はどれくらい大きくなるかわからないので十分に用意しとく
dp = [[inf for _ in range(vmax)] for _ in range(n+1)]
# 初期条件
dp[0][0] = 0
for i in range(n):
    for sum_v in range(vmax):
        # 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 sum_v in range(vmax):
    if dp[n][sum_v] <= W:
        ans = sum_v
print(ans)

Submission status: Accepted

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

n,W=map(int,input().split())
items=[list(map(int,input().split())) for i in range(n)]
weight=[items[i][0] for i in range(n)]
value=[items[i][1] for i in range(n)]
import numpy as np

limit=sum(value)
inf=10**9
dp=np.array([[0]+[inf]*limit for i in range(n+1)])
#print(dp)
for i in range(n):
  w=weight[i]
  v=value[i]
  dp[i+1][:v]=dp[i][:v]
  dp[i+1][v:]=np.minimum(dp[i][v:],dp[i][:-v]+w)

ans=max([i for i in range(limit+1) if dp[n][i]<=W])
print(ans)

Submission status: Accepted

Solution code:
import sys


def solve():
    readline = sys.stdin.readline
    N, W = map(int, readline().split())
    WV = (map(int, readline().split()) for _ in range(N))
    INF = 10 ** 15
    MAX_V = 100 * 10**3 + 1
    dp = [INF] * MAX_V
    dp[0] = 0
    for w, v in WV:
        for i in range(MAX_V-1, v-1, -1):
            tmp_dp = dp[i-v] + w
            if dp[i] > tmp_dp:
                dp[i] = tmp_dp
    for v, w in enumerate(dp):
        if w <= W:
            ans = v
    return ans


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

Submission status: Accepted

Solution code:
import sys


def solve():
    readline = sys.stdin.readline
    N, W = map(int, readline().split())
    WV = (map(int, readline().split()) for _ in range(N))
    INF = 10 ** 15
    MAX_V = 100 * 10**3 + 10
    dp = [INF] * MAX_V
    dp[0] = 0
    for w, v in WV:
        for i in range(MAX_V-1, v-1, -1):
            tmp_dp = dp[i-v] + w
            if dp[i] > tmp_dp:
                dp[i] = tmp_dp
    for v, w in enumerate(dp):
        if w <= W:
            ans = v
    return ans


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

Submission status: Accepted

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

dp=[float('inf')]*100001 # dpリストを作る。
# dp[i]は、価値の総和がiになる時の質量の総和の最小。
dp[0]=0

for i in range(N): # １つ１つの商品について
    for j in range(100000,list1[i][1]-1,-1):
        dp[j]=min(dp[j],dp[j-list1[i][1]]+list1[i][0])

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

Submission status: Accepted

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

V_sum=sum(v)+1
dp=[[float('inf')]*(V_sum) for i in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
    for sum_v in range(V_sum):
        #同価値の場合より軽いほうを入れる
        if sum_v-v[i-1]>=0:
            dp[i][sum_v]=min(dp[i][sum_v],dp[i-1][sum_v-v[i-1]]+w[i-1])

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

ans=0
for i in range(V_sum):
    if dp[-1][i]<=W and ans<i:
        ans=i
print(ans)

Submission status: Accepted

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

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

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)]
dp[0][0] = 0
for i in range(N):
    for value in range(V+1):
        if 0 <= value - v[i]:
            dp[i+1][value] = min(dp[i][value-v[i]]+w[i],dp[i][value])
        else:
            dp[i+1][value] = dp[i][value]
ans = 0
for i in range(V+1):
    if dp[N][i] <= W:
        ans = i
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

U = 10**5
n, W = map(int, input().split())
dp = np.full(U+1, float("inf"))
dp[0] = 0
for _ in range(n):
  w, v = map(int, input().split())
  np.minimum(dp[v:], dp[:-v]+w, out=dp[v:])
ans = np.where(dp <= W)[0][-1]
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N, W = map(int, input().split())
goods = [tuple(map(int, input().split())) for _ in range(N)]
Mv = 10 ** 5
Mw = 10 ** 11

table = np.full((N + 1, Mv + 1), Mw, dtype=np.int64)
table[0][0] = 0
for n in range(N):
    tmp = np.full(Mv + 1, Mw, dtype=np.int64)
    tmp[goods[n][1]:] = table[n][:Mv + 1 - goods[n][1]] + goods[n][0]
    table[n + 1] = np.minimum(table[n], tmp)

print(np.max(np.where(table[N] <= W, table[N], 0).nonzero()))

Submission status: Accepted

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

wv = [[int(x) for x in input().split()] for _ in range(N)]

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

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

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

Submission status: Accepted

Solution code:
from pprint import pprint
n, w = map(int, input().split())
s = [list(map(int, input().split())) for i in range(n)]
ws = [x[0] for x in s]
vs = [x[1] for x in s]
max_v = sum(vs)
INF = float("inf")
dp = [[INF]*(max_v+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(1, n+1):
    for sum_v in range(max_v+1):
        if vs[i-1] <= sum_v:
            dp[i][sum_v] = min(dp[i-1][sum_v], dp[i-1][sum_v-vs[i-1]]+ws[i-1])
        else:
            dp[i][sum_v] = dp[i-1][sum_v]
ans = 0
for sum_v in range(max_v+1):
    if dp[n][sum_v] <= w:
        ans = sum_v
print(ans)

Submission status: Accepted

Solution code:
n, w_bag = map(int, input().split())
wv = [[int(x) for x in input().split()] for _ in range(n)]
v_sum = sum(x[1] for x in wv)
min_weight = [[0 for _ in range(n + 1)] for _ in range(v_sum + 1)] # min_weight[v][i] = not less valuable than v picked out from the former i

for v in range(1, v_sum + 1):
    min_weight[v][0] = w_bag + 1
    for i in range(1, n + 1):
        if v - wv[i - 1][1] >= 0:
            min_weight[v][i] = min(min_weight[v][i - 1],
                                   min_weight[v - wv[i - 1][1]][i - 1] + wv[i - 1][0])
        else:
            min_weight[v][i] = min_weight[v][i - 1]

endflag = False
for enum, m_w_v in enumerate(reversed(min_weight)):
    for m_w_v_i in m_w_v:
        if m_w_v_i <= w_bag:
            print(v_sum - enum)
            endflag = True
            break
    if endflag:
        break
if not endflag:
    print(0)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,W=map(int,input().split())
    w,v=[0]*N,[0]*N
    for i in range(N):
        w[i],v[i]=map(int,input().split())
    dp=[[INF]*(10**5+1) for _ in range(N+1)]
    dp[0][0]=0
    ans=0
    for i in range(N):
        for value in range(10**5+1):
            dp[i+1][value]=min(dp[i+1][value],dp[i][value])
            if value>=v[i]:
                dp[i+1][value]=min(dp[i+1][value],dp[i][value-v[i]]+w[i])
            if dp[i+1][value]<=W:
                ans=max(ans,value)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = int(1e09) + 7
INF = int(1e15)

V_MAX = int(1e05)+1


def main():
    # sys.stdin = open("sample.txt")
    N, W = Scanner.map_int()
    V = [Scanner.map_int() for i in range(N)]
    dp = [[INF for _ in range(V_MAX)] for _ in range(N+1)]
    dp[0][0] = 0

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


if __name__ == "__main__":
    main()

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[i][j]...i番目までの品物で価値j以上を達成するのに必要な重さの最小値(達成できないときはinf)
dp = [[float("inf")]*(V+1) for _ in range(N+1)]

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

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

print(ans)

Submission status: Accepted

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

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

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

    for i in range(n):
        for sum_v in range(lim):
            if sum_v-l[i][1]>=0:
                dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - l[i][1]] + l[i][0])
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])

    ans = 0
    for sum_v in range(lim):
        if dp[n][sum_v] <= w:
            ans = sum_v

    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

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

#dp[0][0]=0

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

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

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

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

Submission status: Accepted

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

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

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

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

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

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

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

Submission status: Accepted

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

wv = []
for i in range(N):
    wv.append(list(map(int, input().split())))
    
dp = [[10**15 for i in range(10**5+1)] for j in range(N+1)]
dp[0][0] = 0

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

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

print(ans)

Submission status: Accepted

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)
BIG = 10**15+1
LEN = 10**3
LEN = LEN*N
dp = [[BIG for i in range(LEN+1)]for j in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0

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

ans = 0
for j in range(LEN+1):
    if dp[N][j] <= W and j >= ans:
        ans = j

        
print(ans)
# print(dp)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

inf = float("inf")
dp = [[inf]*(v_max+1) for i in range(N)]
dp[0][v[0]] = w[0]
for i in range(N):
	dp[i][0] = 0

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

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

print(ans)

Submission status: Accepted

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

v = sum([vi for _, vi in x])
dp = [[2 * 10 ** 9 for j in range(v + 1)] for i in range(2)]
dp[0][0] = 0
dp[1][0] = 0

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

Submission status: Accepted

Solution code:
import numpy as np
N,W = map(int,input().split())

dp = np.full(N*10**3+1, W+1, dtype = np.int64)
dp[0] = 0

for i in range(N):
    w,v = map(int,input().split())
    np.minimum(dp[:-v]+w, dp[v:], out = dp[v:])

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

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

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

print(ans)

Submission status: Accepted

Solution code:
N, W = map(int,input().split())
ws = []
vs = []
for _ in range(N):
   w,v = map(int,input().split())
   ws.append(w)
   vs.append(v)
# i番目の重みws[i], 価値vs[i]
def solve(N, W, ws, vs):
    # V = 全ての品物の価値の総和
    V = sum(vs)

    # 初期値は価値0以外の重さを上限より大きく
    dp = [W+1] * (V + 1)
    dp[0] = 0
    for i in range(N):
        # 価値v, 重さw
        v = vs[i]; w = ws[i]
        for j in range(V, v-1, -1):
            dp[j] = min(dp[j-v] + w, dp[j])

    # 重さが上限以下の価値のうち、最大の価値が解
    return max(i for i in range(V+1) if dp[i] <= W)

print(solve(N,W,ws,vs))

Submission status: Accepted

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

dp = [[10**12]*(sum(value)+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(sum(value)+1 - value[i]):
        # 価値jの時の重みを最小化していく
        # i番目のitemを使わない時
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])

        # i番目のitemを使うとき
        dp[i+1][j+value[i]] = min(dp[i+1][j+value[i]], dp[i][j]+weight[i])

# 重みがW以下で最大の価値を求める
ans = 0
for i in range(sum(value)+1):
    if dp[N][i] <= W:
        ans = i
print(ans)

Submission status: Accepted

Solution code:
#PyPy必須？
n,w=map(int,input().split())
v=10**5
WV=[list(map(int,input().split())) for i in range(n)]
#dp[i][v] 価値vでの最低体重
dp=[[10**10]*(v+1) for i in range(n+1)]
for i in range(n):
    dp[i][0]=0
for i in range(n):
    for j in range(v+1):
        if j-WV[i][1]>=0 and j-WV[i][1]<=v:
            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]
for j in range(v, -1, -1):
    if dp[n][j]<=w:
        print(j)
        break

Submission status: Accepted

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

for i in range(N):
    x,y=map(int,input().split())
    w.append(x)
    v.append(y)

S=sum(v)

DP=[1000000000000]*(S+1)
DP[0]=0


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

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

Submission status: Accepted

Solution code:
[n,w] = [int(i) for i in input().split()]
w_v = []
for i in range(n):
    w_v.append([int(j) for j in input().split()])

"""
dp[i][v] = w
i : 何番目までのものを使うか
v : ちょうどその価値になる
w : その時の重さ
最後に後ろから全探索して重さ超えてないやつ探す？
"""
INF = 10 ** 9 + 7
v_max = 10**3 * n + 1
dp = [[INF] * (v_max) for i in range(n)]
##print(dp)
#価値0になるところの重さは0
for i in range(n):
    dp[i][0] = 0
if n != 1:
    for i in range(n):
        #print("step",i)
        if i != 0:
            for v_zantei in range(v_max):
                if v_zantei >= w_v[i][1]:
                    dp[i][v_zantei] = min(dp[i-1][v_zantei],dp[i-1][v_zantei - w_v[i][1]] + w_v[i][0])
                else:
                    dp[i][v_zantei] = dp[i-1][v_zantei]
            #print(dp[i])
        else:
            dp[i][w_v[i][1]] = w_v[i][0]
            #print(dp[i])
    ans = -1
    for v in range(v_max-1,-1,-1):
        #print(w,dp[n-1][v],ans)
        if dp[n-1][v] <= w and ans < v:
            ##print(v)
            ans = v
    print(ans)
else:
    print(w_v[0][1])