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 = map(int, input().split())
item_max = 100
val_max = 1000
col_max = item_max * val_max

# dp[i][j] = item iまでで価値jになるようにした時の最小重み
dp = [[float('inf') for _ in range(col_max + 1)] for _ in range(n + 1)]
for i in range(n + 1):
    dp[i][0] = 0

for i in range(1, n + 1):
    wi, vi = map(int, input().split())
    for j in range(1, col_max + 1):
        if j >= vi:
            dp[i][j] = min(dp[i - 1][j],
                            dp[i - 1][j - vi] + wi)
        else:
            dp[i][j] = dp[i - 1][j]

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

Submission status: Accepted

Solution code:
from numpy import*
f=lambda:map(int,input().split())
N,W=f()
d=full(10**6,W+1)
d[0]=0
exec("w,v=f();d[v:]=minimum(d[:-v]+w,d[v:]);"*N)
print(max(where(d<=W)[-1]))

Submission status: Accepted

Solution code:
import numpy as np
N,W=map(int,input().split())
dp=np.full(10**5+1,W+1)
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:
# coding: utf-8
# Your code here!
N,W=map(int,input().split())

jwels=[]

for _ in range(N):
    jwels.append(list(map(int,input().split())))

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

for w,v in jwels:
    for i in range(10**5+1)[::-1]:
        if dp[i]!=10**10 and i+v<=10**5:
            dp[i+v]=min(dp[i]+w,dp[i+v])

#print(dp[:100])

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

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
w=[]
v=[]
for _ in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
V=sum(v)
dp=[[float('inf')]*(V+1) for _ in range(N+1)]
dp[0][0]=0
for i in range(N):
    for sum_v in range(V+1):
        if sum_v-v[i]>=0:
            dp[i+1][sum_v]=min(dp[i][sum_v],dp[i][sum_v-v[i]]+w[i])
        else:
            dp[i+1][sum_v]=dp[i][sum_v]
res = 0
for i in range(V+1):
    if dp[N][i]<=W:
        res = i
print(res)

Submission status: Accepted

Solution code:
N, W = [int(i) for i in input().split()]
weight, value = [0] * (N + 1), [0] * (N + 1)

for i in range(1, N + 1):
    weight[i], value[i] = [int(i) for i in input().split()]

#%%

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

for i in range(1, N + 1):
    for j in range(sum_value + 1):
        if j >= value[i]:
            dp[i][j] = min(dp[i - 1][j], weight[i] + dp[i - 1][j - value[i]])
        else:
            dp[i][j] = dp[i -1][j]
        
ans = 0
for i in range(sum_value + 1):
    if dp[N][i] <= W:
        ans = i

print(ans)

Submission status: Accepted

Solution code:
N, W = [int(i) for i in input().split()]
weight, value = [0] * (N + 1), [0] * (N + 1)

for i in range(1, N + 1):
    weight[i], value[i] = [int(i) for i in input().split()]
