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:
N, W = (int(x) for x in input().split())
weights = []
values = []
for _ in range(N):
  w, v = (int(x) for x in input().split())
  weights.append(w)
  values.append(v)

sumValues = sum(values)
dp = [float('inf')] * (sumValues + 1) # Minimum weight at value v.
dp[0] = 0
for item in range(N):
  for value in range(sumValues-values[item], -1, -1):
    dp[value+values[item]] = min(dp[value+values[item]], dp[value]+weights[item])

res = 0
for i in range(sumValues+1):
  if dp[i] <= W:
    res = max(res, i)
print(res)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


def sub(w, v, b):
    """重みリストw, 価値リストv, 重さ上限bのナップサックを解く
    ※ 価値で回すパターン
    """
    sv = sum(v)
    n = len(w)
    dp = [float("inf")] * (sv+1) # iの価値を作るのに必要な重さの最小値
    dp[0] = 0
    for i in range(n):
        for j in range(sv, -1, -1):
            if j>=v[i]:
                dp[j] = min(dp[j], dp[j-v[i]]+w[i])
    return dp
n,w = map(int, input().split())
ws = [None]*n
vs = [None]*n
for i in range(n):
    ws[i], vs[i] = map(int, input().split())
dp = sub(ws, vs, w)
ans = 0
for i,item in enumerate(dp):
    if item<=w:
        ans = i
print(ans)

Submission status: Accepted

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

import numpy as np
import math

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

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

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

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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 = np.full(10**5 + 1, W + 1, dtype=np.int64)
dp[0] = 0

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

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

Submission status: Accepted

Solution code:
#!python3

LI = lambda: list(map(int, input().split()))

# input
N, W = LI()
WV = [LI() for _ in range(N)]

INF = 10 ** 10
MAX = 10 ** 5


def main():
    dp = [[INF] * (MAX + 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(MAX + 1):
            if j < v:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v] + w)
    for i in range(MAX, -1, -1):
        if dp[-1][i] <= W:
            print(i)
            return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np

N, W = map(int, input().split())
dp = np.ones(int(1e5+1)) * np.inf
dp[0] = 0
total = 0
for i in range(N):
    w, v = map(int, input().split())
    dp[v:total+v+1] = np.minimum(dp[v:total+v+1], dp[:total+1] + w)
    total += v

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
INF = 10 ** 9 + 5
V = 10 ** 5 + 5
dp = [[INF] * V for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V):
        w = wv[i][0]
        v = wv[i][1]
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        if j - v >= 0:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v] + w)

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

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, lim = map(int, readline().split())
WV = np.array(read().split(), np.int64)

W = WV[::2]
V = WV[1::2]

# value sum -> min weight
INF = 10**18
dp = np.full(V.sum() + 1, INF, np.int64)
dp[0] = 0
for w, v in zip(W, V):
    np.minimum(dp[v:], dp[:-v] + w, out=dp[v:])

answer = np.where(dp <= lim)[0].max()
print(answer)

Submission status: Accepted

Solution code:
import numpy as np
n, targw = map(int,input().split())
w = [0 for _ in range(n)]
v = [0 for _ in range(n)]
for i in range(n):
	w[i], v[i] = map(int,input().split())
"""
定義
dp[i] := v == i のときのwが最小なるもの.
"""
dp = np.full(100001, targw+1, dtype=np.int64)
dp[0] = 0
for i in range(n):
	dp[v[i]:] = np.minimum(dp[:-v[i]]+w[i], dp[v[i]:])
print(np.where(dp <= targw)[0][-1])

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],v[i] = map(int,input().split())
maxi=sum(v)
    
dp=[[float("inf") for _ in range(N+1)] for _ in range(maxi+1)]
for _ in range(N+1):
    dp[0][_]=0
    
last=0
for i in range(1,N+1):
    for j in range(1,maxi+1):
        if j<v[i-1]:
            dp[j][i]=min(w[i-1], dp[j][i-1])
        else:
            tmp=w[i-1]+dp[j-v[i-1]][i-1]
            if tmp<=W:
                dp[j][i]=min(tmp, dp[j][i-1])
            else:
                dp[j][i]=dp[j][i-1]

#print(dp)
for j in range(maxi,-1,-1):
    if dp[j][-1]!=float("inf"):
        k=j
        break

