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 numpy as np

N, W = map(int, input().split())
inf = 10**18
M = 10**5
#dp = [0 for i in range(10**5+1)]


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

Submission status: Accepted

Solution code:
import numpy as np
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    a, b = map(int, input().split())
    w += [a]
    v += [b]
 
DP = np.ones(N*1000+1, dtype=int) *(W+1)
DP[0] = 0
#総価値 i 円を得るために最低限必要な重量
for i in range(N):
    DP[v[i]:] = np.minimum(DP[:-v[i]]+ w[i], DP[v[i]:])
ans = 0
for k in range(N*1000+1):
    if DP[k] <= W:
        ans = k
        
print(ans)

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
INF = 10**12 + 5
cost=[[INF for i in range(100001)] for j in range(n+1)]
value=[list(map(int,input().split())) for i in range(n)]

for i in range(1,n+1):
  for j in range(100001)[::-1]:
    weight_=value[i-1][0]
    value_=value[i-1][1]
    if j < value_:
      cost[i][j]=min(cost[i-1][j],weight_)
    else:
      cost[i][j]=min(cost[i-1][j-value_]+weight_,cost[i-1][j])
for i in range(100001)[::-1]:
    if cost[-1][i]<=w:print(i+1);exit()

Submission status: Accepted

Solution code:
n,w = map(int,input().split())
w_ls, v_ls = [0] * n, [0] * n
for i in range(n):
    w_ls[i], v_ls[i] = map(int,input().split())
V = sum(v_ls)
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_ls[i] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j-v_ls[i]] + w_ls[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:
def solve(c, a):
    dp = [float('inf')]*(2*10**5)
    dp[0] = 0
    for w, v in a:
        for i in range(len(dp)-1, -1, -1):
            if dp[i] != float('inf'):
                dp[i+v] = min(dp[i+v], dp[i] + w)
    return next(i for i in range(len(dp)-1, -1, -1) if dp[i] <= c)
  
n, k = map(int, input().split())
a = []
for _ in range(n):
    a.append(list(map(int, input().split())))
print(solve(k, a))

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
weights, values = zip(*[tuple(map(int, input().split())) for _ in range(n)])
UV = 10**5
INF = 10**10
dp = [INF]*(UV+1)
dp[0] = 0

for i in range(1, n+1):
    for j in reversed(range(1, UV+1)):
        if j-values[i-1] < 0:
            continue
        dp[j] = min(dp[j], dp[j-values[i-1]]+weights[i-1])

ans = 0
for j in reversed(range(UV+1)):
    if dp[j] <= w:
        ans = j
        break
print(ans)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
value,weight = [0],[0]
for i in range(N):
  w,v = map(int,input().split())
  value.append(v)
  weight.append(w)
V = sum(value)
dp = [[0]+[10**12]*V for _ in range(N+1)]
for i in range(1,N+1):
  for j in range(1,V+1):
    dp[i][j] = min(dp[i-1][j], dp[i-1][max(0, j-value[i])]+weight[i] )
for i in range(V,0,-1):
  if dp[N][i] <= W:
    print(i)
    quit()

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
weights, values = zip(*[tuple(map(int, input().split())) for _ in range(n)])
UV = 10**5
INF = 10**10
dp = [[INF]*(UV+1) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0
    
for i in range(1, n+1):
    for j in range(1, UV+1):
        dp[i][j] = dp[i-1][j]
        if 0 <= j-values[i-1]:
            dp[i][j] = min(dp[i][j], dp[i-1][j-values[i-1]]+weights[i-1])

ans = 0
for i in reversed(range(UV+1)):
    if dp[-1][i] <= w:
        ans = i
        break
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    N, W = map(int, input().split())
    weight = []
    value = []
    for i in range(N):
        w, v = map(int, input().split())
        weight.append(w)
        value.append(v)
    dp = [[0 if i == 0 else W * N for i in range(N * max(value) + 1)]]
    for i in range(N):
        d = []
        for v in range(N * max(value) + 1):
            if v >= value[i]:
                d.append(min(dp[-1][v - value[i]] + weight[i], dp[-1][v]))
            else:
                d.append(dp[-1][v])
        dp.append(d)
    for i in reversed(range(N * max(value) + 1)):
        if dp[-1][i] <= W:
            print(i)
            return


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
weights, values = zip(*[tuple(map(int, input().split())) for _ in range(n)])
UV = 10**5
INF = float('inf')
dp = [[0]+[INF]*UV for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, UV+1):
        dp[i][j] = dp[i-1][j]
        if 0 <= j-values[i-1]:
            dp[i][j] = min(dp[i][j], dp[i-1][j-values[i-1]]+weights[i-1])

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

Submission status: Accepted

Solution code:

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)

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

max_value, max_weight = 0, 0
for w, v in wv:
    max_weight += w
    max_value += v
wv.sort()

dp = np.ones(max_value + 1, dtype=int) * max_weight

for w, v in wv:
    np.minimum(dp[v:] - w, dp[:-v], out=dp[:-v])

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

print(ans)

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
v_max = 10 ** 3 * n
w_max = 10 ** 18
dp = [[w_max for _ in range(v_max + 1)] for _ in range(n + 1)]

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

for i in range(n):
    w_, v_ = wv[i]
    for j in range(v_max + 1):
        if j + v_ <= v_max:
            dp[i+1][j+v_] = min(dp[i][j] + w_, dp[i][j + v_])
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])


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

