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:
#!/usr/bin/env python3
def main():
    import numpy as np

    np.set_printoptions(linewidth=200)

    N, W = map(int, input().split())
    lst = [list(map(int, input().split())) for _ in range(N)]
    v_max = 10 ** 3 * 100 * 10
    w_max = 10 ** 9 * v_max

    # i以上の価値を持つときの最小重量
    dp = np.full(v_max, w_max, dtype=np.int64)
    # initialize
    dp[0] = 0

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

    ans = 0
    for i, w in enumerate(dp):
        if w <= W:
            ans = i
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
INF = float('inf')
N, W = map(int, input().split())

# dp[i][j] : i番目までの品物を使い、価値がjとなるときの重さ
dp = [[INF] * 100010 for _ in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    w, v = map(int, input().split())
    for j in range(100010):
        if j >= v:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v] + w)
        else:
            dp[i][j] = dp[i - 1][j]

ans = 0
for i in range(100010):
    if dp[N][i] <= W:
        ans = max(ans, i)

print(ans)

Submission status: Accepted

Solution code:
INF = float('inf')

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

# dp[i][j] : i番目までの品物を使い、価値がjとなるときの重さ
dp = [[INF] * 100010 for _ in range(N + 1)]
for i in range(N + 1):
    dp[i][0] = 0

for i in range(1, N + 1):
    w, v = map(int, input().split())
    for j in range(100010):
        if j >= v:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v] + w)
        else:
            dp[i][j] = dp[i - 1][j]

ans = 0
for i in range(100010):
    if 0 < dp[N][i] <= W:
        ans = max(ans, i)

print(ans)

Submission status: Accepted

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

