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:
# D問題とほぼ同じだが計算量が問題になる．
# 前回と違い重さの制約が，W<10^9なので，重さのノードを作ってしまうと，計算量がどう仕様もなくなる
# なので，価値に対してノードを作ってあげて，最小の重さを計算するようにする

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

W = []
V = []

for i in range(N):
    w,v = map(int,input().split())
    W.append(w)
    V.append(v)
# dp[v][i] := 商品iまで選択して，価値がv以下となった場合について，最小の重さ
import math
import numpy as np
dp = np.ones((10**3*(N+10))) * np.inf
dp[0] = 0
for v,w in zip(V,W):
    np.minimum(dp[:-v]+w, dp[v:],out=dp[v:])
print(np.where(dp<=W_max)[0][-1])

Submission status: Accepted

Solution code:
#dp[i][j] denotes min weight if possible to obtain value j from first i items
l=input().split()
n=int(l[0])
W=int(l[1])
lweight=[]
lvalue=[]
for i in range(n):
	l=input().split()
	u=int(l[0])
	v=int(l[1])
	lweight.append(u)
	lvalue.append(v)
k=sum(lvalue)
dp=[[-1 for i in range(k+1)] for i 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,k+1):
		if(dp[i-1][j]>-1):
			dp[i][j]=dp[i-1][j]
			if(j>=lvalue[i-1] and dp[i-1][j-lvalue[i-1]]!=-1):
				dp[i][j]=min(dp[i][j],dp[i-1][j-lvalue[i-1]]+lweight[i-1])
		elif(j>=lvalue[i-1] and dp[i-1][j-lvalue[i-1]]!=-1):
			dp[i][j]=dp[i-1][j-lvalue[i-1]]+lweight[i-1]
		else:
			dp[i][j]=-1
maxa=0
for i in range(n+1):
	for j in range(k+1):
		if(dp[i][j]!=-1 and dp[i][j]<=W):
			if(j>maxa):
				maxa=j
print(maxa)

Submission status: Accepted

Solution code:
import numpy as np
N,W = map(int,input().split())
V = 1000 * N + 1
dp = np.full(V,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 = 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 = [[10**100]* (V + 1) for _ in range(N+1)]

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

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

print(ans)

Submission status: Accepted

Solution code:
n,w=[int(k) for k in input().split()]
li=[]
 
 
ans=0
for i in range(n):
    li.append([int(k) for k in input().split()])
dp=[[0 for i in range(100001)] for j in range(n+1)]
for i in range(1,100001):
    dp[0][i]=10**10
dp[0][0]=0    
for a in range(1,n+1):
    for b in range(1,100001):
        if(li[a-1][1]<=b):
            x=li[a-1][0]+dp[a-1][b-li[a-1][1]]
            y=dp[a-1][b]
            dp[a][b]=min(x,y)
        else:
            dp[a][b]=dp[a-1][b]
        if dp[a][b]<=w:
          ans=max(ans,b)
 
 
print(ans)

Submission status: Accepted

Solution code:
n,w=[int(k) for k in input().split()]
li=[]
 
 
ans=0
for i in range(n):
    li.append([int(k) for k in input().split()])
dp=[[0 for i in range(100001)] for j in range(n+1)]
for i in range(1,100001):
    dp[0][i]=10**10
dp[0][0]=0    
for a in range(1,n+1):
    for b in range(0,100001):
        if(li[a-1][1]<=b):
            x=li[a-1][0]+dp[a-1][b-li[a-1][1]]
            y=dp[a-1][b]
            dp[a][b]=min(x,y)
        else:
            dp[a][b]=dp[a-1][b]
        if dp[a][b]<=w:
          ans=max(ans,b)
 
 
print(ans)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
wv = []
a = 0
for i in range(N):
    w,v = map(int,input().split())
    a = max(v,a)
    wv.append((w,v))
A = N*a
inf = 10**15
dp = [[inf]*(A+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    for v in range(A+1):
        if v-wv[i-1][1]>=0:
            dp[i][v] = min(dp[i-1][v-wv[i-1][1]]+wv[i-1][0],dp[i-1][v])

        else:
            dp[i][v] = dp[i-1][v]

ans = 0

for j in reversed(range(A+1)):
    if dp[N][j]<=W:
        ans = j
        break
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, W = map(int, input().split())
    dp = [INF] * (n * 1001 + 1)
    dp[0] = 0
    for _ in range(n):
        w, v = map(int, input().split())
        for v0 in range(n * 1001, -1, -1):
            if dp[v0] == INF:
                continue
            if v + v0 <= n * 1001:
                dp[v + v0] = min(dp[v + v0], dp[v0] + w)
    for v in range(n * 1001, -1, -1):
        if dp[v] <= W:
            print(v)
            return
resolve()

Submission status: Accepted

Solution code:
import numpy
N, W = map(int, input().split())
memo = numpy.array([[10**9+1 for i in range(10**5+1)] for j in range(N)])
memo[-1][0] = 0
for n in range(N):
    w, v = map(int, input().split())
    memo[n][:v] = memo[n-1][:v]
    memo[n][v:] = numpy.fmin(memo[n-1][v:], memo[n-1][:-v]+w)
a = numpy.where(memo[-1] <= W)
print(numpy.max(a[0]))

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

def resolve():
    return 

N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range (N)]
INF = 10**10
VMAX = N * 10**3 + 10
dp = [[INF]*(VMAX) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(VMAX):
        if j>=wv[i][1]:
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]] + wv[i][0])
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j])

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