Submission status: Accepted

Solution code:


n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
v_max = 10 ** 5
w_max = 10 ** 18
dp = [[w_max for _ in range(v_max + 1)] for _ in range(n + 1)]

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

for i in range(n):
    w_, v_ = wv[i]
    for j in range(v_max + 1):
        if j + v_ <= v_max:
            dp[i+1][j+v_] = min(dp[i][j] + w_, dp[i][j + v_])
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])


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

Submission status: Accepted

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

dp = [[inf for j in range(10**5+1)] for i in range(N+1)] #dp[i][v] = W

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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    INF = 10**10
    VMAX=10**3*N
    dp=[[INF for j in range(VMAX+1)] for i in range(N+1)]
    dp[0][0] = 0
    for i in range(1,N+1):
        for j in range(VMAX+1):
            if j-v[i-1] >=0:
                dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i-1]]+w[i-1])
            else:
                dp[i][j] = dp[i-1][j]

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


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    n, w = map(int, input().split())
    items = [tuple(map(int, input().split())) for i in range(n)]

    dp = [[10**12] * 100001 for i in range(n + 1)]
    dp[0][0] = 0

    for i, item in enumerate(items):
        for i_v in range(100001):
            if item[1] - i_v > 0:
                dp[i + 1][i_v] = dp[i][i_v]
            else:
                dp[i + 1][i_v] = min(dp[i][i_v - item[1]] + item[0], dp[i][i_v])

    result = 0
    for sum_v, weght in enumerate(dp[-1]):
        if weght <= w:
            result = sum_v
    print(result)


if __name__ == '__main__':
    main()

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)
    