dp = [[float('inf')] * (10**5+1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    for j in range(10**5+1):
        if j - knap[i][1] >= 0:
            dp[i+1][j] = min(dp[i][j-knap[i][1]] + knap[i][0], dp[i][j])
        else :
            dp[i+1][j] = dp[i][j]
for i in range(10**5, 0, -1):
    if dp[n][i] <= w :
        print(i)
        exit()

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
w=[]
v=[]
for i in range(n):
  w_,v_=map(int,input().split())
  w.append(w_)
  v.append(v_)
dp=[[float('inf')]*(100001) 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[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]
  
ans=100000
while dp[n][ans]>W:
  ans-=1
print(ans)

Submission status: Accepted

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

import numpy as np

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

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

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

Submission status: Accepted

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


def main(n,w,p):
    #dp[n][v]
    dp = [[0 for i in range(n*10**3+1)]]
    ans = 0
    for i in range(n):
        item = p[i]
        temp = []
        for j in range(n*10**3+1):
            #Cannot achieve
            cur = 0
            if j<item[1]:
                cur = dp[i][j]
                temp.append(cur)
            elif j==item[1]:
                cur = item[0]
                if dp[i][j]:
                    cur = min(item[0],dp[i][j])
                temp.append(cur)
            else:
                if dp[i][j] and dp[i][j-item[1]]:
                    cur = min(dp[i][j],dp[i][j-item[1]]+item[0])
                elif dp[i][j]:
                    cur = dp[i][j]
                elif dp[i][j-item[1]]:
                    cur = dp[i][j-item[1]]+item[0]
                temp.append(cur)
            if cur and cur<=w:
                ans = max(ans,j)
        dp.append(temp)
    print(ans)

                    
if __name__=="__main__":
    n,w,p = getval()
    main(n,w,p)

Submission status: Accepted

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

def main():
    N, W = map(int,input().split())
    WG = [0]
    V = [0]
    for i in range(N):
        w, v = map(int,input().split())
        WG.append(w)
        V.append(v)
    
    dp = [[float('inf')]*(max(V)*N+1) for _ in range(N+1)]
    dp[0][0] = 0
    
    for i in range(1,N+1):
        for v in range(0,max(V)*N+1):
            if v-V[i] < 0:
                dp[i][v] = dp[i-1][v]
                continue
            dp[i][v] = min(dp[i-1][v], dp[i-1][v-V[i]]+WG[i])
    
    ans = 0
    for i in range(max(V)*N+1):
        if dp[N][i] <= W:
            ans = i
            
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
w = [-1]
v = [-1]
for i in range(N):
    x,y = map(int,input().split())
    w.append(x)
    v.append(y)
INF = 10**11+1
dp = [[INF]*(10**5+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(1,N+1):
    for j in range(0,10**5+1):
        if (j-v[i]>=0):
            dp[i][j] =min(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
        else:
            dp[i][j] = dp[i-1][j]
ans = 10**5
while dp[N][ans]>W:
    ans -= 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

input = sys.stdin.readline

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

# ---------------------------------------

N, W = inpl()
INF = 10**12
dp = [[INF] * 100001 for i in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):
    w, v = inpl()
    for j in range(0, 100001):
        if j - v >= 0:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-v] + w)
        else:
            dp[i][j] = dp[i-1][j]
            
ans = 100000
while dp[N][ans] > W:
    ans -= 1

_debug(dp[N][ans])
print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
Items = [tuple(map(int, input().split())) for _ in range(N)]
DP = [float('inf')] * 10 ** 6
DP[0] = 0
for w, v in Items:
    D = DP[:]
    for i, d in enumerate(DP):
        if w + d > W:
            continue
        D[i + v] = min(DP[i + v], w + d)
    DP = D
ans = 0
for i, d in enumerate(DP):
    if d == float('inf'):
        continue
    ans = i
print(ans)

Submission status: Accepted

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

dp = [[float('inf') for i in range(10**5+1)] for j in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    w, v = map(int, input().split())
    for j in range(0, 10**5+1):
        if (j-v) >= 0:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-v]+w)
        else:
            dp[i][j] = dp[i-1][j]
    #print(dp)  
    
ans = 10**5
while(dp[N][ans])>W:
  ans -= 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    N, W = map(int, input().split())
    max_val = 10 ** 5
    dp = [[float('inf')]*(max_val + 1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(1, N+1):
        w, v = map(int, input().split())
        for j in range(max_val + 1): # 価値がj以上になるときの最小の重さを選ぶ
            if j - v < 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min([
                    dp[i-1][j-v] + w,
                    dp[i-1][j]
                ])

    for i, w in enumerate(reversed(dp[-1])):
        if w <= W:
            print(max_val - i)
            exit()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,W = map(int,input().split())
wl = []
vl = []
for i in range(n):
    w,v =  map(int,input().split())
    wl.append(w)
    vl.append(v)
s = sum(vl)

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


for i in range(n):
    for j in range(s+1):
        if vl[i]-j>0:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j],dp[i][j-vl[i]]+wl[i])
        #[print(*dp[l]) for l in range(n+1)]
        #print("---------------")
ans = 0
for i in range(n+1):
    for j in range(s+1):
        if dp[i][j]<=W:
            ans = max(ans,j)
print(ans)

Submission status: Accepted

Solution code:
n,w=map(int, input().split())
g=[0]
v=[0]
for i in range(n):
    G,V=map(int, input().split())
    g.append(G)
    v.append(V)

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

for i in range(1,n+1):
    for j in range(10**5+10):
        if j-v[i]>=0:dp[i][j]=min(dp[i-1][j],dp[i-1][j-v[i]]+g[i])
        else:dp[i][j]=dp[i-1][j]

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

Submission status: Accepted

Solution code:
import numpy as np
import warnings
warnings.filterwarnings('ignore')

Mv = 10 ** 5
Mw = 10 ** 11

N, W = list(map(int, input().split()))
w = np.array([0] * (N+1))
v = np.array([0] * (N+1))
for i in range(N):
    w[i+1], v[i+1] = map(int, input().split())

V = np.max(v)

# dp[i,j]:iまでのアイテムで価値がj以下の時の重さの最小値
dp = np.array([[Mw] * (Mv + 1)] * (N+1))
dp[0][0] = 0
for i in range(1, N+1):
    tmp_arr = np.full(Mv+1, Mw, dtype=int)
    tmp_arr[v[i]:] = dp[i-1][:-v[i]] + w[i]
    dp[i] = np.minimum(dp[i-1], tmp_arr)

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

Submission status: Accepted

Solution code:
n,w = map(int,input().split())
ls = [list(map(int,input().split())) for _ in range(n)]
inf = float("inf")
dp = [[inf]*(100000+1) for _ in range(n+1)]
dp[0][0] = 0
ans = 0
for i in range(n):
    for v in range(100001):
        if v - ls[i][1] >= 0:
            dp[i+1][v] = min(dp[i][v],dp[i][v-ls[i][1]]+ls[i][0])
        else:
            dp[i+1][v] = dp[i][v]
for j in range(100001):
    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):
  wi, vi = map(int, input().split())
  w.append(wi)
  v.append(vi)
dp = [[float('inf')]*(max(v)*N+1) for _ in range(N+1)]
dp[0][0] = 0

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

ans = 0
for sum_v in range(max(v)*N+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)
#dp[i+1][j] := i番目までの品物から総和がjとなるように選んだ時の重さの総和の最小値
dp=[[float("inf")]*(max(v)*N+1) for _ in range(N+1)]
#初期条件
dp[0][0]=0
for i in range(N):
	for j in range(max(v)*N+1):
		if v[i]>j:
			dp[i+1][j] = dp[i][j]
		else:
			dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]]+w[i])

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