print(ans)

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
V, W = [], []
for i in range(n):
    wi, vi = map(int, input().split())
    W.append(wi)
    V.append(vi)
    
max_sumv = sum(V) 
# dp[i][sum_v] := i-1 番目までの品物から価値がsum_v以上を達成するように選んだときの、重さの総和の最小値   
dp = [[10 ** 9] * (max_sumv + 1) for _ in range(n+1)]

dp[0][0] = 0
for i in range(n):
    for sum_v in range(max_sumv + 1):
        #i番目の商品を選ぶ場合
        if sum_v - V[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - V[i]] + W[i])
        #i番目の商品を選ばない場合
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])
ans = 0
for i in range(max_sumv + 1):
    if dp[n][i] <= w:
        ans = i
print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
X = [list(map(int, input().split())) for i in range(N)]
DP=[[float("inf")]*(N*10**3+1) for i in range(N+1)]
DP[0][0] = 0
for i in range(1, N+1):
    for j in range(N*10**3+1):
        if j-X[i-1][1] >= 0:
            DP[i][j]=min(DP[i-1][j], DP[i-1][j-X[i-1][1]]+X[i-1][0])
        else:
            DP[i][j] = DP[i-1][j]
ans = 0
for i in range(N+1):
    for j in range(N*10**3+1):
        if DP[i][j] <= W:
            ans = max(ans, j)
print(ans)

Submission status: Accepted

