Problem:


Score : 100 points

Problem Statement

There are N items, numbered 1, 2, \ldots, N.
For each i (1 \leq i \leq N), Item i has a weight of w_i and a value of v_i.

Taro has decided to choose some of the N items and carry them home in a knapsack.
The capacity of the knapsack is W, which means that the sum of the weights of items taken must be at most W.

Find the maximum possible sum of the values of items that Taro takes home.

Constraints

All values in input are integers.

1 \leq N \leq 100

1 \leq W \leq 10^9

1 \leq w_i \leq W

1 \leq v_i \leq 10^3

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

Print the maximum possible sum of the values of items that Taro takes home.

Sample Input 1

3 8
3 30
4 50
5 60

Sample Output 1

90

Items 1 and 3 should be taken.
Then, the sum of the weights is 3 + 5 = 8, and the sum of the values is 30 + 60 = 90.

Sample Input 2

1 1000000000
1000000000 10

Sample Output 2

10

Sample Input 3

6 15
6 5
5 6
6 4
6 6
3 5
7 2

Sample Output 3

17

Items 2, 4 and 5 should be taken.
Then, the sum of the weights is 5 + 6 + 3 = 14, and the sum of the values is 6 + 6 + 5 = 17.



Sample input:
3 8
3 30
4 50
5 60


Sample output:
90

Submission status: Accepted

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

import collections
def main():
    N,W = map(int, input().split())
    I = collections.deque()
    for _ in range(N):
        I.append(tuple(map(int, input().split())))

    MV = 1 + N*(10**3)
    dp = [[0]*MV for _ in range(N+1)]
    inf = 2*10**9
    for j in range(MV):
        dp[0][j] = inf
    dp[0][0] = 0
    
    for i in range(N):
        w,v = I.popleft()
        for j in range(MV):
            if j < v:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i][j-v] + w)
    ans = 0
    for v,w in enumerate(dp[N]):
        if w <= W:
            ans = v
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

import collections
def main():
    N,W = map(int, input().split())
    I = collections.deque()
    for _ in range(N):
        I.append(tuple(map(int, input().split())))

    MV = N*(10**3) + 1
    dp = [[0]*MV for _ in range(N+1)]
    inf = 2*10**9
    for j in range(MV):
        dp[0][j] = inf
    dp[0][0] = 0
    
    for i in range(N):
        w,v = I.popleft()
        for j in range(MV):
            if j < v:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i][j-v] + w)
    ans = 0
    for j in range(MV):
        if dp[N][j] <= W:
            ans = j
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = 1<<32

def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[INF] * (max(v)*N+1) for i in range(N+1)]
    dp[0][0] = 0

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

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

    # for i in dp:
    #     print(i)

    print(ans)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]" 
    v = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

M = 100000
dp = [-1] * (M + 1)
dp[0] = W
for _ in range(N):
    w, v = map(int, input().split())
    for i in range(M, -1, -1):
        if dp[i] == -1:
            continue
        if dp[i + v] < dp[i] - w:
            dp[i + v] = dp[i] - w

for i in range(M, -1, -1):
    if dp[i] != -1:
        print(i)
        break

Submission status: Accepted

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

maxv = 10 ** 3 * N + 1
t = [-1] * maxv
t[0] = W
cmaxv = 0
for _ in range(N):
    nw, nv = map(int, input().split())
    for i in range(cmaxv, -1, -1):
        ti = t[i]
        if ti == -1:
            continue
        if t[i + nv] < ti - nw:
            t[i + nv] = ti - nw
            if cmaxv < i + nv:
                cmaxv = i + nv
print(cmaxv)

Submission status: Accepted

Solution code:
import sys
imput = sys.stdin.readline
def main():
    # input
    N, weight = map(int, input().split())
    W, V = [], []
    for _ in range(N):
        w, v = map(int, input().split())
        W.append(w)
        V.append(v)
    V_max = sum(V)

    # loop
    dp = [[10**9]*(V_max+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(0, V_max+1):
            if j<V[i]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i][j-V[i]]+W[i])

    # check
    ans = []
    for j in range(1, V_max+1):
        if dp[i+1][j] <= weight:
            ans.append(j)
    print(max(ans))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
max_value = N*(10**3)
dp = [[10**11]*(max_value+1) for _ in range(N+1)]
dp[0][0]=0
for j in range(1, N+1):
    w, v = map(int, input().split())
    for k in range(0, max_value+1):
        if k < v:
            dp[j][k] = dp[j-1][k]
        else:
            dp[j][k] = min(dp[j-1][k-v]+w, dp[j-1][k])