Submission status: Accepted

Solution code:
# E - Knapsack 2
# W の制約が大きいとき

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

INF = 10**10

# dp[i][j]: i-1 番目までの品物から価値が j を達成するように選んだときの重さの総和の最小値
dp = [[INF]*(v_max+1) for _ in range(N+1)]

# 初期条件
# 品物を一個も選ばないとき価値は 0, 重さも 0
dp[0][0] = 0

# i-1 番目の品物
for i in range(1,N+1):
    # 価値 sum_v
    for sum_v in range(v_max+1):
        # i-1 番目の品物を選ぶとき
        if (sum_v - value[i-1] >= 0):
            dp[i][sum_v] = min(dp[i][sum_v], dp[i-1][sum_v - value[i-1]] + weight[i-1])
        # v-1 番目の品物を選ばないとき
        dp[i][sum_v] = min(dp[i][sum_v],dp[i-1][sum_v])

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

Submission status: Accepted

Solution code:
N,W=[int(x) for x in input().split()]
w=[-1 for _ in range(N)]
v=[-1 for _ in range(N)]
for i in range(N):
	w[i],v[i]=[int(x) for x in input().split()]
#Constraints N<=100 W<=10^9 w[i]<=10^9 and v[i]<=10^3
#dp[w] used to store maximum value at weight<=w
#dp[v] used to store minimum weight at value==v
dp=[1000000002 for _ in range(100001)]
dp[0]=0
for i in range(N):
	for v_ in range(100000,v[i]-1,-1):
		#print(v_-v[i])
		dp[v_]=min(dp[v_],dp[v_-v[i]]+w[i])
for v_ in range(100000,-1,-1):
	if dp[v_]<=W: print(v_); break

Submission status: Accepted

Solution code:
n, W = map(int, input().split())
inf = 10 ** 10
V = 10 ** 5
dp = [inf for _ in range(V + 1)]
dp[0] = 0
ans = 0
for _ in range(n):
    w, v = map(int, input().split())
    for i in range(V, v - 1, -1):
        dp[i] = min(dp[i], dp[i - v] + w)
        if dp[i] <= W:
            ans = max(ans, i)
print(ans)

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
INF = float('inf')
P = []
for _ in range(n):
    iw, iv = map(int, input().split())
    P.append([iw, iv])