ans=0
for i in range(N,0,-1):
    if dp[k][i]==dp[k-v[i-1]][i-1]+w[i-1]:
        k = k-v[i-1]
        ans += v[i-1]
print(ans)

Submission status: Accepted

Solution code:
inf=10**10
def knapsackBottomUp(wt,price,c,n,m):
    dp=[[inf for x in range(m+1)] for y in range(n+1)]
    for l in range(n+1):
        dp[l][0]=0


    for i in range(1,n+1):
        wi=wt[i];vi=price[i]
        for V in range(1,m+1):
            if vi <= V:
                dp[i][V]=min(wi+dp[i-1][V-vi],dp[i-1][V])
            else:
                dp[i][V]=dp[i-1][V]

    res=0
    for i in range(m+1):
        if dp[n][i]<=c:
            res=i
    print(res)
n,c=map(int,input().split())
wt=[]
price=[]
wt.append(0)
price.append(0)
for _ in range(n):
    w,v=map(int,input().split())
    wt.append(w)
    price.append(v)
max_val=sum(price)
knapsackBottomUp(wt,price,c,n,max_val)

Submission status: Accepted

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

lw=w
totval=0
wei=[]
val=[]
for test in range(n):
    cw, v = [int(x) for x in input().split()]
    wei.append(cw)
    val.append(v)
    totval+=v

dp=[float('inf')]*(totval+1)
dp[0]=0
for item in range(n):
    for j in range(totval,val[item]-1,-1):
        dp[j]=min(dp[j-val[item]]+wei[item],dp[j])
    #print(dp)
ans=0
for i in range(totval+1):
    if dp[i] <=w:
        ans=i
print(ans)

Submission status: Accepted

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

Wl=[]
Vl=[]
for i in range(N):
  w,v=map(int,input().split())
  Wl.append(w)
  Vl.append(v)
V=max(Vl)
dp=[ [10**20]*((V+1)*(N+1)) for i in range(N+1) ]
dp[0][0]=0
#print(dp)
for i in range(1,N+1):
  for v in range((V+1)*(N+1)):
    #print(i,w)
    if v>=Vl[i-1]:
      dp[i][v]=min(dp[i-1][v-Vl[i-1]]+Wl[i-1],dp[i-1][v])
    else:
      dp[i][v]=dp[i-1][v]

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

Submission status: Accepted

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

V = sum(v)
Vi=[0] * N
for i in range(N):
    if i==0:
        Vi[i]=v[i]
    else:
        Vi[i]=Vi[i-1]+v[i]

# dp[i][j]:i番目までの品物から価値がj以上になるよう選んだときの重さの総和の最小値
dp = [[float("inf")] * (V + 1) for _ in range(N + 1)]
dp[0][0] = 0

for i in range(N):
    for j in range(Vi[i] + 1):
        # i+1番目を入れる場合vs入れない場合（前の段階から足し合わせることで価値がj以上になる場合）
        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]

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

print(ans)

Submission status: Accepted

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

V = sum(v)
# dp[i][j]:i番目までの品物から価値がj以上になるよう選んだときの重さの総和の最小値
dp = [[float("inf")] * (V + 1) for _ in range(N + 1)]
dp[0][0] = 0

for i in range(N):
    for j in range(V + 1):
        # i+1番目を入れる場合vs入れない場合（前の段階から足し合わせることで価値がj以上になる場合）
        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]

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

print(ans)

Submission status: Accepted

Solution code:
NW = list(map(int, input().split()))
wv = []
for i in range(NW[0]):
    wv.append(list(map(int, input().split())))

dp = [[float("inf")] * 10**3*(NW[0]+1) for i in range(NW[0]+1)]
dp[0][0] = 0
for i in range(len(dp)):
    for sum_v in range(len(dp[i])):
        try:
            if sum_v-wv[i][1]>=0:
                dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v-wv[i][1]] + wv[i][0])
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])
        except:
            continue

for sum_v in range(len(dp[i])):
    if dp[NW[0]][sum_v] <= NW[1]:
        res = sum_v

print(res)

Submission status: Accepted

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

from collections import defaultdict

dp = defaultdict(lambda: float('inf'))

dp[0] = 0

for _ in range(N):
    w, v = map(int, input().split())
    for nv, nw in list(dp.items()):
        if nw + w <= W:
            dp[nv+v] = min(dp[nv+v], nw+w)