answer = 0
for index, weight in enumerate(dp[N]):
    if weight <= W:
        answer = index
print(answer)

Submission status: Accepted

Solution code:
def main():
    [N, W] = [int(num) for num in input().split()]

    products = []
    v_all = 0
    for i in range(N):
        w_v = [int(num) for num in input().split()]
        products.append(w_v)
        v_all += w_v[1]

    dp = [[10**10] * (v_all+1) for _ in range(N+1)]

    dp[0][0] = 0

    for i in range(N+1):
        if i == 0:
            continue
        for v in range(v_all+1):
            if v < products[i-1][1]:
                dp[i][v] = dp[i-1][v]
            else:
                dp[i][v] = min(dp[i-1][v-products[i-1][1]] + products[i-1][0], dp[i-1][v])

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,W = [int(s) for s in input().split()]
dp = [[10**10]*(1000*100+1) for _ in range(N+1)]#外側から内側のイメージ

dp[0][0] = 0
for i in range(N):
    w, v = [int(s) for s in input().split()]
    for sum_v in range(1000*100+1):
        if sum_v - v >= 0:
            dp[i+1][sum_v] = min(dp[i][sum_v], dp[i][sum_v-v] + w)
        else:
            dp[i+1][sum_v] = dp[i][sum_v]

ans = 0
for sum_v in range(1000*100+1):
    if dp[N][sum_v] <= W:
        ans = sum_v

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

max_value = np.sum(np.array(WV), axis=0)[1]

# dp[i]: 価値iを達成するのに必要な重さの最小値
dp = np.full(max_value+1, W+1, dtype='int64')

dp[0] = 0
for w, v in WV:
    # 価値i(0 <= i <= max_value-v)の時の重さの最小値に対し
    # 次の荷物を入れて、価値i+vの時の重さの最小値を更新
    np.minimum(dp[:-v]+w, dp[v:], out=dp[v:])

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

Submission status: Accepted

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

DP = [0] * (sum_v+1)

for i in range(N):
    for j in (reversed(range(sum_v))):
        if j == 0 or DP[j] != 0:
            if DP[j + v[i]] > DP[j] + w[i] or DP[j + v[i]] == 0:
                DP[j + v[i]] = DP[j] + w[i]
                

for j in (reversed(range(sum_v+1))):
    if DP[j] != 0 and DP[j] <= W:
        print(j)
        break

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, W = list(map(int, input().split()))
WV = [list(map(int, input().split())) for _ in range(N)]

DP = [[float("inf")] * (10**5+1)]
for _ in range(N):
    DP.append([float("inf")] * (10**5+1))

DP[0][0] = 0

for n in range(N):
    for v in range(10 ** 5 + 1):
        if v - WV[n][1] >= 0:
            DP[n+1][v] = min(DP[n+1][v], DP[n][v - WV[n][1]] + WV[n][0])
        DP[n+1][v] = min(DP[n+1][v], DP[n][v])

ans = 0
for v in range(10 ** 5 + 1):
    if DP[N][v] <= W:
        ans = v

print(ans)

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
l=[list(map(int, input().split())) for i in range(n)]
c=0
d=0
for i in range(n):
    c+=l[i][1];d+=l[i][0]
dp=[[0]*(c+1) for _ in range(n)]
for i in range(1,l[0][1]+1):
    dp[0][i]=l[0][0]
for i in range(l[0][1]+1,c+1):
    dp[0][i]=d
for i in range(1,n):
    for j in range(1,c+1):
        if j<=l[i][1]:
            dp[i][j]=min(dp[i-1][j],l[i][0])
        else:
            dp[i][j]=min(dp[i-1][j],dp[i-1][j-l[i][1]]+l[i][0])
#print(dp)
for i in range(c,0,-1):
    if dp[-1][i]<=w:
        print(i)
        break

Submission status: Accepted

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

N, W = map(int, input().split())
table = []
for i in range(N):
  w,v = map(int, input().split())
  table.append((w,v))
dp = [[W+1]*(10**3*N+1) for i in range(N+1)]
dp[0][0] = 0

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

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

Submission status: Accepted

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

N,W=map(int,input().split())
V = 1000
INF = 1e+10
wv = [list(map(int, input().split())) for _ in range(N)]
dp = [[INF]*(N*V+1) for _ in range(N+1)]
dp[0][0] = 0

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

