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:
#from collections import deque
from pprint import pprint

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

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

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

dp[0][0] = 0

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    N, W = map(int, input().rstrip().split())
    item_list = []
    for _ in range(N):
        w, v = map(int, input().rstrip().split())
        item_list.append((w, v))

    # dp[i][v] = i番目まで見て価値vを達成できる最小の重さ
    dp = [[float("inf")] * (100001) for _ in range(N+1)]
    dp[0][0] = 0

    max_value = 0
    for i, item in enumerate(item_list, 1):
        for v in range(100001):
            # もし品物iが入れられる
            if dp[i-1][v] + item[0] <= W:
                dp[i][v+item[1]] = min(dp[i][v+item[1]], dp[i-1][v]+item[0])
                max_value = max(max_value, v+item[1])
            # 入れないパターン
            dp[i][v] = min(dp[i][v], dp[i-1][v])
    print(max_value)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin, stdout


def solve(mw, iw, iv):
    vs = sum(iv)
    A = [[float('inf') for i in range(vs+1)] for i in range(len(iv) + 1)]        
    A[0][0] = 0
    rs = 0
    for i in range(1, len(iv) + 1):
        rs += iv[i-1]
        for j in range(vs + 1):
            if i > rs: break
            if j < iv[i-1]: A[i][j] = A[i-1][j]
            else: A[i][j] = min(A[i-1][j], A[i-1][j-iv[i-1]] + iw[i-1])
    ans = 0
    for i in range(len(A[0])-1, -1, -1):
        if A[-1][i] != float('inf') and A[-1][i] <= mw:
            return i

# def test():
#     f = open('a.txt', 'r')
#     t = int(f.readline())
#     count, error = 1, 0
#     for _ in range(t):
#         try:
#             n, mw = f.readline().split()
#             iw, iv = [], []
#             for _ in range(int(n)):
#                 w, v = f.readline().split()
#                 iw.append(int(w))
#                 iv.append(int(v))
#             ans = int(f.readline())
#             output = solve(int(mw), iw, iv)
#             if ans != output:
#                 error += 1 
#                 stdout.write(f"Case #:{count} (WA) | Ans: {ans} Output: {output}\n")
#             else:
#                 stdout.write(f"Case #:{count} Pass\n")
#         except RuntimeError:
#             error += 1
#             stdout.write(f"Case #{count} (RE)")
#         count += 1
#     if error == 0: stdout.write("All test cases passed")
#     else: stdout.write(f"Passed: {count-error-1} | Errors: {error}")

def main():
    iw, iv = [], []
    n, mw = [int(i) for i in stdin.readline().split()]
    for _ in range(n):
        w,v = [int(i) for i in stdin.readline().split()]
        iw.append(w)
        iv.append(v)
    print(solve(mw, iw, iv))

main()
# test()

Submission status: Accepted

Solution code:
INF = 1000000000000
n, W = map(int, input().split())
values = []
weights = []
total = 10
for _ in range(n):
    w, v = map(int, input().split())
    weights.append(w)
    values.append(v)
    total += v
dp = [[INF for j in range(total)] for i in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0
for i in range(1,n+1):
    for v in range(1,total):
        if v < values[i-1]:
            dp[i][v] = dp[i-1][v]
        else:
            dp[i][v] = min(dp[i-1][v],dp[i-1][v-values[i-1]]+weights[i-1]) 
res = 0
for i in range(total):
    if dp[n][i] <= W:
        res = i
print(res)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from collections import deque
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,W=mp()
dp=[[10**10]*(n*1000+1) for i in range(n+1)]
for i in range(n+1):
    dp[i][0]=0
for i in range(1,n+1):
    w,v=mp()
    for k in range(n*1000+1):
        dp[i][k]=dp[i-1][k]
        if k-v>=0:
            dp[i][k]=min(dp[i-1][k],dp[i-1][k-v]+w)
ans=0
for i in range(n*1000+1):
    if dp[-1][i]<=W:
        ans=i
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N, W = geta(int)
    INF = 10 << 60
    VMAX = 10**5
    cur = [INF] * (VMAX + 1)
    cur[0] = 0

    for i in range(N):
        w, v = geta(int)
        update = cur[:]

        for j in range(v, VMAX + 1):
            if cur[j - v] == INF: continue
            tmp = cur[j - v] + w
            if tmp < cur[j]: update[j] = tmp

        cur = update

    ans = 0
    for v in range(VMAX + 1):
        if cur[v] <= W: ans = v
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
w_list = [0]
v_list = [0]
ans = 0

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

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

for i in range(1, N + 1):
    for j in range(100001):
        if j - v_list[i] >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v_list[i]] + w_list[i])
        else:
            dp[i][j] = dp[i - 1][j]