print(max(dp))

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)
m = sum(v)
dp=[[float("inf")]*(m+1) for i in range(N+1)]
dp[0][0] = 0

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

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

########################################
# ナップサック
# 重さ：max_wi,Wー10**9くらい
# 価値：N*max_viー10**5くらい
# dp[v]:v以上の価値となる最小の重さ
########################################

import numpy as np

def main():
    N, W = map(int, input().split())
    max_vi = 10**3
    max_V = N*max_vi
    dp = [W+1] * (max_V+1)
    dp[0] = 0
    dp = np.array(dp)
    for _ in range(N):
        w_, v_ = map(int, input().split())
        dp[v_:] = np.minimum(dp[v_:], dp[:-v_] + w_)
#    print(dp)
    print(np.max(np.where(dp <= W)))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
MAX_V = 10**5+1
dp = [float('inf')] * MAX_V
dp[0] = 0
for _ in range(N):
    w, v = map(int, input().split())
    for sum_v in range(MAX_V)[::-1]:
        if sum_v >= v:
            dp[sum_v] = min(dp[sum_v - v] + w, dp[sum_v])
        else:
            dp[sum_v] = min(dp[sum_v], w)
ans = 0
for v in range(MAX_V)[:: -1]:
    if dp[v] <= W:
        ans = v
        break
print(ans)

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
value=[]
wt=[]
for i in range(n):
    a,b=map(int,input().split())
    wt.append(a)
    value.append(b)
dp=[[0 for i in range(sum(value)+1)] for j in range(n+1)]
for i in range(sum(value)+1):
    dp[0][i]=1000000000000
for j in range(n+1):
    dp[j][0]=0