for i in reversed(range(N*V+1)):
    if dp[N][i] <= W:
        print(i)
        break

Submission status: Accepted

Solution code:
import sys
n, limit = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
#print(L)

dp = [{} for i in range(n+1)]
#print(dp)

for i in range(n):
    Lw, Lv = L[i][0], L[i][1]
    dp[i+1][Lv] = Lw #※初めてi+1行目に値が入る
    for v, w in dp[i].items():
        dp[i+1][v] = min(dp[i+1].get(v, w), w) #i+1行目に値がある場合があるので比較
        ww = min(dp[i+1].get(v+Lv, w+Lw), w+Lw)
        if ww <=limit:
            dp[i+1][v+Lv] =ww 

print(max(dp[-1].keys()))

Submission status: Accepted

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

knapsack = [ [ int(v) for v in input().split() ] for i in range(n) ]
total_value = sum([ i[1] for i in knapsack ])

dp_list = [ w+1 for i in range(total_value+1) ]
dp_list[0] = 0

for wi, vi in knapsack:
    new_dp_list = [0] + [ w+1 for i in range(total_value) ]
    for j in range(total_value+1):
        if j >= vi:
            new_dp_list[j] = min(dp_list[j], dp_list[j-vi] + wi)
        else:
            new_dp_list[j] = dp_list[j]
    dp_list = new_dp_list

ans = 0
for i, v in enumerate(dp_list):
    if v != w+1:
        ans = i
print(ans)

Submission status: Accepted

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

N, W = map(int, input().split())
table = []
for i in range(N):
  w,v = map(int, input().split())
  table.append((w,v))
INF = W+1
dp = [[INF]*(10**3*N+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
  for k in range(10**3*N+1):
    w,v = table[i-1]
    dp[i][k] = dp[i-1][k]
    if v<=k and dp[i-1][k-v] <= INF:
      dp[i][k] = min(dp[i][k],dp[i-1][k-v]+w)

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

Submission status: Accepted

Solution code:
import sys
n, limit = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
#print(L)
dp = [{} for i in range(n+1)]

for i in range(n):
    Lw, Lv = L[i][0], L[i][1] 
    dp[i+1][Lv] = min(Lw, dp[i].get(Lv, Lw))          #価値テーブルに重量を入れる
    for v, w in dp[i].items():
        dp[i+1][v] = min(w, dp[i+1].get(v, w)) #上下比較
        tmp_w= min(Lw+ w, dp[i+1].get(Lv+v, Lw+w))
        if tmp_w <=limit:
            dp[i+1][Lv+ v] = tmp_w
        
print(max(dp[-1].keys()))

Submission status: Accepted

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

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

# i番目まで選べる時の価値とその時の最小重み
dp = [{} for _ in range(N+1)]
dp[0][0] = 0

for i, (w, v) in enumerate(wv):
    #i-1個目までの時の価値と対応する最小重みを取り出す
    for v0, w0 in dp[i].items(): # 典型的なDPの過去の部分を利用するのがi, 現在部分がi+1
        # iまで選べる時にその価値がすでに組み合わせが存在するなら小さいほう、
        if v0 in dp[i+1]:
            dp[i+1][v0] = min(dp[i+1][v0], w0)
        # 組み合わせがないならi-1個までで作った時の重みを採用
        else:
            dp[i+1][v0] = w0

        #i番目を利用して制限を超えるならその組み合わせはスキップ
        if w0 + w > W:
            continue
        #i-1番目までのそれぞれの組み合わせとi番目を選んだ場合
        if v0 + v in dp[i+1]:
            
            dp[i+1][v0 + v] = min(dp[i+1][v0 + v], w0 + w)
        else:
            dp[i+1][v0 + v] = w0 + w

print(max(dp[N].keys()))

Submission status: Accepted

Solution code:
N, W = [int(i) for i in input().split()]
WV = [[int(i) for i in input().split()] for j in range(N)]

import numpy as np
max_value = np.sum(np.array(WV), axis=0)[1]

# dp[v]: 価値vを達成するのに必要な重さの最小値
dp = np.full(max_value + 1, W + 1, dtype='int64')

dp[0] = 0
for w, v in WV:
    # 価値i(0 <= i <= max_value - v)のときの重さの最小値に対し
    # 次の荷物を入れて、価値i+vのときの重さの最小値を更新
    np.minimum(dp[:-v] + w, dp[v:], out=dp[v:])
print(np.max(np.where(dp <= W)))

Submission status: Accepted

Solution code:
N,W = map(int, input().split())
INF = 10**12
dp = [[INF for i in range(110000)] for j in range(N+1)]

"""
dp[i][v] i個目の品物に対して、価値vをgetしうる重さの最小値
"""
dp[0][0] = 0

for i in range(N):
    w,v = map(int, input().split())
    for j in range(110000):
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])
        if v + j < 110000 and dp[i][j] != INF:
            # print("aaa",v+j,min(dp[i][v+j],dp[i][j]+w))
            dp[i+1][v+j] = min(dp[i][v+j],dp[i][j]+w)
            # print(dp[i+1][v+j],min(dp[i][v+j],dp[i][v]+w))