for i in range(100001):
    if dp[N][i] != INF and dp[N][i] <= W:
        ans = max(ans, i)

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import numpy as np

def main():
    N, W = map(int, input().split())
    V = 10**3 * N + 1 
    
    dp = np.full(V, W+1)
    # print(len(dp))
    dp[0] = 0
    
    for _ in range(N):
        w, v = map(int, input().split())
        dp[v:] = np.minimum(dp[v:], dp[:-v]+w)

    # print(dp)
    print(np.max(np.where(dp<=W)))
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
N, W = map(int, input().split())
 
items = [tuple(map(int, input().split())) for _ in range(N)]
 
dp = np.full(N*1000 +1, W+1) #横軸を価値の値に変換する
dp[0] = 0
 
for i, (w, v) in enumerate(items):
    dp[v:] = np.minimum(dp[v:], dp[:-v]+w)
 
print(np.max(np.where(dp <= W)))

Submission status: Accepted

Solution code:
import numpy as np

if __name__=='__main__':
    N,Max_w = map(int,input().split())
    v,w = [],[]
    for _ in range(N):
        a,b = map(int,input().split())
        w.append(a)
        v.append(b)
    
    sum_v = sum(v)+1
    dp = [10**10 for _ in range(sum_v + 1)]
    dp[0] = 0
    dp = np.array(dp)
    
    for a,b in zip(w,v):
        x = dp[:-b]+a
        y = dp[b:]
        np.minimum(x,y,out=dp[b:])


    ans = np.where( dp <= Max_w )
    print(np.max(ans))

Submission status: Accepted

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

def main():
    n, w_max = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(n)]
    inf = float('inf')
    dp = [[inf] * 100001 for _ in range(n + 1)]
    dp[0][0] = 0
    for i1 in range(1, n + 1):
        w, v = items[i1 - 1][0], items[i1 - 1][1]
        for col in range(1, 100001):
            if v >= col:
                tmp1 = w
            else:
                tmp1 = dp[i1 - 1][col - v] + w
            dp[i1][col] = min(dp[i1 - 1][col], tmp1)
    for i2 in range(100000, 0, -1):
        if dp[-1][i2] <= w_max:
            print(i2)
            sys.exit()

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

dp = np.full(N*1000 +1, W+1) #横軸を価値の値に変換する
dp[0] = 0

for i, (w, v) in enumerate(items):
    dp[v:] = np.minimum(dp[v:], dp[:-v]+w)

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

Submission status: Accepted

Solution code:
import numpy as np

N,W = map(int,input().split())
DP= np.full(N*1000+1,W+1)
DP[0] = 0
for i in range(N):
  w,v = map(int,input().split())
  DP[v:] = np.minimum(DP[v:],DP[:-v]+w)

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

Submission status: Accepted

Solution code:
import numpy as np
# knapsack with N <= 100 and W <= 10**9
n, W = map(int, input().split())
# dp[i][j] = w' means upto i elements j such that you get min weight  w'
# then your solution will be j where w' = W
dp = np.full(fill_value=10**15+1,shape=(n,10**5+1), dtype='int64')
w, v = map(int, input().split())
dp[0,v] = w
dp[0,0] = 0
for i in range(1,n):
    w, v = map(int, input().split())
    dp[i, :v] = dp[i-1, :v]
    dp[i, v:] = np.fmin(dp[i-1, v:], dp[i-1,:-v]+w)