maxv = sum(v)
dp = [[float('inf')]*(maxv+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for sumv in range(maxv+1):
        if sumv - v[i]  >= 0:
            dp[i+1][sumv] = min(dp[i+1][sumv], dp[i][sumv-v[i]] + w[i])
        dp[i+1][sumv] = min(dp[i+1][sumv], dp[i][sumv])

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

n, w = map(int, readline().split())
wv = [list(map(int, readline().split())) for i in range(n)]
dp = np.full(n * 1000 + 1, w + 1, dtype=int)
dp[0] = 0
for x, y in wv:
    dp[y:] = np.minimum(dp[y:], dp[:-y] + x)
print(np.max(np.where(dp <= w)))

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

dp = [0] + [float("inf")] * 10**5

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

res = 0
for v, e in enumerate(dp):
    if e <= W:
        res = v

print(res)

Submission status: Accepted

Solution code:
N, W = map(int,input().split())
wn = [0]*N
vn = [0]*N
vnmax = pow(10,3)*N+1
dp = [10**9+1]*(vnmax)
dp[0] = 0

for n in range(N):
  wn, vn = map(int,input().split())
  for v in range(vnmax-1,vn-1,-1):
    dp[v] = min(dp[v],dp[v-vn]+wn)

num = 0
for v in range(1,vnmax):
  if dp[v] <= W: num = v
print(num)

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
x=[0]+[-1]*110000

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

    for j in range(len(x))[::-1]:# j: len(x)から1ずつ減る
        if x[j]>=0:
            if  x[j]+w<=W:
                if x[j+v]<0:
                    x[j+v]=x[j]+w
                    ma=max(ma,j+v)
                else:
                    x[j+v]=min(x[j+v],x[j]+w)

print(ma)

Submission status: Accepted

Solution code:
n, w = [int(i) for i in input().split()]
dp = [10 ** 18] * (10 ** 5 + 1)
dp[0] = 0
for _ in range(n):
    u, v = [int(i) for i in input().split()]
    for i in reversed(range(len(dp))):
        if i + v < len(dp) and dp[i]+u <= w:
            dp[i + v] = min(dp[i + v], dp[i] + u)
ans = 0
for i, j in enumerate(dp):
    if j != 10 ** 18:
        ans = max(ans, i)
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n,w = map(int,readline().split())
WV = []
for i in range(n):
	WV.append(list(map(int,readline().split())))

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

#価値j以上で重さがwを満たすようなものの最大値
for i in range(n):
	for j in range(10**5+1):
		if WV[i][1] - j > 0:
			dp[i+1][j] = dp[i][j]
		else:
			dp[i+1][j] = min(dp[i][j],dp[i][j-WV[i][1]]+WV[i][0])

ans = 0
for idx,i in enumerate(dp[-1]):
	if i <= w:
		ans = idx

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
W, V = [], []
for i in range(n):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
sumV = sum(V)
A = [1 << 30 for j in range(sumV+1)]
A[0] = 0
for i in range(n):
    B = []
    for j in range(V[i]):
        B.append(A[j])
    for j in range(V[i], sumV+1):
        B.append(min(A[j], A[j-V[i]]+W[i]))
    A = B
for j in range(sumV, 0, -1):
    if A[j] <= m:
        print(j)
        exit()

Submission status: Accepted

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

dp = [0] + [float("inf")]*(10**5)
for i in range(n):
    for j in range(10**5,wv[i][1]-1,-1):
        dp[j] = min(dp[j],dp[j-wv[i][1]]+wv[i][0])

res = 0
for v,e in enumerate(dp):
    if e <= w:
        res = v
print(res)

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
sv=sum(list(zip(*l))[1])
dp=[10**12]*(sv+1)
dp[0]=0

for wi,vi in l:
    for j in range(sv-vi,-1,-1):
        dp[j+vi]=min(dp[j+vi],dp[j]+wi)
        #except IndexError:print(j,sv,vi);exit()
ans=0

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

Submission status: Accepted

Solution code:
INF = 10 ** 9 + 10
MAX_V = 1010

N, W = map(int, input().split())
MAX_SUM_V = N * MAX_V

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

dp = [[INF] * MAX_SUM_V for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for sum_v in range(MAX_SUM_V):
        if sum_v - v[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - v[i]] + w[i])
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])

for sum_v in range(MAX_SUM_V):
    if(dp[N][sum_v] <= W):
        res = sum_v
print(res)

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

V = sum(v)

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

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())
    
# dp[i][j]:i番目の品物を詰めて価値jのときの重さの最小値
dp = [[10**9+1]*(sum(v)+1) for i in range(N+1)]
dp[0][0] = 0