Solution code:
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
V = N*10**3
dp = [[float('INF')]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    w,v = wv[i-1]
    for j in range(V+1):
        if j-v>=0 and dp[i-1][j-v]+w<=W:
            dp[i][j] = min(dp[i][j],dp[i-1][j-v]+w)
        dp[i][j] = min(dp[i][j],dp[i-1][j])
print(max([i for i in range(V+1) if dp[-1][i]<=W]))

Submission status: Accepted

Solution code:
import itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
V = 10**5
dp = [[float('INF')]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i,j in itertools.product(range(1,N+1),range(V+1)):
    w,v = wv[i-1]
    if j-v>=0 and dp[i-1][j-v]+w<=W:
        dp[i][j] = min(dp[i][j],dp[i-1][j-v]+w)
    dp[i][j] = min(dp[i][j],dp[i-1][j])
print(max([i for i in range(V+1) if dp[-1][i]<=W]))

Submission status: Accepted

Solution code:
import itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
V = N*10**3
dp = [[float('INF')]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i,j in itertools.product(range(1,N+1),range(V+1)):
    w,v = wv[i-1]
    if j-v>=0 and dp[i-1][j-v]+w<=W:
        dp[i][j] = min(dp[i][j],dp[i-1][j-v]+w)
    dp[i][j] = min(dp[i][j],dp[i-1][j])
print(max([i for i in range(V+1) if dp[-1][i]<=W]))

Submission status: Accepted

Solution code:
import itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
V = N*10**3
dp = [[float('INF')]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i,j in itertools.product(range(1,N+1),range(V+1)):
    w,v = wv[i-1]
    if j-v>=0 and dp[i-1][j-v]+w<=W:
        dp[i][j] = min(dp[i][j],dp[i-1][j-v]+w)
    dp[i][j] = min(dp[i][j],dp[i-1][j])
for k in range(V+1)[::-1]:
    if dp[-1][k]<=W:
        print(k)
        break

Submission status: Accepted

Solution code:
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
V = N*10**3
dp = [[float('INF')]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    w,v = LI()
    for j in range(V+1):
        if j-v>=0:
            dp[i][j] = min(dp[i][j],dp[i-1][j-v]+w)
        dp[i][j] = min(dp[i][j],dp[i-1][j])
print(max([i for i in range(V+1) if dp[-1][i]<=W]))

Submission status: Accepted

Solution code:
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
V = N*10**3
dp = [[float('INF')]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    w,v = wv[i-1]
    for j in range(V+1):
        if j-v>=0:
            dp[i][j] = min(dp[i][j],dp[i-1][j-v]+w)
        dp[i][j] = min(dp[i][j],dp[i-1][j])
print(max([i for i in range(V+1) if dp[-1][i]<=W]))

Submission status: Accepted

Solution code:
import itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
V = N*10**3
dp = [[float('INF')]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i,j in itertools.product(range(1,N+1),range(V+1)):
    w,v = wv[i-1]
    if j-v>=0:
        dp[i][j] = min(dp[i][j],dp[i-1][j-v]+w)
    dp[i][j] = min(dp[i][j],dp[i-1][j])
ans = 0
for k in range(V+1):
    if dp[-1][k]<=W:
        ans = max(ans,k)
print(ans)

Submission status: Accepted

Solution code:
import itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
V = N*10**3
dp = [[float('INF')]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i,j in itertools.product(range(1,N+1),range(V+1)):
    w,v = wv[i-1]
    if j-v>=0:
        dp[i][j] = min(dp[i][j],dp[i-1][j-v]+w)
    dp[i][j] = min(dp[i][j],dp[i-1][j])
print(max([i for i in range(V+1) if dp[-1][i]<=W]))

Submission status: Accepted

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

for i in range(N):
    w, v = map(int, input().split())
    wv.append([w, v])
MAX_V = 10**5+100
INF = 10**10
dp = [[INF]*MAX_V for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(MAX_V):
        if j - wv[i][1] >= 0:
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]]+wv[i][0])
        else:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
ans = 0
for i in range(MAX_V):
    if dp[N][i] <= W:
        ans = i
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, W = map(int, input().split())
    goods = [list(map(int, input().split())) for _ in range(n)]
    
    max_value = 1
    for i in range(n):
        max_value += goods[i][1]

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

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

    res = 0
    for k in range(max_value):
        if dp[-1][k] <= W:
            res = k

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, W = map(int, input().split())
    goods = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[1])
    max_value = 1
    for i in range(n):
        max_value += goods[i][1]

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

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

    res = 0
    for k in range(max_value):
        if dp[-1][k] <= W:
            res = k

    print(res)


if __name__ == '__main__':
    resolve()

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 = [[10**100]* (V + 1) for _ in range(N+1)]
#dp[i][j]: i番目までの品物から価値が j以上になるように
#選んだときの持ち帰る品物の重さの総和の最小値
dp[0][0] = 0
for i in range(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())

dp = [float("INF")]*(N*10**3 + 1)
dp = np.array(dp)
dp[0] = 0

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
def main():
    N,W = map(int, input().split())
    w,v = [0]*N,[0]*N
    for i in range(N):
        w[i],v[i] = map(int, input().split())
    # dp[i][w] := 容量をwとして荷物0~iの中から荷物を選んだ時の価値の最大値
    # ではなく...
    # dp[i][v] := 荷物0~iの中から荷物を選んで価値vを超える時の重さ合計の最小値
    # 初期値dp[0][v] = 0の重さ(もし0の価値がvを超えないならINF)
    V = N*max(v)
    INF = float('inf')
    dp = [[INF]*(V+1) for i in range(N)]
    for x in range(V+1):
        dp[0][x] = INF if x>v[0] else w[0]
    dp[0][0] = 0
    for i in range(N-1):
        for j in range(V+1):
            if j>=v[i+1]:
                # i+1番目を選ぶ
                dp[i+1][j] = min(dp[i+1][j], (dp[i][j-v[i+1]])+w[i+1])
            # i+1番目を選ばない
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])

    # dp[N-1]のうちW以下であるものの価値の最大値
    for val in range(V,-1,-1):
        if dp[-1][val]<=W:
            print(val)
            break
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, W = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    vmax=N*1000
    inf=10**10
    dp=[inf]*(vmax+1)
    dp[0]=0
    for i in range(N):
        w,v=S[i]
        j=vmax
        while j-v>=0:
            dp[j]=min(dp[j-v]+w,dp[j])
            j-=1
    ans=0
    for i, val in enumerate(dp):
        if val<=W:
            ans=i
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, W = map(int,input().split())
wv = [list(map(int,input().split())) for i in range(n)]
inf = 10 ** 10
dp = [[inf] * (1000 * n + 1) for i in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    for j in range(1000 * n + 1):
        if dp[i][j] == inf:continue
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

        w, v = wv[i]
        if dp[i][j] + w <= W:
            dp[i + 1][j + v] = min(dp[i + 1][j + v], dp[i][j] + w)

for i in range(1000 * n + 1):
    if dp[-1][-(i + 1)] != inf:
        print(1000 * n - i)
        exit()

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
from sys import stdin, stdout
from collections import deque, defaultdict
import math as m

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	n, W = rli()
	items = []
	maxval = 0
	for _ in range(n):
		w, v = rli()
		maxval += v
		items.append((w, v))

	dp = [INF for _ in range(maxval + 1)]
	dp[0] = 0
	for w, v in items:
		for i in range(maxval, -1, -1):
			if i - v >= 0:
				dp[i] = min(dp[i], dp[i-v] + w)
	ans = NINF
	for val, minweight in enumerate(dp):
		if minweight <= W:
			ans = val
	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
sumv=0
v,w=[],[]
m=10**9
for i in range(n):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
    sumv+=b
dp=[m]*(sumv+1)
dp[0]=0
for i in range(n):
    for j in range(sumv,v[i]-1,-1):
        dp[j]=min(dp[j],dp[j-v[i]]+w[i])
ans=0

for i in range(sumv+1):
    if dp[i]<=W:
        ans=i 
# print(dp)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import bisect
N,W= map(int,input().split())
ans= [[float('inf') for e in range(10**5+1)] for f in range(N+1)]
for i in range(N):
 w,v=map(int,input().split())
 for j in range(0,v):
  ans[i+1][j]=min(ans[i][j],w)
 for j in range(v,10**5+1):
  ans[i+1][j]=min(ans[i][j],ans[i][j-v]+w)
print(bisect.bisect(ans[N],W))

Submission status: Accepted

Solution code:
import sys

n,c = list(map(int, input().split()))
W=[]
P=[]
for _ in range(n):
    w,val = list(map(int, input().split()))
    W.append(w)
    P.append(val)
maxV = sum(P)
dp=[]
for i in range(n+1):
    dp.append([sys.maxsize]*(maxV+1))
for i in range(n+1):
    dp[i][0]=0
for i in range(1,n+1):
    for j in range(1,maxV+1):
        inc=sys.maxsize
        exc=sys.maxsize
        if j-P[i-1]>=0:
            inc=W[i-1]+dp[i-1][j-P[i-1]]
        exc=dp[i-1][j]
        dp[i][j]=min(inc,exc)
ans=0
for i in range(1,maxV+1):
    if dp[n][i]<=c:
        ans=i
print(ans)

Submission status: Accepted

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

dp = np.full(N*10**3+1,Max_W+1,dtype=np.int64)
dp[0] = 0
for i in range(N):
    w,v = map(int,input().split())
    a = dp[:-v] + w
    b = dp[v:]
    m = np.minimum(a,b)
    dp[v:] = m
max_w = 0
max_v = 0
ans = np.where( dp <= Max_W )
print(np.max(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)

#w_list.insert(0,0)#アイテム番号を1インデックスに変更.
#v_list.insert(0,0)#アイテム番号を1インデックスに変更.

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

#print(dp)

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


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

print(ans)

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,W=LI()
  dp=[[inf]*100100 for _ in range(n+1)]
  dp[0][0]=0

  w=[]
  v=[]
  for _ in range(n):
    a,b=LI()
    w.append(a)
    v.append(b)

  for i in range(n):
    for j in range(100100):
      dp[i+1][j]=min(dp[i+1][j],dp[i][j])

      if j+v[i]<100100:
        dp[i+1][j+v[i]]=min(dp[i+1][j+v[i]],dp[i][j]+w[i])

  ans=0
  for i in range(100100):
    x=dp[n][i]
    if x<=W:
      ans=i

  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
N, W= map(int, input().split())
inf1 = 10**9+10
inf = 10**5+10
dp = [inf1]*inf

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

print(j)

Submission status: Accepted

Solution code:
import numpy as np
MaxW=int(1e5)
N,W=map(int,input().split())
WV=[]
for i in range(N):
    WV.append(list(map(int,input().split())))
dp=[1e30 for i in range(MaxW+1)]
dp[0]=0
dp=np.array(dp)
for i in range(N):
    dp[WV[i][1]:]=np.minimum(dp[WV[i][1]:],dp[:MaxW-WV[i][1]+1]+WV[i][0])
for i in reversed(range(MaxW+1)):
    if dp[i]<=W:
        print(i)
        break

Submission status: Accepted

Solution code:
a= input().split()
N = int(a[0])
W = int(a[1])
wv_list = []
max_value = 0

#価値と重さのやつをリストにしてる
for i in range(N):
  b = input().split()
  w = int(b[0])
  v = int(b[1])
  max_value += v

  wv_list.append([w, v])

#初期化
#とりあえず、全部最大になるように
inf=float('inf')
n_list = [[inf for i in range(max_value + 1)] for j in range(N)]

#最初のアイテムに関して、重みを適切な価値のところにいれている
n_list[0][wv_list[0][1]] = wv_list[0][0]

for i in range(1, N):
  # 今まで全く選んでなかった場合に、i番目のアイテムを選んだ時
  n_list[i][wv_list[i][1]] = wv_list[i][0]
  for j in range(max_value):

    s = j + wv_list[i][1]
    #アイテムを選んだらこうなりますよってのを更新
    if s <= max_value:
      n_list[i][s] = min(n_list[i - 1][j] + wv_list[i][0], n_list[i][s])

    #選ばんかったらこうなりますよってのを更新？
    n_list[i][j] = min(n_list[i - 1][j], n_list[i][j])
  
for i in range(1, max_value):

  if n_list[-1][-i] <= W:
    print(max_value - i + 1)
    break

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,weight=map(int,input().split())
    WV=[tuple(map(int,input().split())) for i in range(n)]
    dp=[[10**10]*(10**5+1) for _ in range(n+1)] #i番目までの品物について，価値の総和がjのときのナップザックの重さ
    dp[0][0]=0
    for i in range(n):
        ni=i+1
        w,v=WV[ni-1]
        for j in range(10**5+1):
            if dp[i][j]+w<=weight and (j==0 or dp[i][j]!=10**10):
                dp[ni][j+v]=min(dp[ni][j+v],dp[i][j]+w)
            dp[ni][j]=min(dp[i][j],dp[ni][j])
    for i in range(10**5,-1,-1):
        if dp[-1][i]!=10**10:
            print(i)
            break

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n,w = map(int,input().split())
v = 10**5
dp = [[n*w+1]*(v+1) for i in range(n)]
ans = 0
for i in range(n):
    W,V = map(int,input().split())
    if i == 0:
        for j in range(v+1):
            if j <= V:
                dp[0][j] = W
    else:
        for j in range(v+1):
            if 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)
kouho = dp[-1]
for i in range(v+1):
    if kouho[i] <= w:
        ans = i
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from collections import defaultdict as dd
n,w=map(int,input().split())
maxn=10000000000000000
we=[0]*n
val=[0]*n
su=0
for i in range(n):
    ww,v=map(int,input().split())
    we[i]=ww
    val[i]=v
    su+=v
dp=[maxn]*(su+1)
dp[0]=0
for i in range(n):
    for j in range(su-val[i],-1,-1):
        dp[j+val[i]]=min(dp[j+val[i]],we[i]+dp[j])
ans=0
for i in range(len(dp)):
    if(dp[i]<=w):
        ans=max(ans,i)
print(ans)

Submission status: Accepted

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

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

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

#print("---")
for i in range(sum(v)+1):
#  print("w=",dp[N][i],"v=",i)
  if dp[N][i]>W: continue
  res=i

print(res)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = lambda: sys.stdin.buffer.readline().rstrip()
    n, w_max = map(int, input().split())
    import numpy as np

    v,w = [],[]
    for i in range(n):
        w_, v_ = map(int, input().split())
        v.append(v_)
        w.append(w_)
    dp = np.array([10**10]*(10**5+1),dtype=int)
    dp[0] = 0
    for i in range(n):
        dp[v[i]:] = np.minimum(dp[v[i]:], w[i]+dp[:-v[i]])
    ans = 0
    for i,w in enumerate(dp):
        if w<= w_max:
            ans = i
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def chmin(a,b):
    if a >= b:
        return b
    else:
        return a
    
V = sum(value)
inf = float('inf')
dp = [[inf]*(V+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for v in range(V+1):
        dp[i+1][v] = dp[i][v]
        
        if v >= value[i]:
            dp[i+1][v] = chmin(dp[i][v - value[i]] + weight[i], dp[i][v])
for v in range(V+1):
    if dp[N][v] <=W:
        res = v
print(res)

Submission status: Accepted

Solution code:
def main():
    n,wmax = map(int,input().split())
    wv = [list(map(int,input().split())) for _ in range(n)]

    # min -> inf, max -> -1
    inf = 10**18
    vmax = sum(list(zip(*wv))[1])
    dp = [[inf]*(vmax+1) for _ in range(n+1)]

    # shoki joken
    dp[0][0] = 0
    for i in range(n):
        w,v = wv[i]
        for j in range(vmax+1):
            # i select or not select
            if j-v >= 0:
                dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)
            else:
                dp[i+1][j] = dp[i][j]

    res = 0
    for i in range(vmax+1):
        if wmax >= dp[-1][i]:
            res = max(res,i)
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

dp=[[W+1 for _ in range(10**5+1)] for _ in range(N+1)]
w,v=map(int,input().split())
dp[1][v]=w
dp[1][0]=0
for i in range(1,N):
    w,v=map(int,input().split())
    for j in range(10**5+1):
        dp[i+1][j]=min(dp[i][j],dp[i+1][j])
        if j+v<=10**5:
            dp[i+1][j+v]=min(dp[i][j+v],dp[i][j]+w)
out=0
for i in range(10**5+1):
    if dp[N][i]<=W:
        out=i
print(out)

Submission status: Accepted

Solution code:
import  numpy as np

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

INF = 1e100

dp = [INF] * (10 ** 5 + 1)
dp = np.array(dp)

dp[0] = 0

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


for v,num in enumerate(dp):
    if num <= W:
        ans = v

print(ans)

Submission status: Accepted

Solution code:
# region header
import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
from string import ascii_lowercase, ascii_uppercase, digits
sys.setrecursionlimit(10**6)
INF = float('inf')
MOD = 10 ** 9 + 7
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rf(): return float(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]
def rf_(): return [float(_) for _ in rs().split()]
def divisors(n, sortedresult=True):
    div = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.append(i)
            if i != n // i:
                div.append(n//i)
    if sortedresult:
        div.sort()
    return div
# endregion
N, W = ri_()
w, v = [0] * N, [0] * N
for i in range(N):
    w[i], v[i] = ri_()
dp = [[INF] * (N * (10 ** 3) + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for j in range(N * (10 ** 3) + 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]
ans = 0
for j in range(N * (10 ** 3) + 1):
    if dp[N][j] <= W:
        ans = max(ans, j)
print(ans)