ans = 0
for j in range(100001):
    if dp[n-1][j] <= W:
        ans = max(ans, j)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N , W = map(int,input().split())
dp = np.full(N * 1000 + 1,W + 1)
dp[0] = 0

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

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

Submission status: Accepted

Solution code:
N_W=list(map(int,input().split()))
N=N_W[0]
W=N_W[1]
items=[]
for i in range(N):
	sets=list(map(int,input().split()))
	items.append(sets)
V=0
for i in range(N):
	V=max(V,items[i][1])

f_inf=float('inf')

knapsack=[[f_inf for v in range(N*V+1)] for i in range(N+1)]
knapsack[0][0]=0

for i in range(N):
	for v in range(0,N*V+1):
		if v-items[i][1]>=0:
			knapsack[i+1][v]=min(knapsack[i+1][v],knapsack[i][v],knapsack[i][v-items[i][1]]+items[i][0])
		else:
			knapsack[i+1][v]=min(knapsack[i+1][v],knapsack[i][v])
value=0
for i in range(len(knapsack)):
	for j in range(len(knapsack[0])):
		if knapsack[i][j]<=W:
			value = max(value,j)
print(value)

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
a,b=[0]*n,[0]*n
for i in range(n):a[i],b[i]=map(int,input().split())
mv=sum(b)
dp=[[10**10 if j!=0 else 0 for j in range(mv+1)]for i in range(n+1)]
for i in range(1,n+1):
	for j in range(1,mv+1):
		if j<b[i-1]:dp[i][j]=dp[i-1][j]
		else:dp[i][j]=min(dp[i-1][j],a[i-1]+dp[i-1][j-b[i-1]])
ans=0
for i in range(mv+1):
	if dp[-1][i]<=w:ans=i
print(ans)

Submission status: Accepted

Solution code:
import numpy as np


def main():
    INF = 10**15
    V = 10**5 + 1
    N, W = list(map(int, input().split(' ')))
    items = np.array([list(map(int, input().split(' '))) for _ in range(N)])
    dp = np.full((N, V + 1), INF)
    dp[0, :(items[0, 1] + 1)] = items[0, 0]
    dp[0, 0] = 0
    for n in range(1, N):
        weight, value = items[n, 0], items[n, 1]
        dp[n, :] = dp[n - 1, :]
        dp[n, value:] = np.fmin(
            dp[n, value:],
            weight + dp[n - 1, :(- value)]
        )
    ans = 0
    for v in range(V):
        if dp[N - 1, v] <= W:
            ans = v
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding:utf-8

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

V = sum(v)

inf = 10000000000000
dp = [[inf for x in range(V+1)] for y in range(N+1)]

dp[0][0] = 0

for i in range(1, N+1):
	for j in range(V+1):
		# 品物を選ばない
		dp[i][j] = min(dp[i][j], dp[i-1][j])
		# 品物を選ぶ
		if j - v[i-1] >= 0:
			dp[i][j] = min(dp[i][j], dp[i-1][j-v[i-1]] + w[i-1])

# for i in range(N+1):
# 	for j in range(V+1):
# 		if dp[i][j] == inf:
# 			print(" inf", end="")
# 		else:
# 			print("{0:>4}".format(str(dp[i][j])), end="")
# 	print("")

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