#%%
sum_value = sum(value)
dp = [[float("inf")] * (sum_value + 1) for _ in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    for j in range(sum_value + 1):
        if j >= value[i]:
            dp[i][j] = weight[i] + dp[i - 1][j - value[i]]
        
        dp[i][j] = min(dp[i][j], dp[i -1][j])
        
ans = 0
for i in range(sum_value + 1):
    if dp[N][i] <= W:
        ans = i

print(ans)

Submission status: Accepted

Solution code:
N, W = [int(i) for i in input().split()]
weight, value = [0] * (N + 1), [0] * (N + 1)

for i in range(1, N + 1):
    weight[i], value[i] = [int(i) for i in input().split()]
#%%
sum_value = sum(value)
dp = [[float("inf")] * (sum_value + 1) for _ in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    for j in range(sum_value + 1):
        if j >= value[i]:
            dp[i][j] = min(dp[i][j], weight[i] + dp[i - 1][j - value[i]])
        # i番目の品物を買った場合と買わなかった場合を比較してweightが小さい方をDPテーブルに記憶する
        dp[i][j] = min(dp[i][j], dp[i -1][j])
        
ans = 0
for i in range(sum_value + 1):
    if dp[N][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)]

dp = []
valmax = int(1e5)
INF = int(1e10)
for _ in range(N+1):
    dp.append([INF] * (valmax+1))
dp[0][0] = 0

for i in range(N):
    for v in range(valmax+1):
        dp[i+1][v] = min(dp[i][v], dp[i][v - wv[i][1]] + wv[i][0])

maxval = 0
for k, l in enumerate(dp[N]):
    if l <= W:
        maxval = max(maxval, k)
    else:
        continue
print(maxval)

Submission status: Accepted

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

#%%

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

#%%

for i in range(N):
    for j in range(sum_value + 1):
        if j >= value[i]:
            dp[i + 1][j] = min(weight[i] + dp[i][j - value[i]], dp[i + 1][j])
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

#%%

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

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
a = [[int(i) for i in input().split(" ")] for j in range(n)]
dp = [[0]+[float("inf")]*(10**5) for i in range(n+1)]
for i in range(1, n+1):
    w_, v_ = a[i-1]
    for j in range(1, 10**5+1):
        if j < v_:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = min(dp[i-1][j-v_]+w_, dp[i-1][j])
for i in range(10**5, -1, -1):
    if dp[n][i]<=w:
        print(i)
        break

Submission status: Accepted

Solution code:
n,wei = [int(x) for x in input().split()]
w = []
v = []
for _ in range(n):
    a,b = [int(x) for x in input().split()]
    w.append(a)
    v.append(b)
v_x = n*max(v)+1
dp = [[float("inf")]*(v_x) for x in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for j in range(v_x):
        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])

res = 0
for i in range(v_x):
    if dp[n][i]<=wei:
        res = i
print(res)

Submission status: Accepted

Solution code:
from itertools import product


def read():
    N, W = list(map(int, input().split()))
    pairs = list()
    for i in range(N):
        w, v = list(map(int, input().split()))
        pairs.append((w, v))
    return N, W, pairs

def solve(N, W, pairs, INF=(10**11)+1):
    V = sum([v for w, v in pairs])
    dp = [[INF for j in range(V+1)] for i in range(N+1)]
    dp[0][V] = sum([w for w, v in pairs])
    for i, j in product(range(0, N), range(V, -1, -1)):
        w, v = pairs[i]
        dp[i+1][j] = dp[i][j]
        if 0 <= j + v <= V:
            dp[i+1][j] = min(dp[i][j], dp[i][j+v] - w)
    vmax = 0
    for j, i in product(range(V, -1, -1), range(0, N+1)):
        if dp[i][j] <= W:
            vmax = j
            break
    return vmax


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main(): #startline-------------------------------------------
    N,W = map(int,input().split())
    wv = [list(map(int,input().split())) for i in range(N)]
    w = [wv[i][0] for i in range(N)]
    v = [wv[i][1] for i in range(N)]
    MV = max(v)*N+1
    inf = float("inf")
    dp = [[inf]*MV for i in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(MV):
            if v[i] <= j:
                dp[i+1][j] = min(dp[i][j],dp[i][j-v[i]]+w[i])
            else:
                dp[i+1][j] = dp[i][j]
    ldp = dp[N]
    for i in reversed(range(MV)):
        if ldp[i] <= W:
            print(i)
            exit()

if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
N,W = map(int, input().strip().split(" "))
oj = []
for i in range(N):
    tmp = list(map(int, input().strip().split(" ")))
    oj.append(tmp)

#dp = [0] * (W+1)
M = 100 * 1001
dp = [10**10] * M

dp[oj[0][1]] = oj[0][0]

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

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

Submission status: Accepted

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

w = [0] * (N + 1)
v = [0] * (N + 1)

for i in range(1, N + 1):
    w[i], v[i] = map(int, input().split())
    
INF = 1000000010
MAX_V = 100010 #NVの最大
dp = [[INF] * (MAX_V + 1) for _ in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    for value in range(MAX_V):
        if value >= v[i]:#入れられる可能性があるかどうか
#ある場合は、直前にvalueがvalue-v[i]の場合の重さ最小値にw[i]を加えたものと比較
            dp[i][value] = min(dp[i][value], dp[i - 1][value-v[i]] + w[i])
#dp[i][value] = i-1番目までの品から価値がvalue以上になるように選んだ時の重さの最小値
        dp[i][value] = min(dp[i-1][value], dp[i][value])
    
ans = 0
for i in range(MAX_V+1):
    if dp[N][i] <= W:
        ans = i
print(ans)

Submission status: Accepted

Solution code:
import bisect

N, W = map(int, input().split())
w = [0] * (N + 1)
v = [0] * (N + 1)

for i in range(1, N + 1):
    w[i], v[i] = map(int, input().split())
INF = 1000000010
MAX_V = 100010
dp = [[INF] * MAX_V for _ in range(N + 1)]
dp[0][0] = 0

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

print(bisect.bisect_right(dp[N], W)-1)

Submission status: Accepted

Solution code:
n, W = map(int, input().split())
w = []
v = []
for _ in range(n):
    ww, vv = map(int, input().split())
    w.append(ww)
    v.append(vv)

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

for i in range(n):
    for j in range(10**5+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])
ans = 0
for i in range(10**5,-1,-1):
    if dp[n][i] <= W:
        ans = i
        break
print(ans)

Submission status: Accepted

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

def main():
    n, m = map(int, readline().split())
    inf = 10**11
    dp = [inf] * (1000 * n + 1)
    dp[0] = 0

    for i in range(n):
        w, v = map(int, input().split())
        for j in range(1000 * n - v, -1, -1):
            if dp[j] != inf:
                dp[j + v] = min(dp[j + v], dp[j] + w)
    ans = 0
    for a, b in enumerate(dp):
        if b <= m:
            ans = max(ans, a)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
inf = 10**11
dp = [inf] * (1000 * n + 1)
dp[0] = 0

for i in range(n):
    w, v = map(int, input().split())
    for j in range(1000 * n - v, -1, -1):
        if dp[j] != inf:
            dp[j + v] = min(dp[j + v], dp[j] + w)
ans = 0
for a, b in enumerate(dp):
    if b <= m:
        ans = max(ans, a)
print(ans)

Submission status: Accepted

Solution code:
MAX_N = 110
MAX_V = 100100
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())
INF = float('inf')
dp = [[INF] * MAX_V for _ in range(MAX_N)]
dp[0][0] = 0
for i in range(N):
    for j in range(MAX_V):
        dp[i + 1][j] = min(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])