res = dp[N]
ans = 0
for v,r in enumerate(res):
    if r <= W:
        ans = v
print(ans)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,W = LI()
wv = [LI() for _ in range(n)]
V = 0
for i in range(n):
    w,v = wv[i]
    V += v
    
dp = [[inf]*(V+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    w,v = wv[i]
    for j in range(V+1):
        if j < v:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j],dp[i][j-v] + w)
res = 0
for i in range(V+1):
    if dp[-1][i] <= W:
        res = i
print(res)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
from operator import itemgetter


def branchAndBound(N: int, M: int, V: list, W: list, R: list) -> int:
    def upperbound(w, v, i):
        rest = M - w
        _v = v
        for j in range(i + 1, N):
            if W[j] >= rest:
                rest -= W[j]
                v += V[j]
                _v = v
            else:
                _v += R[j] * rest
                break
        return v, _v

    prov, tmp = upperbound(0, 0, -1)
    h = [(tmp, W[0], V[0] * (W[0] >= M), 0), (upperbound(0, 0, 0)[1], 0, 0, 0)]
    while h:
        _v, w, v, cur = heappop(h)
        if _v > prov or cur == N - 1:
            continue
        nxtw, nxtv = w + W[cur + 1], v + V[cur + 1]
        if nxtw >= M:
            heappush(h, (_v, nxtw, nxtv, cur + 1))
        _prov, ub = upperbound(w, v, cur)
        if _prov < prov:
            prov = _prov
        if ub < prov:
            heappush(h, (ub, w, v, cur + 1))
    return -prov


def main():
    N, M, *L = map(int, open(0).read().split())
    t = [(v, w, v / w) for w, v in zip(*[iter(L)] * 2)]
    t.sort(key=itemgetter(2), reverse=True)
    V, W, R = [], [], []
    for v, w, r in t:
        V += [-v]
        W += [-w]
        R += [r]
    ans = branchAndBound(N, -M, V, W, R)
    print(ans)
    
if __name__=="__main__":main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
sum=0
for i in range(n):
  sum+=l[i][1]
dp=[[999999999999 for i in range(sum+1)] for j in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
  for j in range(sum+1):
    dp[i][j]=min(dp[i-1][max(j-l[i-1][1],0)]+l[i-1][0],dp[i-1][j])
for i in range(sum,-1,-1):
  if dp[n][i]<=w:
    print(i)
    break

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
n, limit = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dp =[defaultdict(int) for _ in range(n)]
dp[0][L[0][1]] = L[0][0]
#print(dp)
for i in range(1, n):
    dp[i][L[i][1]] = min(L[i][0], dp[i-1].get(L[i][1], L[i][0])) #①L[i]の荷物を代入
    for v, w in dp[i-1].items():
        dp[i][v] = min(w, dp[i].get(v, w)) #②i-1番目の各荷物を代入
        dp[i][v+L[i][1]] = min(w + L[i][0], dp[i-1].get(v+L[i][1], w + L[i][0]) ) #③i-1番目の各荷物とL[i]を足した物を代入
        #print(dp)

ans =0
for v, w in dp[-1].items():
    if w<=limit:
        if ans < v:
            ans = v

print(ans)

Submission status: Accepted

Solution code:
import sys
n, limit = map(int, sys.stdin.readline().split()) 
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dp = [dict() for i in range(n)]
#print(dp)
dp[0][L[0][1]] = L[0][0]

for i in range(1, n):
    dp[i][L[i][1]] = min(L[i][0], dp[i-1].get(L[i][1], float('inf')))
    for v, w in dp[i-1].items():
        dp[i][v] = min(dp[i-1][v], dp[i].get(v, float('inf')))
        dp[i][L[i][1] + v] = min(L[i][0] + dp[i-1][v], dp[i-1].get(L[i][1] + v, float('inf'))) 
        
ans = 0
for v, w in dp[-1].items():
    if w <=limit:
        if ans < v:
            ans = v
#print(dp)
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for i in range(N)]

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

    max_v = 0
    for i in range(N):
        w, v = wv[i]
        dp[v:max_v + v + 1] = np.minimum(dp[v:max_v + v + 1], dp[:max_v + 1] + w)
        max_v += v
    
    print(np.where(dp <= W)[0].max())

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    t = [[int(i) for i in input().split()] for _ in range(N)]

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

    dp[0][0] = 0
    for n in range(1, N+1):
        dp[n][0] = 0
        for v in range(1, N*10**3+1):
            dp[n][v] = min(dp[n-1][v], dp[n-1][max(0, v-t[n-1][1])]+t[n-1][0])
    ans = float("inf")*-1
    for i, v in enumerate(dp[N]):
        if v <= W:
            ans = max(ans, i)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

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)