print(max_v)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

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

    # 添字を付け加える系DP．ナップサックとかはこの一種
    # https://qiita.com/drken/items/dc53c683d6de8aeacf5a#%E9%A1%9E%E9%A1%8C-3

    INF = 10**20  # INF+INFを計算してもオーバーフローしない範囲で大きく

    I = N
    # dpテーブル dp[i][j]:=i番目以下で価値j以上の時の，重さの最小値
    J = sum(value)
    dp = [[INF]*(J+1) for _ in range(I+1)]
    # 初期条件
    dp[0][0] = 0
    # ループ
    for i in range(1,I+1):
        for j in range(J+1):
            if j-value[i-1] >= 0:
                dp[i][j] = min(dp[i][j], dp[i-1][j-value[i-1]]+weight[i-1])
            dp[i][j] = min(dp[i][j], dp[i-1][j])
    ans = 0
    for j in range(J+1):
        if dp[I][j] <= W:
            ans = j
    print(ans)

resolve()

Submission status: Accepted

Solution code:
import numpy as np

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

max_v = 10**3*(N+1)
dp = np.full([N+1,max_v], np.inf)
dp[0,0] = 0
 
for i in range(N):
    # 遷移元なし
    dp[i+1,:wv[i,1]] = dp[i,:wv[i,1]]
    # 遷移元あり
    dp[i+1,wv[i,1]:] = np.minimum(dp[i,wv[i,1]:], dp[i,:max_v-wv[i,1]]+wv[i,0])

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

Submission status: Accepted

Solution code:


def main():
    N, W = map(int, input().split())
    weight = [0]
    value = [0]
    for i in range(N):
        w, v = map(int, input().split())
        weight.append(w)
        value.append(v)
    V = sum(value)
    dp = [[float('inf')]*(V+1) for i in range(N+1)]
    for i in range(N):
        dp[i][0] = 0
    
    for i in range(1, N+1):
        for val in range(1, V+1):
            if val >= value[i]:
                dp[i][val] = min(dp[i-1][val], dp[i-1][val-value[i]]+weight[i])
            else:
                dp[i][val] = dp[i-1][val]
    ans = 0
    for v in range(V, -1, -1):
        if dp[N][v] <= W:
            ans = v
            break
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def chmin(dp, i, j, b):
    if dp[i][j] > b:
        dp[i][j] = b
        return True
    return False
def main():
    N, W = map(int, input().split())
    goods = []
    INF = 10 ** 9 + 1
    for _ in range(N):
        goods.append(list(map(int, input().split())))
    dp = [[INF for _ in range(100001)] for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        w, v = goods[i][0], goods[i][1]
        for j in range(100001):
            chmin(dp, i+1, j, dp[i][j])
            if j-v >= 0:chmin(dp, i+1, j, dp[i][j-v]+w)
    ans = 0
    for i in range(100001):
        if dp[N][i] <= W:ans = i
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#dp[i][v] = min dp[i-1][v], dp[i-1][v-vi] + wi
N, W = [int(_n) for _n in input().split()]
weights = []
values = []
for i in range(N):
    w,v = [int(_n) for _n in input().split()]
    weights.append(w)
    values.append(v)
V = max(values) * N+1
INF = 10**12
dp = [[INF]*(V+1) for _ in range(N)]

for v in range(V+1):
    dp[0][v] = INF if v > values[0] else weights[0]
dp[0][0] = 0
for i in range(1,N):
    for v in range(V+1):
        dp[i][v] = min(dp[i-1][v], dp[i-1][max(0,v-values[i])] + weights[i])
ok = 0
ng = V
while ng - ok > 1:
    mid = (ng+ok)//2
    if dp[N-1][mid] > W:
        ng = mid
    else:
        ok = mid
print(ok)

Submission status: Accepted

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

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
# import numpy as np

def IL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

N, W = IL()
v_list = [0] * N
w_list = [0] * N

for i in range(N):
	w_list[i], v_list[i] = IL()

v_max = 100100
dp = [[sys.maxsize] * (v_max+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
	for j in range(v_max+1):
		if j >= v_list[i]:
			dp[i+1][j] = min(dp[i][j-v_list[i]] + w_list[i], dp[i][j])
		else:
			dp[i+1][j] = min(dp[i+1][j], dp[i][j])

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

print(ans)

Submission status: Accepted

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

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

for i in range(N): #i番目の荷物を拾うかどうか
    for j in range(V+1): #価値jを超える重量の最小値
        dp[i+1][j]=min(dp[i][j],dp[i][max(0,j-v[i])]+w[i])
        if dp[i+1][j]<=W:
            ans=max(ans,j)
        
print(ans)

Submission status: Accepted

Solution code:
import sys

input = lambda :sys.stdin.readline().rstrip()

def main():
    N, W = map(int, input().split())
    w, v = [0 for i in range(N)], [0 for i in range(N)]
    for i in range(N):
        w[i],v[i] = map(int, input().split())
    ans = solve(N, W, w, v)
    print(ans)


def solve(N, W, w, v):
    INF = W + 1
    vmax = 10 ** 3 * 10 ** 2
    dp = [[INF for i in range(vmax + 1)] for j in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(vmax + 1):
            dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i])
    for v in range(vmax, -1, -1):
        if dp[N][v] <= W:
            ans = v
            break
    return ans


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

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

    dp[0][0] = 0
    # i種類目までの荷物を見る
    for i in range(N):
        # その荷物を価値がjになるように持つ
        for j in range(V + 1):
            w, v = WV[i]

            if v <= j:
                # 荷物iを選ぶ場合
                dp[i+1][j] = min(dp[i+1][j], dp[i][j-v] + w)
            # 荷物iを選ばない場合
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])

    # print(dp)
    max_ind = 0
    for j in range(V+1):
        if dp[-1][j] <= W:
            max_ind = j
    print(max_ind)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np

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

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