res = 0
for sum_v in range(MAX_V):
    if dp[N][sum_v] <= W:
        res = sum_v
print(res)

Submission status: Accepted

Solution code:
N, W = list(map(int, input().split()))
INF = int(1e11)
dp = [[INF for i in range(int(1e5)+1)] for j 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(0, int(1e5)+1):
        if j - v >= 0:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-v]+w)
        dp[i][j] = min(dp[i][j], dp[i-1][j])

for j in reversed(range(int(1e5)+1)):
    for i in range(N+1):
        if dp[i][j] <= W:
            print(j)
            break
    else:
        continue
    break

Submission status: Accepted

Solution code:
N, W = list(map(int, input().split()))
INF = int(1e11)
dp = [[INF for i in range(int(1e5)+1)] for j 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(0, int(1e5)+1):
        dp[i][j] = min(dp[i-1][j], dp[i-1][j-v]+w)

for j in reversed(range(int(1e5)+1)):
    for i in range(N+1):
        if dp[i][j] <= W:
            print(j)
            break
    else:
        continue
    break

Submission status: Accepted

Solution code:
import bisect
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)
INF=10**10
G=[[INF]*(V+3) for i in range(n+1)]
for i in range(1,n+1):
  for j in range(V+3):
    if j-v[i-1]<0:
      G[i][j]=min(G[i-1][j],w[i-1])
    else:
      G[i][j]=min(G[i-1][j],G[i-1][j-v[i-1]]+w[i-1])
A=G[n][0:V+3]
print(bisect.bisect_right(A,W,lo=0,hi=len(A)))

Submission status: Accepted

Solution code:
n, w = [int(i) for i in input().split()]
wv = [[int(i) for i in input().split()] for _ in range(n)]
v = sum(list(zip(*wv))[1])

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

for i in range(n):
    w_i, v_i = wv[i]
    for j in range(v+1):
        # i番目を選ぶとき
        if j - v_i >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j-v_i] + w_i)
        # i番目を選ばないとき
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])

ans = 0
for j in range(v+1):
    if dp[n][j] <= w:
        ans = j

print(ans)

Submission status: Accepted

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

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

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