#v[i-1]を使うかどうか
for i in range(1,N+1):
    #価値がjのときの最小の重さ
    for j in range(sum(v)+1):
        if j >= v[i-1]:
            dp[i][j] = min(dp[i-1][j-v[i-1]]+w[i-1],dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

# 重さがW以下のもので価値が最大となるものを探す
ans = 0
for i in range(sum(v)+1):
    if dp[-1][i] <= W:
        ans = max(ans,i)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N,W = map(int,input().split())
V_sum = 0
w_l = []
v_l = []
for i in range(N):
    w,v = list(map(int,input().split()))
    V_sum+=v
    w_l.append(w)
    v_l.append(v)
dp = np.full(V_sum+1,W+1)
dp[0] = 0
for i in range(N):
    dp[v_l[i]:] = np.minimum(dp[v_l[i]:],dp[:-v_l[i]]+w_l[i])
for i in range(V_sum,-1,-1):
    if dp[i]<=W:
        print(i)
        break

Submission status: Accepted

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

# DPはnumpy使わずにpypy3で提出する(pythonより3倍くらい早い）
# Dとの違い：Wが大きく、vは小さい

'''
3 8
3 30
4 50
5 60
'''

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

v_max = (max(v)+1) * N
dp = [[None] * v_max for _ in range(N+1)]
dp[0] = [float('inf')] * v_max
dp[0][0] = 0

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

# print(dp)
print(len([i for i in dp[N] if i <= W]) - 1)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]
weights = list(map(lambda x: x[0], items))
values = list(map(lambda x: x[1], items))
sum_weights = sum(weights)
sum_values = sum(values)

dp = [([0] + [sum_weights*2 for _ in range(sum_values)]) for _ in range(N+1)]

for i in range(N):
    for v in range(1, sum_values+1):
        if v - values[i] >= 0:
            dp[i+1][v] = dp[i][v-values[i]] + weights[i]
        
        dp[i+1][v] = min(dp[i+1][v], dp[i][v])
        
for i in reversed(range(sum_values+1)):
    if dp[N][i] <= W:
        print(i)
        break

Submission status: Accepted

Solution code:
def solve(items, n, W):
    V = sum([v for _, v in items])
    dp = [float('inf')] * (V + 1)
    dp[0] = 0

    for w, v in items:
        for i in range(V, v-1, -1):
            dp[i] = min(dp[i], dp[i-v] + w)
    
    for i in range(V, -1, -1):
        if dp[i] <= W:
            return i

    return 0


def main():
    inp = lambda: [int(x) for x in input().split()]
    n, w = inp()
    items = [inp() for _ in range(n)]
    print(solve(items, n, w))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

for _ 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 = map(int, input().split())

import numpy as np
dp = np.full(N*1000+1, W+1, dtype=int)
dp[0] = 0


for _ 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 sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    MAX_V = 10 ** 3 * N + 1

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

    for mv in range(MAX_V):
        for i, (w, v) in enumerate(items):
            if mv - v >= 0:
                dp[i+1][mv] = min(dp[i][mv], dp[i][mv - v] + w)
            else:
                dp[i+1][mv] = dp[i][mv]

    print(max([v for v, w in enumerate(dp[N]) if w <= W]))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

w = []
v = []

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

DP = [[float('inf')]*(100001) for i in range(N+1)]

DP[0][0] = 0

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

for i in range(100001):
    if DP[N][100000-i] <= W:
        break
print(100000-i)

Submission status: Accepted

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

L = 100001
dp = [float('inf')]*100001
dp[0] = 0

for _ in range(N):
    w,v = map(int,input().split())
    for k in reversed(range(v,L)):
        dp[k] = min(dp[k], dp[k-v]+w)