for i, (w, v) in enumerate(items):
  tmp = dp[:-v] + w
  dp[v:] = np.minimum(dp[v:], tmp)
print(np.max(np.where(dp <= W)))

Submission status: Accepted

Solution code:
import numpy as np
n,w,*wv=map(int,open(0).read().split())
wei=wv[0::2]
val=wv[1::2]
sack=np.array([float('inf') for i in range(sum(val)+1)])
sack[0]=0
for i in range(n):
  sack[val[i]:]=np.minimum(sack[val[i]:],sack[:-val[i]]+wei[i])
print(np.where(sack<=w)[0][-1])

Submission status: Accepted

Solution code:
## coding: UTF-8
import sys
#import time

#start = time.time()
N, W = map(int,input().split())
l = [list(map(int, input().split())) for _ in range(N)]


dp = [ [sys.maxsize] * (N * 1000) for _ in range(N) ]
for i in range(N):
    for j in range(N * 1000):
        w = l[i][0]
        v = l[i][1]
        if(j == 0):
            dp[i][j] = 0
        elif(j <= v):
            dp[i][j] = min(dp[i-1][j], w)
        else:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-v] + w)
#for k in range(N):
    #print(dp[k][:20])

#print(dp[-1][2999])
#print(dp[-1][3000])
cnt = 0
i = 0
while cnt <= W:
    cnt = dp[-1][i]
    i += 1
    if(i == N*1000):
        i += 2
        break
print(i-2)#0-index , while分の構造上、iが2多くなる

Submission status: Accepted

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

dp = [[float('inf')] * (10 ** 5 + 5) for _ in range(N + 5)]
dp[0][0] = 0
for i in range(N):
    for j in range(10 ** 5 + 1):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        if 0 <= j - vt[i]:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - vt[i]] + wt[i])
# print(dp)
ans = 0
for i in range(N + 1):
    for j in range(10 ** 5 + 1):
        if dp[i][j] <= W:
            ans = max(ans, j)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N, W = map(int, input().split())
dp = np.full(N*10**3+1, W+1)
dp[0] = 0

for i in range(N):
    w, v = map(int, input().split())
    dp[v:] = np.minimum(dp[v:], dp[:-v]+w)
print(np.where(dp<=W)[0][-1])

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 _ in range(110)]
dp[0][0]=0

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

Submission status: Accepted

Solution code:
import numpy as np
N,W = map(int,input().split())
s=np.full(N*1000+1,W+1)
s[0]=0
for i in range(N):
  w,v =  map(int,input().split())
  s[v:]=np.minimum(s[v:],s[:-v]+w)