for i in range(n):
    for j in range(100005):
        # i番目の品物を選ぶ
        if j >= v[i]:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j-v[i]] + w[i])
        # i番目の品物を選ばない
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ans = 0
for v in range(100005):
    if dp[n][v] <= lim_w:
        ans = max(ans, v)

print(ans)

Submission status: Accepted

Solution code:
def main():
    goods, weight_limit = map(int, input().split())
    weight = []
    value = []
    for _ in range(goods):
        w, v = map(int, input().split())
        weight.append(w)
        value.append(v)
    max_value = 10 ** 5 + 10
    dp = [[float("inf") for _ in range(max_value + 1)] for _ in range(goods + 1)]
    dp[0][0] = 0
    for i in range(goods):
        for v in range(max_value + 1):
            if v >= value[i]:
                dp[i + 1][v] = min(dp[i][v], dp[i][v - value[i]] + weight[i])
            else:
                dp[i + 1][v] = dp[i][v]
    answer = 0
    for i in range(max_value):
        if dp[-1][i] <= weight_limit:
            answer = max(answer, i)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
ls = []
sum_v = 0
for i in range(N):
    ls.append(list(map(int,input().split())))
    sum_v += ls[-1][1]


dp = [[10**9+7]*(sum_v+1) for i in range(N+1) ]
# dp[i][j] はi番目までものを（できるだけ）価値j以上になるよう選ぶのときの最小の重さ
dp[0][0] = 0# ０個選んで価値j以上 --> dp[0][0]のみ達成

for i in range(1,N+1):
    w,v = ls[i-1]
    for j in range(0,sum_v+1):##
        if j>=v:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-v] + w)
            #??dp[i-1][j]==inf かつ dp[i-1][j-v]==infのとき??
            #dp[i-1][j-v]にwを足したほうがでかい　--> dp[i][j]==infとなる(価値jは達成できない)

        else:# v > jのとき　何にvを足してもjを超えてしまうので（ピッタリ価値jにできないので）前のまま
            dp[i][j] = dp[i-1][j]
mx = 0
for i in range(1,N+1):
    for j in range(0,sum_v+1):
        if dp[i][j] <=W:
            mx = max(mx,j)
print(mx)

Submission status: Accepted

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

import numpy as np
MAX = 10**5 + 1
dp = [np.full(MAX, 10**13) for i in range(N + 1)]
dp[0][0] = 0

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

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

print(ans)

Submission status: Accepted

Solution code:
# import numpy as np
# import scipy as sp
# import sys
# input = sys.stdin.readline
# print(a,b,c,sep="") # 半角スペースなしで出力(abc)
# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=list(map(int, input().split()))  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# a=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# a=[int(input()) for _ in range (n)]  #リスト入力  改行でa1 ... anのとき
# s=[list(map(str,list(input()))) for i in range(h)]  # 文字列の二次元配列入力
# s = [list(map(int, input().split())) for i in range(n)] # 数値の二次元配列入力
# a = b[:], a = [x[:] for x in b] # deepcopy
# chr(ord('a') + 1) # chrのインクリメント
# s.sort(key=lambda x: x[1], reverse=False) # 2番目の要素で昇順にソート（Trueなら降順）

n, w = list(map(int, input().split()))
wl = [0] * n
vl = [0] * n
v = 100001
for i in range(n):
    wl[i], vl[i] = map(int, input().split())

INF = float("inf")
dp = [[INF]*(v+1)for _ in range(n+1)]  # h:item w:value dp:weight
dp[0][0] = 0
for i in range(n):
    for j in range(v+1):
        if j-vl[i] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j-vl[i]]+wl[i])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

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

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

sumv = sum(v)
inf = float('inf')
#dp = [[inf]*110000 for _ in range(N+1)]
dp = [[inf]*(sumv+1) for _ in range(N+1)]
for row in range(N+1):
    dp[row][0] = 0


for i in range(N):
    for j in range(sumv+1):
        dp[i+1][j] = min(dp[i][j],dp[i][j-v[i]]+w[i]) #i番目の商品までで価値jを達せられる重さの最小値
# print(dp)
# for i in range(N):
#     print(dp[i])

ans = 0
for i in range(N+1):
    for j in range(sumv+1):
        if dp[i][j] <= W: # 重さ制約を満たすあ時に価値が上回っていたら更新
            ans = max(ans,j)