dp = [[INF for i in range(10 ** 5 + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(1, n + 1):
    for j in range(10 ** 5 + 1):
        if j - P[i - 1][1] >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - P[i - 1][1]] + P[i - 1][0])
        else:
            dp[i][j] = dp[i - 1][j]

ans = 10 ** 5
while dp[n][ans] > w:
    ans -= 1
print(ans)

Submission status: Accepted

Solution code:
n,W = map(int,input().split())
w,v = [],[]
for i in range(n):
    wi,vi = map(int,input().split())
    w.append(wi)
    v.append(vi)
mv = sum(v)
INF = float("INF")
dp = [[INF]*(mv+100) for i in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for sv in range(mv+100):
        if sv-v[i] >= 0:
            dp[i+1][sv] = min(dp[i+1][sv],dp[i][sv-v[i]]+w[i])
        dp[i+1][sv] = min(dp[i+1][sv],dp[i][sv])
    #print(dp)
ans = 0
for i in range(mv+100):
    #print(dp[n][i])
    if dp[n][i] <= W:
        ans = max(ans,i)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N, W = map(int, input().split())
knap = []
for i in range(N):
    knap.append(tuple(map(int, input().split())))

s_val = sum([v for w, v in knap])
    
INF = float("inf")
dp = np.full(s_val+1, INF)
dp[0] = 0

for i, (w, v) in enumerate(knap):
    dp[v:] = np.minimum(dp[v:], dp[:-v]+w)
    
print(max([i for i in range(s_val+1) if dp[i] <= W]))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
#D流用したので文字滅茶苦茶
N,W=map(int,input().split())

dp=[10**9+1]*(10**5+1)
dp[0]=0


for _ in range(N):
    w,v=map(int,input().split())
    for i in range(10**5+1)[::-1]:
        if dp[i]!=-10**9+1 and i+v<=10**5:
            dp[i+v]=min(dp[i]+w,dp[i+v])


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

print(ans)

Submission status: Accepted

Solution code:
def edu_dp_e_knapsack2():
    n, c = map(int, input().split())
    w, v = [0], [0]
    for _ in range(n):
        a, b = map(int, input().split())
        w.append(a)
        v.append(b)
    dp = [[float('inf')] * 100001 for _ in range(n + 1)]
    dp[0][0] = 0
    for i in range(1, n + 1):
        for j in range(0, 100001):
            dp[i][j] = dp[i - 1][j]
            if j >= v[i]:
                dp[i][j] = min(dp[i][j], dp[i - 1][j - v[i]] + w[i])
    ans = 100000
    while dp[n][ans] > c: ans -= 1
    print(ans)
edu_dp_e_knapsack2()

Submission status: Accepted

Solution code:
INF = 1e10
n, w = map(int, input().strip().split())
data = [list(map(int, input().strip().split())) for _ in range(n)]
data = [[INF, INF]] + data

max_value = n * 1000
# i番目に価値の総和がj以上となるように選んだときの重さの最小値 双対問題？
dp = [[INF] * (max_value + 1) for _ in range(n + 1)]

dp[0][0] = 0

for i in range(1, n + 1):
    for j in range(max_value + 1):
        wi, vi = data[i][0], data[i][1]
        # i番目の品物を入れる場合
        take = dp[i - 1][j - vi] + wi if j - vi >= 0 else INF
        # 入れない場合
        dismiss = dp[i - 1][j]
        dp[i][j] = min(take, dismiss)


result = dp[-1]
for j in reversed(range(max_value + 1)):
    if result[j] <= w:
        print(j)
        break

Submission status: Accepted

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

w = [0]
v = [0]

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

dp = [[float('inf') for a in range(110000)] for b in range(N+1)]
dp[0][0] = 0

ans = 0

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

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

        if dp[i][j] <= W and j > ans:
            ans = j

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N,W=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(N)]
vmax=sum([v for w,v in a])
INF=float("inf")
dp=np.full(vmax+1,INF)
dp[0]=0

for i in range(N):
    w,v=a[i]
    dp[v:]=np.minimum(dp[v:],dp[:-v]+w)
print(max([i for i in range(vmax+1) if dp[i]<=W]))
# print(dp)

Submission status: Accepted

Solution code:
import numpy as np

N, W = map(int, input().split())
a = [list(map(int,input().split())) for _ in range(N)]
vmax = sum([a[i][1] for i in range(N)])
INF = float('inf')
dp = np.full(vmax+1, INF)
dp[0] = 0

for i in range(N):
  w, v = a[i-1]
  dp[v:] = np.minimum(dp[v:], dp[:-v]+w)
print(max([i for i in range(vmax+1) if dp[i] <= W]))

Submission status: Accepted

Solution code:
import numpy as np
def main():
    N,W = map(int,input().split())
    w,v = [],[]
    for _ in range(N):
        w_,v_ = map(int,input().split())
        w.append(w_)
        v.append(v_)

    Vmax = max(v)*N
    INF = 10**9

    dp = np.ones((N+1,Vmax+1),dtype=np.int64)*INF
    dp[0][0]=0

    for i in range(N):
        tmp = np.ones(Vmax+1,dtype=int)*INF
        if i==0:tmp[0]=0
        tmp[v[i]:] = dp[i][:-v[i]] + w[i]
        dp[i+1] = np.minimum(dp[i],tmp)

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

Submission status: Accepted

Solution code:
# E.Knapsack2 → numpy spped up
import numpy as np
N,W = map(int,input().split())
w,v = [],[]
for _ in range(N):
    w_,v_ = map(int,input().split())
    w.append(w_)
    v.append(v_)
    
Vmax = max(v)*N
INF = 10**9
            
dp = np.ones((N+1,Vmax+1),dtype=np.int64)*INF
dp[0][0]=0

for i in range(N):
    tmp = np.ones(Vmax+1,dtype=int)*INF
    tmp[v[i]:] = dp[i][:-v[i]] + w[i]
    dp[i+1] = np.minimum(dp[i],tmp)

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

Submission status: Accepted

Solution code:
import math
N,W=map(int,input().split())
dp=[[math.inf for _ in range(100001)] for _ in range(N+1)]
#print(dp[-1][100000])
dp[0][0]=0
def min_(a,b):
  if a<b:
    return a
  else:
    return b
  
def nap():
  for i in range(N):
    w,v=map(int,input().split())
    for j in range(100001):
      if j-v>=0:
        #print(dp[i-1][j-w[i]])
        dp[i+1][j]=min(dp[i+1][j],dp[i][j-v]+w)
      dp[i+1][j]=min(dp[i+1][j],dp[i][j])
  ans=100000
  #print(dp[0][:4])
  while dp[-1][ans]>W:
    ans-=1
  print(ans)

nap()

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
w_list, v_list = [], []
for _ in range(N):
    w, v = map(int, input().split())
    w_list.append(w)
    v_list.append(v)
sum_v = sum(v_list)+1

dp = [[float('INF')]*(sum_v) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    w, v = w_list[i], v_list[i]
    for j in range(sum_v):
        if v<=j: dp[i+1][j] = min(dp[i][j], dp[i][j-v]+w)
        else: dp[i+1][j] = dp[i][j]
for i in range(sum_v-1, -1, -1):
    if dp[-1][i] <= W:
        print(i)
        break

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
"""
n, k = [int(i) for i in input().split(' ')]

arr = [int(i) for i in input().split(' ')]

dp = [10**10]*n

k += 1
dp[0] = 0

for i in range(0, n):
    for j in range(1, k):
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i] + abs(arr[i+j]-arr[i]))

print(dp[n-1])
n = int(input())

a = [int(i) for i in input().split(' ')]

for i in range(1, n):
    new_a = [int(i) for i in input().split(' ')]
    new_a[0] = max(new_a[0]+a[1], new_a[0]+a[2])
    new_a[1] = max(new_a[1]+a[0], new_a[1]+a[2])
    new_a[2] = max(new_a[2]+a[1], new_a[2]+a[0])
    a, new_a = new_a, a

print(max(a))
"""

n, W = [int(i) for i in input().split(' ')]

dp = [10**9+7]*(10**5+1)
dp[0] = 0
for _ in range(n):
    curwt, val = [int(i) for i in input().split(' ')]
    for v in range((10**5) - val, -1, -1):
        dp[v+val] = min(dp[v+val], dp[v]+curwt)

ans = 0
for i, val in enumerate(dp):
    if val <= W:
        ans = max(i, ans)

print(ans)

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
INF=float('inf')
P=[]
for _ in range(n):
  iw,iv=map(int,input().split())
  P.append([iw,iv])

dp=[[INF for i in range(10**5+1)] for j in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
  for j in range(10**5+1):
    if j-P[i-1][1]>=0:
      dp[i][j]=min(dp[i-1][j],dp[i-1][j-P[i-1][1]]+P[i-1][0])
    else:
      dp[i][j]=dp[i-1][j]
      
ans=10**5
while dp[n][ans]>w:
  ans-=1
print(ans)

Submission status: Accepted

Solution code:
n,w = map(int,input().split())
v = [0]*n
for i in range(n):
    v[i] = list(map(int,input().split()))
    
dp = [[float("Inf") for j in range(1000*n+1)] for i in range(n+1)]

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

for i,[W,V] in enumerate(v):
    for j in range(1000*n):
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])
        if dp[i][j] + W <= w:
            dp[i+1][j+V] = min(dp[i+1][j+V], dp[i][j] + W)
ans = 0
for i in range(1, n+1):
    for j in range(1000*n+1):
        if dp[i][j] <= w:
            ans = max(ans, j)
print(ans)

Submission status: Accepted

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

weight=[]
value=[]
for i in range(n):
  a,b=map(int,input().split())
  weight.append(a)
  value.append(b)

xxx=sum(value)
dp=[[float('inf')]*(sum(value)+1) for i in range(n+1)]
dp[0][0]=0

for i in range(n):
  for j in range(xxx+1):
    dp[i+1][j]=min(dp[i+1][j],dp[i][j])                             #+1、個数制限なし
    dp[i+1][min(j+value[i],xxx)]=min(dp[i+1][min(j+value[i],xxx)],dp[i][j]+weight[i])

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

print(ans)

Submission status: Accepted

Solution code:
from pprint import pprint

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

lim = 1
for i in range(n):
    lim += wv[i][1]

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

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

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

Submission status: Accepted

Solution code:
from pprint import pprint

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

lim = 1
for i in range(n):
    lim += wv[i][1]

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

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

ans = float('inf')

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

Submission status: Accepted

Solution code:
import numpy as np
[N,W]=[int(x) for x in input().split()]
wv=[[int(x) for x in input().split()] for i in range(N)]

dp=np.array([[10**10]*(10**5+1) for i in range(N)])

dp[0][wv[0][1]]=wv[0][0]
dp[0][0]=0

for i in range(1,N):
  last=10**5-wv[i][1]+2
  dp[i][wv[i][1]:]=np.minimum(dp[i-1][wv[i][1]:],dp[i-1][:last-1]+wv[i][0])
  dp[i][:wv[i][1]]=dp[i-1][:wv[i][1]]
ans=0
count=10**5
while(ans==0):
  if dp[N-1][count]<=W:
    ans=count
    break
  else:
    count=count-1
print(ans)

Submission status: Accepted

Solution code:
# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")


# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input


def out(var): sys.stdout.write(str(var))  # for fast output, always take string


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  # as stdout.write always print sring.


def testcase(t):
    for p in range(t):
        solve()


from random import randint

from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count



def ifvalid(i):
    if i<0:
        return False
    return True


def solve():
    n,W=sep()
    ar=[]
    for _ in range(n):
        ar.append(lis())
    inf=10**10
    dp=[[inf for i in range(100005)] for _ in range(n+5)]
    dp[0][ar[0][1]]=ar[0][0]
    for i in range(n):
        dp[i][0]=0
    ans=0
    if ar[0][0]<=W:
        ans=ar[0][1]
    for i in range(1,n):
        for v in range(1,100005):
            if ifvalid(v-ar[i][1]):
                dp[i][v]=min(dp[i-1][v],dp[i-1][v-ar[i][1]]+ar[i][0])
            else:
                dp[i][v]=dp[i-1][v]
            if dp[i][v]<=W:
                ans=max(v,ans)
    print(ans)








solve()