print(np.max(np.where(s<=W)))

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
w=[]
v=[]
for _ in range(N):
    ww,vv=map(int,input().split())
    w.append(ww)
    v.append(vv)
INF=float("inf")
max_v=max(v)*N +1
dp=[[INF for i in range(max_v)] for j in range(N+1)]
dp[0][0]=0
for i in range(N):
    for j in range(max_v):
        if j - v[i]>=0:
            dp[i+1][j]=min(dp[i+1][j],dp[i][j-v[i]]+w[i])
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])

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

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
w=[]
v=[]
for _ in range(N):
    ww,vv=map(int,input().split())
    w.append(ww)
    v.append(vv)
INF=float("inf")
max_v=10**5+1
dp=[[INF for i in range(max_v)] for j in range(N+1)]
dp[0][0]=0
for i in range(N):
    for j in range(max_v):
        if j - v[i]>=0:
            dp[i+1][j]=min(dp[i+1][j],dp[i][j-v[i]]+w[i])
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])

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

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007
inf = 10**12
#+++++

def main():
	#a = int(input())
	n, max_w = IN()
	#s = input()
	dp_v = [inf] * (10**5 + 100)
	dp_v[0] = 0
	for _ in range(n):
		add_v = []
		w, v = IN()
		for i, cv in enumerate(dp_v):
			if dp_v[i] == inf:
				continue
			if dp_v[i] + w < dp_v[i+v]:
				add_v.append((i+v, dp_v[i] + w))
		for i, nv in add_v:
			dp_v[i] = nv
			
	for i, min_w in enumerate(dp_v[::-1]):
		if min_w <= max_w:
			v=len(dp_v)-i-1
			return v
		
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
Weight = [0]
Value = [0]
ans = 0
for i in range(N):
    w, v = map(int, input().split())
    Weight.append(w)
    Value.append(v)
VS = sum(Value)
DP = [[float('inf')] * (VS + 1) for i in range(N + 1)]

for n in range(N + 1):
    for val in range(VS + 1):
        if val == 0:
            DP[n][val] = 0
        elif Value[n] > val:
            DP[n][val] = DP[n - 1][val]
        else:
            DP[n][val] = min(DP[n - 1][val], DP[n - 1][val - Value[n]] + Weight[n])
            if (n == N) and (DP[n][val] <= W):
                ans = max(ans, val)

print(ans)

Submission status: Accepted

Solution code:
# dp[v] i番目までの品物で、価値がv以上になるよう選んだときの重さの最小値。
# 品物を増やすごとに、配列を更新して使いまわす。
# とれる価値の最大値VmaxはN*max(vi) 添え字は0<=v<=Vmax dpリストの長さはVmax+1
# ループは1~N回回す　添え字は0<=i<=N-1<N
# 解答はN回ループした後のdp[j]<=Wとなる最大のj

import numpy as np

# 入力 table[i][0]は重さ、table[i][1]は価値
N, W = map(int, input().strip().split())
t = []
for i in range(N):
    t.append(list(map(int, input().strip().split())))
table = np.array(t)

# 初期化 wiの最大値は10^9
Vmax = N * max(table[:, 1])
dp = np.full(Vmax + 1, 10 ** 9)
dp[0] = 0

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

# 解答　dpの後ろから見て、最初にWを下回ったときのi
for j in range(Vmax, 0, -1):
    if dp[j] <= W:
        print(j)
        break

Submission status: Accepted

Solution code:
[n,w] = [int(i) for i in input().split()]
wv = []
for i in range(n):
    wv.append([int(i) for i in input().split()])
num = 100001
#num = 30
dp = [[10 ** 13]* num for i in range(n)]

"""
dp[i][j] = 重さ
i : i品目まで見たときの値
j : 価値の総和がjになる
"""
for i in range(n):
    dp[i][0] = 0