V = sum(v)

dp = [ [INF for _ in range(V+1)] for _ in range(N+1) ]

dp[0][0] = 0

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

#print(dp[N])

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

print(ans)

Submission status: Accepted

Solution code:


import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

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)

V = sum(v)

dp = [ [INF for _ in range(V+1)] for _ in range(N+1) ]

dp[0][0] = 0

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

#print(dp[N])

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

print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
Data = [list(map(int, input().split())) for _ in range(N)]
sum_value_aploximate = N * 10**3 + 1

dp = [[None for _ in range(sum_value_aploximate)] for _ in range(N+1)]
temp = float("inf")
dp[0] = [temp for _ in range(sum_value_aploximate)]
dp[0][0] = 0

for i in range(1, N+1):
    for j in range(sum_value_aploximate):
        if Data[i-1][1] <= j:
            dp[i][j] = min(dp[i-1][j], (dp[i-1][j-Data[i-1][1]] + Data[i-1][0]))
        else:
            dp[i][j] = dp[i-1][j]

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

print(ans)

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
ws = [0] * n
vs = [0] * n

for i in range(n):
    ws[i], vs[i] = map(int, input().split())

INF = 10 ** 18
dp = [[INF] * 100010 for _ in range(110)]
dp[0][0] = 0
for i in range(n):
    for sum_v in range(100010):
        # i番目を選ぶ
        if sum_v - vs[i] >= 0:
            dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v - vs[i]] + ws[i])
        
        # i番目を選ばない
        dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v])

ans = 0
for sum_v in range(100010):
    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()]
dp = [[10**9+1]*(10**5+1) for _ in range(N+2)]
uv = [[0,0]]+[[int(x) for x in input().split()] for _ in range(N)]
dp[0][0]=0
for i in range(N+1):
  for j in range(10**5+1):
    dp[i+1][j] = min(dp[i+1][j],dp[i][j])
    if uv[i][1]+j<=10**5:
      dp[i+1][j+uv[i][1]] = min(dp[i][j]+uv[i][0],dp[i+1][j+uv[i][1]])
ans = 0
for i in range(10**5+1):
  if 0<dp[N+1][i]<=W:
    ans = max(ans,i)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    INF = float('inf')
    MAX_V = 10 ** 3 * N
    dp = [INF] * (MAX_V + 1)
    dp[0] = 0
    for i in range(N):
        for j in range(MAX_V - v[i], -1, -1):
            dp[j + v[i]] = min(dp[j + v[i]], dp[j] + w[i])
    ret = 0
    for j in range(MAX_V + 1):
        if dp[j] <= W:
            ret = max(ret, j)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]" 
    v = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
li=[list(map(int,input().split())) for i in range(N)]
max_n=0
for a in range(N):
    max_n+=li[a][1]
dp=[[float('INF')]*(max_n+1) for i in range(N+1)]
dp[0][0]=0
for i in range(N):
    for sum_v in range(max_n+1):
        if sum_v >= li[i][1]:
            dp[i+1][sum_v]=min(dp[i][sum_v],dp[i][sum_v-li[i][1]]+li[i][0])
        else:
            dp[i+1][sum_v]=dp[i][sum_v]
ans=0
for i in range(max_n+1):
    if dp[N][i] <= W:
        ans = i
print(ans)