print(ans)
# 3 50
# 1 2
# 2 3
# 3 4

Submission status: Accepted

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

for i in range(n):
    ww, vv = map(int, input().split())
    w.append(ww)
    v.append(vv)

dp = [[float("inf")] * (n*(10**3+1)) for i in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    for j in range(n*1001):
        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])

for i in range(n * 1001):
    if dp[n][i] <= mw:
        ans = i

print(ans)

Submission status: Accepted

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

    dp = [[10**10]*(max(v)*(N+1)) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(1, N+1):
        for j in range(max(v)*(N+1)) :
            # i番目の品物を選ぶ場合
            if j >= v[i-1] :
                dp[i][j] = min(dp[i][j], dp[i-1][j-v[i-1]]+w[i-1])
            # i番目の品物を選ばない場合
            dp[i][j] = min(dp[i][j], dp[i-1][j])
    ans = 0
    for i in range(max(v)*(N+1)) :
        if dp[N][i] <= W :
            ans = i

    return ans

print(DP_E())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
A = list()
for n in range(N):
	A.append(list(map(int, input().split())))
inf = 10**10
V = 0
for a in range(N):
	V += A[a][1]
dp = [inf for v in range(V+1)]
dp[0] = 0
for p in range(N):
	for q in range(V - A[p][1], -1, -1):
		dp[q + A[p][1]] = min(dp[q + A[p][1]], dp[q] + A[p][0])
# print(dp)
ans = 0
for b in range(V+1):
	if (dp[b] <= W):
		ans = b
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys
from functools import reduce


def input():
    return sys.stdin.readline().strip()


def iinput():
    return int(input())


def tinput():
    return input().split()


def rinput():
    return map(int, tinput())


def rlinput():
    return list(rinput())


mod = int(1e9)+7


def factors(n):
    return set(reduce(list.__add__,
                      ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))


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

if __name__ == "__main__":
    n, weigh = rinput()
    w, v = [], []
    for i in range(n):
        wi, vi = rinput()
        w.append(wi)
        v.append(vi)

    mxv = sum(v)
    dp = [[99999999999 for i in range(mxv+1)]for j in range(n+1)]
    for i in range(n+1):
        dp[i][0]=0
    # print(w_v)
    for item in range(1, n+1):
        for val in range(1, mxv+1):
            if v[item-1] <= val:
                dp[item][val] = min(
                    dp[item-1][val-v[item-1]]+w[item-1], dp[item-1][val])
            else:
                dp[item][val] = dp[item-1][val]
    # print(dp)
    ans=0
    for i in range(mxv+1):
        if dp[n][i]<=weigh:
            ans=i
    print(ans)

Submission status: Accepted

Solution code:
import sys

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

INF = 10**10 + 1
dp = [[INF]*(N+1) for i in range(1000*N+2)]

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

i = 1

#while(True):
for j in range(1, N+1):
        for i in range(1, 1000*N+2):
#for i in range(1, 1000*N+2):
        #for j in range(1, N+1):
                if i-WV[j-1][1]>=0:
                        dp[i][j] = min(dp[i-WV[j-1][1]][j-1]+WV[j-1][0], dp[i][j-1])
                else:
                        dp[i][j] = min(dp[i][j-1], WV[j-1][0])
        #print(i, dp[i][N])
        #if dp[i-1][N] <= W and dp[i][N] > W:
                #break
        #i += 1

for i in range(1000*N+2):
        if dp[i][N] > W:
                print(i-1)
                exit()

Submission status: Accepted

Solution code:
import sys

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

INF = 10**10 + 1
dp = [[INF]*(N+1) for i in range(1000*N+2)]

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

i = 1

#while(True):
for i in range(1, 1000*N+2):
        for j in range(1, N+1):
                if i-WV[j-1][1]>=0:
                        dp[i][j] = min(dp[i-WV[j-1][1]][j-1]+WV[j-1][0], dp[i][j-1])
                else:
                        dp[i][j] = min(dp[i][j-1], WV[j-1][0])
        #print(i, dp[i][N])
        if dp[i-1][N] <= W and dp[i][N] > W:
                break
        #i += 1

print(i-1)

Submission status: Accepted

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10 ** 7)

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

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