for i in range(n):
    if i != 0:
        for j in range(num):
            if j >= wv[i][1]:
                dp[i][j] = min(dp[i][j],dp[i-1][j])
                dp[i][j] = min(dp[i][j],dp[i-1][j-wv[i][1]]+wv[i][0])
            else:
                dp[i][j] = min(dp[i][j],dp[i-1][j])
    else:
        dp[i][wv[i][1]] = wv[i][0]
ans = 0
for i in range(num):
    if dp[n-1][i] <= w:
        ans = i
print(ans)
#print(dp)
"""
6 15
______
6 5
5 6
6 4
6 6
3 5
7 2

 0,   1,   2,   3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15,  16,  17,  18,  19,  20,  21,  22,  23,  24,  25,  26,  27,  28,  29,

[0, 100, 100, 100, 100,   6, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100],
[0, 100, 100, 100, 100,   6,   5, 100, 100, 100, 100,  11, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100],
[0, 100, 100, 100,   6, 100, 100, 100, 100,  12,  11, 100, 100, 100, 100,  17, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100],
[0, 100, 100, 100,   6, 100,   6, 100, 100, 100,  12, 100, 100, 100, 100,  18,  17, 100, 100, 100, 100,  23, 100, 100, 100, 100, 100, 100, 100, 100],
[0, 100, 100, 100,   6,   3, 100, 100, 100,   9, 100,   9, 100, 100, 100,  15, 100, 100, 100, 100,  21,  20, 100, 100, 100, 100,  26, 100, 100, 100],
[0, 100,   7, 100, 100, 100,  13,  10, 100, 100, 100,  16, 100,  16, 100, 100, 100,  22, 100, 100, 100, 100,  28,  27, 100, 100, 100, 100,  33, 100]
]
"""

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)


def main():
    N, W = map(int, input().split())
    weights = []
    values = []
    for i in range(N):
        w, v = map(int, input().split())
        weights.append(w)
        values.append(v)
    V = max(values)
    dp = [[float("inf")] * (N * V + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        w = weights[i]
        v = values[i]
        for j in range(N * V + 1):
            if j >= v:
                dp[i + 1][j] = min(dp[i][j - v] + w, dp[i][j])
            else:
                dp[i + 1][j] = dp[i][j]
    for j in range(N * V):
        if dp[-1][-j - 1] <= W:
            print(N * V - j)
            return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

n, w = map(int, input().split())
v = 100*10**3
item = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] + [float("inf")]*v] + [[float("inf")]*(v+1) for _ in range(n)]
wei, val = 0, 1

for i in range(n):
    for j in range(v+1):
        if item[i][val] <= j:
            dp[i+1][j] = min(dp[i][j], dp[i][j-item[i][val]] + item[i][wei])
        else:
            dp[i+1][j] = dp[i][j]

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

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
goods = [list(map(int, input().split())) for _ in range(n)]
dp = [[10 ** 11] * (10 ** 5 + 1) for _ in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    weight, value = goods[i]
    for sum_value in range(10 ** 5 + 1):
        if (sum_value - value) >= 0:
            dp[i + 1][sum_value] = min(dp[i + 1][sum_value], dp[i][sum_value - value] + weight)
        dp[i + 1][sum_value] = min(dp[i + 1][sum_value], dp[i][sum_value])

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

print(ans)

Submission status: Accepted

Solution code:
import sys
INF = 10**18
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N,W = LI()
dp = [INF for _ in range(N*1000+1)]

dp[0] = 0
for i in range(N):
    w,v = LI()
    for j in range(len(dp)-1,0,-1):
        if j-v < 0: continue
        dp[j] = min(dp[j],dp[j-v]+w)

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

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(N)]
import numpy as np
V=N*1000+1
dp=np.ones(V,dtype=np.int64)*(W+1)
dp[0]=0
for w,v in WV:
    dp[v:]=np.minimum(dp[v:],dp[:-v]+w)
print(max([i for i in range(V) if dp[i]<=W]))