for i in range(1,n+1):
    for j in range(1,sum(value)+1):
        if value[i-1]<=j:
            dp[i][j]=min(wt[i-1]+dp[i-1][j-value[i-1]],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
for i in range(sum(value),-1,-1):
    if dp[-1][i]<=w:
        print(i)
        break

Submission status: Accepted

Solution code:
import numpy as np

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

r = 10 ** 5 + 100
dp = np.array([[0]+[float("inf")]*(r-1)]*(N+1))
for i in range(1, N+1):
    w, v = map(int, input().split())
    dp[i,:v] = dp[i-1,:v]
    dp[i,v:r] = np.minimum(dp[i-1,v:r], dp[i-1,:r-v]+w)
    
print(max(np.where(dp[N]<=W)[0]))

Submission status: Accepted

Solution code:
import numpy as np

N, W = map(int, input().split())
MAX_V = (10**3) * N + 1
INF = 1 << 60

dp = np.full(MAX_V, INF)
dp[0] = 0

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

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

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
l=[[0,0]]
for _ in range(n):
    l.append(list(map(int,input().split())))
dp=[[10**10]*(n*(10**3)+1) for _ in range(n+1)]
for k in range(n+1):
    dp[k][0]=0
for i in range(1,n+1):
    for j in range(0,n*(10**3)+1):
        if j>=l[i][1]:
            dp[i][j]=min(dp[i-1][j-l[i][1]]+l[i][0],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
print(max([i for i,x in enumerate(dp[n]) if x<=w]))

Submission status: Accepted

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

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

for i in range(N):
    for j in range(vmax + 1):
        if j + wv[i][1] <= vmax:
            dp[i + 1][j + wv[i][1]] = min(dp[i][j] + wv[i][0], dp[i][j + wv[i][1]])

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

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

Submission status: Accepted

Solution code:
def b():
    def solve(N, W, V, wv):
        dp = [10**10] * (V+1)
        dp[0] = 0

        for i in range(N):
            wi = wv[i][0]
            vi = wv[i][1]

            # 降順でやらないと複数回アイテムをカウントしちゃう（j1 + wi をやった後に j2 + wi をやると、 j1 + wi == j2 のときに2カウントになってしまう）
            for v in range(V - vi, -1, -1):
                if dp[v] == -1:
                    continue
                if dp[v+vi] > dp[v] + wi:
                    dp[v+vi] = dp[v] + wi

        light = [i for i, w in enumerate(dp) if w <= W]
        return light[-1]

    N, W = map(int, input().split())
    wv = []
    V = 0

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

    print(solve(N, W, V, wv))

if __name__ == "__main__":
    b()

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
lst = [[0,0]]
vmax = 0
for _ in range(n):
    a, b = map(int, input().split())
    lst.append([a,b])
    vmax += b

dp = [[w+1] * (vmax+1) for _ in range(n+1)]
dp[0][0] = 0
ans = 0

for i in range(0, n):
    for sum_v in range(0, vmax+1):
        if sum_v  >= lst[i+1][1]:
            dp[i+1][sum_v] = min(dp[i][sum_v -  lst[i+1][1]] + lst[i+1][0], dp[i][sum_v])
        else:
            dp[i+1][sum_v] = dp[i][sum_v]
        if dp[i+1][sum_v] <= w:
            ans = max(ans, sum_v)

print(ans)

Submission status: Accepted

Solution code:
INF = 10**18
n, w = map(int, input().split())

weights = [0]
values = [0]

for i in range(n):
    x, y = map(int, input().split())
    weights.append(x)
    values.append(y)

max_value = sum(values)
dp = [[INF for i in range(max_value+1)] for j in range(n+1)]

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

for i in range(n+1):
    for j in range(max_value + 1):

        if values[i] <= j:
            dp[i][j] = min(dp[i-1][j], weights[i] + dp[i-1][j - values[i] ] )
        else:
            dp[i][j] = dp[i-1][j]

ans = 0

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

print(ans)
#print(dp)

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
wv=[]
for i in range(n):
    wv.append(tuple(map(int,input().split())))
v=sum([i[1] for i in wv])

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

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

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

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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

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

n, W = na()
wv = [na() for _ 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:
import sys

stdin = sys.stdin

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

n, W = na()
wv = [na() for _ in range(n)]
dp = [0]+[float("inf")]*(10**5)
for i in range(n):
      for j in range(10**5,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())

MAX_V = 10**5
dp = [[10**(18)]*(MAX_V+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_V+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(MAX_V+1):
  if dp[N][j] <= W and dp[N][j] != 10**(18):
    ans = max(ans, j)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
vmax = 1000*100+1
wmax = 100*10**9
dp = np.ones(vmax, dtype='int64') * wmax
dp[0] = 0

for i in range(N):
    wi, vi = map(int, input().split())
    dp[vi:] = np.fmin(dp[vi:], dp[:-vi] + wi)

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

Submission status: Accepted

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
vmax = 1000*100+1
wmax = 100*10**9
dp = np.ones(vmax, dtype='int64') * wmax
dp[0] = 0

for i in range(N):
    wi, vi = map(int, input().split())
    ndp = np.copy(dp)
    ndp[vi:] = np.fmin(dp[vi:], dp[:-vi] + wi)
    dp = ndp

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
vmax = 1000*100+1
wmax = 100*10**9
dp = [wmax] * vmax
dp[0] = 0
 
for i in range(N):
    wi, vi = map(int, input().split())
    ndp = dp[:]
    for j in range(vi, vmax):
        ndp[j] = min(dp[j], dp[j-vi] + wi)
    dp = ndp

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

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
l=[]
weight=[0]
value=[0]

for _ in range(n):
    a,b=map(int,input().split())
    value.append(b)
    weight.append(a)
maxvalue=sum(value)
dp=[[10**10 for i in range(maxvalue+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,maxvalue+1):
        if value[i]<=j:
            
            dp[i][j]=min(dp[i-1][j],dp[i-1][j-value[i]]+weight[i])
        else:
            dp[i][j]=dp[i-1][j]
for i in range(maxvalue+1):
    if dp[-1][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)]
INF = 10 ** 9 + 10

V = N * 1000
dp = [[INF] * (V + 1) for _ in range(N + 1)]
dp[0][0] = 0
s = 0
for i in range(N):
    w = wv[i][0]
    v = wv[i][1]
    for j in range(V + 1):
        dpp = dp[i][j - v] + w
        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])
        if dp[i + 1][j] <= W:
            s = max(s, j)

print(s)

Submission status: Accepted

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

INF = W + 10
dp = [[INF for _ in range(N*10**3+10)] for _ in range(N+1)]

dp[0][0] = 0
for sum_v in range(N*10**3+1):
    for n in range(N):
        Wi = wv[n][0]
        Vi = wv[n][1]
        if sum_v - Vi >= 0:
            dp[n+1][sum_v] = min(dp[n][sum_v], dp[n][sum_v-Vi] + Wi)
        dp[n+1][sum_v] = min(dp[n][sum_v], dp[n+1][sum_v])

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

print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from heapq import heapify, heappop, heappush
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

# ここから書き始める
n, w = map(int, input().split())
dp = [[INF for j in range(10 ** 5 + 1)] for i in range(n)]
dp[0][0] = 0
for i in range(n):
    weight, value = map(int, input().split())
    if i == 0:
        dp[i][value] = weight
        continue
    for j in range(10 ** 5 + 1):
        dp[i][j] = min(dp[i][j], dp[i - 1][j])
        if 0 <= j - value:
            dp[i][j] = min(dp[i][j], dp[i - 1][j - value] + weight)
ans = 0
for i in reversed(range(10 ** 5 + 1)): 
    if dp[-1][i] <= w:
        ans = i
        break
print(ans)

Submission status: Accepted

Solution code:
def main():
    n, W = list(map(int, input().split()))
    V = 100000
    INF = float('inf')
    dp = [[INF] * (V + 1) for _ in range(n + 1)]
    dp[0][0] = 0
    for i in range(1, n + 1):
        w, v = list(map(int, input().split()))
        for j in range(V + 1):
            if v > j:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = min(dp[i - 1][j - v] + w, dp[i - 1][j])
    ans = V
    while dp[n][ans] > W:
        ans -= 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

w=[0]*N
v=[0]*N

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

for i in range(N):
    ww,vv=input().split()
    w[i]=int(ww)
    v[i]=int(vv)

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
wv=[[0,0]]+[list(map(int,input().split())) for _ in range(N)]

dp=[[10**11+1 for i in range(100*10**3+1)] for j in range(N+1)]

dp[0][0]=0

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

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

Submission status: Accepted

Solution code:
# E Knapsack 2

from collections import deque

MAX_V = 10**5+1
n, w = map(int,input().split())
wv_list = deque([[int(x) for x in input().split()] for y in range(n)])

dp = [[float("Inf")] * (MAX_V) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0

for i in range(n):
    _w,_v = wv_list.popleft()
    for j in range(MAX_V):
        if j-_v < 0:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i][j-_v]+_w)

ans = 0
for i in range(MAX_V):
    if dp[n][i] <= w:
        ans = i
print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
INF = 1 << 60


def main():
    N, W, *WV = map(int, read().split())
    weight = WV[::2]
    value = WV[1::2]

    V = sum(value)
    dp = [[INF] * (V + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for v in range(V + 1):
            if v - value[i] >= 0:
                dp[i + 1][v] = dp[i][v - value[i]] + weight[i]
            if dp[i + 1][v] > dp[i][v]:
                dp[i + 1][v] = dp[i][v]

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

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
INF = 1 << 60


def main():
    N, W, *WV = map(int, read().split())
    weight = WV[::2]
    value = WV[1::2]

    V = sum(value)
    dp = [[INF] * (V + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for v in range(V + 1):
            if v - value[i] >= 0:
                dp[i + 1][v] = dp[i][v - value[i]] + weight[i]
            else:
                dp[i + 1][v] = weight[i]
            if dp[i + 1][v] > dp[i][v]:
                dp[i + 1][v] = dp[i][v]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
INF = 1 << 60


def main():
    N, W, *WV = map(int, read().split())
    weight = WV[::2]
    value = WV[1::2]

    V = sum(value)
    dp = [[INF] * (V + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for v in range(V + 1):
            if v - value[i] >= 0:
                dp[i + 1][v] = dp[i][v - value[i]] + weight[i]
            if dp[i + 1][v] > dp[i][v]:
                dp[i + 1][v] = dp[i][v]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int, input().split())))
INF = 10**10
v_max = 10**5
dp = [[INF]*(v_max+1) for _ in range(N+1)]
dp[0][0] = 0
ans = 0
for i in range(N):
    for j in range(v_max+1):
        if j >= wv[i][1]:
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]]+wv[i][0])
            #print(i, j, dp[i+1][j], dp[i][j], wv[i][0])
        else:
            dp[i+1][j] = dp[i][j]
        if i+1 == N and dp[i+1][j] <= W:
            ans = j
print(ans)

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