INF = 10 ** 12
dp = [np.ones(10 ** 5 + 10, dtype=np.int64)*INF for _ in range(N + 1)]
dp[0][0] = 0

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

    # print(dp[i+1][:20])

r = dp[N]
ans = np.where(r <= W)[0].max()

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N, W = map(int, input().split())
wvs = [list(map(int, input().split())) for _ in range(N)]

INF = 10 ** 12
L = 10 ** 5 + 1

dp = np.full(L, INF, dtype=int)
dp[0] = 0

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

dp = [[10 ** 9 + 7 for i in range(sum(value) + 1)] for j in range(n + 1)]

dp[0][0] = 0

for i in range(n):
    for j in range(sum(value) + 1):
        if j - value[i] >= 0:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - value[i]] + weight[i])

        else:
            dp[i + 1][j] = dp[i][j]

a = sorted(range(sum(value) + 1), reverse = True)

for i in a:
    if dp[n][i] <= w:
        print(i)
        break

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
K = [[0, 0] for _ in range(N)]
V = 0
for i in range(N):
    w, v = map(int, input().split())
    K[i] = [w, v]
    V += v
dp = [[float('inf')]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    w, v = K[i]
    for sum_v in range(V+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 i, d in enumerate(dp[-1]):
    if d<=W: ans = i
print(ans)

Submission status: Accepted

Solution code:
# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate,permutations, combinations,combinations_with_replacement,product

def resolve():
    N, W = map(int, input().split())
    weight, value = [0] * N, [0] * N
    for i in range(N):
        weight[i], value[i] = map(int, input().split())



    # この前段階で、荷物の数N、ウェイトの上限W、
    # weightの表weightとvalueの表valueは用意しておく。
    def knapsack(N, W, weight, value):

        V=sum(value)
        # dp[i][v]はvを運べる最小のウェイトを意味する。
        # 求めたいのは、dp[N][v]<=Wなるvのmax
        dp = [[float('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]:
                    dp[i + 1][v] = min(dp[i][v], dp[i][v - value[i]] + weight[i])
                else:
                    dp[i + 1][v] = dp[i][v]

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

        return ans




    print(knapsack(N, W, weight, value))


resolve()

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番目を選ぶ場合
		if j - v[i] >= 0:
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v[i]] + w[i])
		# i+1番目を選ばない場合
		dp[i + 1][j] = min(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 = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())
V = sum(v)
INF = float('inf')
# the min weight to hold value j
dp = [INF] * (V+1)
dp[0] = 0
for i in range(N):
    for j in range(v[i], V+1)[::-1]:
        dp[j] = min(dp[j], dp[j-v[i]] + w[i])
for j in range(V+1)[::-1]:
    if dp[j] <= W:
        print(j)
        break

Submission status: Accepted

Solution code:
N,W = list(map(int,input().split()))
DP = [[float('inf')]*(1000*N+1) for i in range(N+1)]
DP[0][0] = 0
V = 0
for i in range(1,N+1):
    w,v = list(map(int,input().split()))
    V += v
    for j in range(V+1):
        DP[i][j] = min(DP[i-1][j],DP[i-1][j-v]+w) if v <= j else DP[i-1][j]

for i in range(1000*N,-1,-1):
    if DP[N][i] <= W:
        print(i)
        break

Submission status: Accepted

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

INF = 10**9 + 100
MAX_V = 10**5 + 100
dp = [INF] * (MAX_V + 1)
dp[0] = 0
for wi, vi in wv:
    for sum_v in reversed(range(vi, MAX_V+1)):
        dp[sum_v] = min(dp[sum_v - vi] + wi, dp[sum_v])
#print(dp)
ans = 0
for i in reversed(range(MAX_V+1)):
    if dp[i] <= w:
        print(i)
        exit()
#print(ans)

Submission status: Accepted

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

INF = 10**9 + 100
MAX_V = 10**5 + 100
dp = [INF] * (MAX_V + 1)
dp[0] = 0
for wi, vi in wv:
    for sum_v in reversed(range(vi, MAX_V+1)):
        dp[sum_v] = min(dp[sum_v - vi] + wi, dp[sum_v])
#print(dp)
ans = 0
for i in range(MAX_V, -1, -1):
    if dp[i] <= w:
        print(i)
        exit()
#print(ans)