print(next(v for v,w in zip(reversed(range(L)), reversed(dp)) if w <= W))

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
goods = [list(map(int, input().split())) for i in range(N)]
V = sum([x[1] for x in goods])
INF = 10**10
dp = [[INF]*(V+1) for i in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
for i in range(N):
    for j in range(V):
        if j+1 >= goods[i][1]:
            dp[i+1][j+1] = min(dp[i][j+1], dp[i][j+1-goods[i][1]] + goods[i][0])
        else:
            dp[i+1][j+1]= dp[i][j+1]
ans = 0
for i in range(V):
    if dp[N][i+1] <= W:
        ans = i+1
print(ans)

Submission status: Accepted

Solution code:
#dp[i][sum_v]:= i-1以下の品物の中から、価値をsum_v以上になる時の重さの最小値

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

w,v=[0],[0]

for _ in range(N):
    wi,vi=map(int,input().split())
    w.append(wi)
    v.append(vi)

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

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

ans=0

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

Submission status: Accepted

Solution code:
# #!/usr/bin/env python3

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

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

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

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

dp[0][0] = 0

# # dp[i + 1][sum_v]: i番目までの品物から価値がsum_v以上になるように選んだときの、重さの総和の最小値
# # dp[i + 1][sum_v] = max(dp[i][sum_v], dp[i][sum_v - v[i]] + w[i])

for i in range(N):
    for sum_v in range(max_sum_v + 1):
        if sum_v - value[i] >= 0:
            dp[i + 1][sum_v] = min(dp[i][sum_v], dp[i][sum_v - value[i]] + weight[i])
        else:
            dp[i + 1][sum_v] = dp[i][sum_v]

for sum_v in range(max_sum_v + 1):
    if dp[N][sum_v] <= W:
        res = sum_v

print(res)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
L = 100000
dp = [[1000000001 for _ in range(L+1)] for _ in range(N+1)]
W, V = [], []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
dp[0][0] = 0
for i in range(N):
    for j in range(L+1):
        if j - V[i] >= 0:
            dp[i+1][j] = min(dp[i][j], dp[i][j-V[i]] + W[i])
        else:
            dp[i+1][j] = dp[i][j]
for i, d in enumerate(dp[N]):
    if d <= M:
        maxv = i
print(maxv)

Submission status: Accepted

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

VMAX = 10**5 + 100
ans = 0
dp = [[float('inf')] * (VMAX+1) for _ in range(N+1)]
dp[0][0] = 0
for n in range(N):
    for v in range(VMAX):
        if dp[n][v] != float('inf'):
            dp[n+1][v] = min(dp[n+1][v], dp[n][v])
            dp[n+1][v+V[n]] = min(dp[n+1][v+V[n]], dp[n][v] + W[n])

            if dp[n+1][v+V[n]] <= L:
                ans = max(ans, v+V[n])
# print(*dp, sep='\n')
print(ans)

Submission status: Accepted

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

#output
import numpy as np
V = max(v)
INF = 10**10
dp = np.full((N+1, N*V+1), INF)
dp[0, 0] = 0

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

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

print(answer)

Submission status: Accepted

Solution code:
import numpy as np

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

# dp[i][sum_v] := i-1 番目までの品物から価値が sum_v 以上を達成するように選んだときの、重さの総和の最小値
# dp[i + 1][sum_v] = min(dp[i][sum_v], dp[i][sum_v - v] + w)
INF = 10**10
dp = np.array([INF] * 10**6)
dp[0] = 0
for _ in range(N):
    w, v = map(int, input().split())
    # for sum_v in range(10**2 + 1):
    #     if sum_v - v < 0:
    #         continue
    #     dp[sum_v] = min(dp[sum_v], dp[sum_v - v] + w)
    np.minimum(dp[:-v] + w, dp[v:], out=dp[v:])

# print(dp[:100])
ans = 0
for i in range(len(dp)):
    if dp[i] <= W:
        ans = i
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

N, W = MAP()
w, v = ZIP(N)

max_v = 0
dp = np.full(1000*N+1, 10**18, dtype=np.int64)
dp[0] = 0
for w, v in zip(w, v):
	np.minimum(dp[v:max_v+v+1], dp[:max_v+1]+w, out=dp[v:max_v+v+1])
	max_v += v
print(np.where(dp <= W)[0].max())

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

N, W = MAP()
w, v = ZIP(N)
max_v = sum(v)
dp = [INF]*(max_v+1)
dp[0] = 0
for w, v in zip(w, v):
	for i in range(max_v, -1, -1):
		if i-v >= 0:
			dp[i] = min(dp[i], dp[i-v]+w)

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

Submission status: Accepted

Solution code:
import numpy as np

N, W = map(int, input().split())
dp = np.array([W + 1] * (N * 1000 + 1))
dp[0] = 0
for _ in range(N):
  w, v = map(int, input().split())
  dp[v:] = np.minimum(dp[v:], dp[:-v] + w)
max_value = 0
for v, w in enumerate(dp):
  if w <= W:
    max_value = v
print(max_value)

Submission status: Accepted

Solution code:
# E - Knapsack 2
def knapsack_heavy(weight_limit: int, weights: list, values: list) -> int:
    max_value = sum(values)
    dp = [0] + [1 << 30] * max_value  # dp[i] := minimum weight at value i
    for w, v in zip(weights, values):
        for cur_v in range(max_value, v - 1, -1):
            if dp[cur_v - v] + w < dp[cur_v]:
                dp[cur_v] = dp[cur_v - v] + w
    return max(v for v, w in enumerate(dp) if w <= weight_limit)


def main():
    N, W, *WV = map(int, open(0).read().split())
    print(knapsack_heavy(W, WV[::2], WV[1::2]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# E - Knapsack 2
from collections import defaultdict


def knapsack_heavy(limit: int, weight: list, value: list) -> int:
    dp = defaultdict(lambda: 1 << 30)  # dp[i] := minimum weight at value i
    dp[0] = 0
    for w, v in zip(weight, value):
        for cur_v, cur_w in tuple(dp.items()):
            if w + cur_w <= limit:
                dp[v + cur_v] = min(dp[v + cur_v], w + cur_w)
    return max(dp.keys())


def main():
    N, W, *WV = map(int, open(0).read().split())
    print(knapsack_heavy(W, WV[::2], WV[1::2]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# E - Knapsack 2
def knapsack_heavy(limit: int, weight: list, value: list) -> int:
    lim = sum(value)
    dp = [0] + [1 << 30] * lim  # dp[i] := minimum weight at value i
    for w, v in zip(weight, value):
        for cur_v in range(lim, v - 1, -1):
            dp[cur_v] = min(dp[cur_v], dp[cur_v - v] + w)
    ret = max(v for v, w in enumerate(dp) if w <= limit)
    return ret


def main():
    N, W, *WV = map(int, open(0).read().split())
    print(knapsack_heavy(W, WV[::2], WV[1::2]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
max_v = 100 * 10**3
dp = [float("inf")] * (max_v + 1)
dp[0] = 0

for _ in range(N):
    w, v = map(int, input().split())
    for dp_v in reversed(range(max_v+1)):
        dp_w = dp[dp_v]
        if (dp_v == 0 or dp_w < float("inf")) and dp_v + v <= max_v:
            dp[dp_v + v] = min(dp[dp_v + v], dp[dp_v] + w)

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

print(ans)

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
dp = [[(10**9+1) for _ in range(10**5+1)] for _ in range(n)]
wn, vn = map(int, input().split())
dp[0][0] = 0
dp[0][vn] = wn
for i in range(1, n):
    wn, vn = map(int, input().split())
    for j in range(10**5+1):
        if (j - vn) >= 0:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-vn] + wn)
        else:
            dp[i][j] = dp[i-1][j]
#print(dp)
ansl = dp[n-1][::-1]
#print(ansl)
for k in range(len(ansl)):
    if ansl[k] <= w:
        print(10**5-k)
        break

Submission status: Accepted

Solution code:
from decimal import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]

n,w = li()
l = []
for i in range(n):l.append(li())
l.sort()
d = defaultdict(int)
for i in range(10**5 + 10):d[i] = float('inf')
for i in l:

    for j in range(10 ** 5 + 10,0,-1):
        d[j + i[1]] = min(d[j + i[1]],d[j] + i[0])
    d[i[1]] = min(d[i[1]],i[0])
ans = 0
for i in range(10**5 + 10):
    if d[i] <= w:ans = i
print(ans)