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:
'''
w,v = [0] * n, [0] * n
for i in range(n):
    w[i] , v[i] = map(int,input().split())
'''

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

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

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

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)
# print(w)
# print(v)

# print(wv)
dp = [[10 ** 12] * 100100 for _ in range(110)]
dp[0][0] = 0

for i in range(N):
    for sum_v in range(100100):

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

        dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v])
# print(dp[1][:100])
# print(dp[2][:100])


for sum_v in range(100100):
    if dp[N][sum_v] <= W:
        ans = sum_v
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())

def solve(w,v):
    # print(W)
    dp = [[W+1]*(10**5+1) for i in range(N+1)]
    dp[0][0]=0
    for i in range(1,N+1):
        for j in range(10**5+1):
            if j < v[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i-1]]+w[i-1])
    for i in range(10**5,-1,-1):
        if dp[-1][i]<=W:
            ans = i
            break
    return ans
print(solve(w,v))

Submission status: Accepted

Solution code:
#5
N,W=map(int,input().split())
A=[[0]]+[[int(x) for x in input().split()] for i in range(N)]
A_w=[]
V=N*10**3

dp=[[float("inf") for i in range(V+1)] for j in range(N+1)]
dp[0][0]=0

for i in range(1,N+1):
    w=A[i][0]
    v=A[i][1]
    for sum_v in range(V+1):
        if sum_v-v>=0:
            dp[i][sum_v]=min(dp[i][sum_v],dp[i-1][sum_v-v]+w)
        dp[i][sum_v]=min(dp[i][sum_v],dp[i-1][sum_v])
Max=0
for i in range(V+1):
    if dp[-1][i]<=W:
        Max=i
print(Max)

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(n)]
sumv = 0
for i in range(n):
    sumv += p[i][1]
p.insert(0, [0, 0])
inf = w + 1
dp = [[inf for _ in range(sumv + 1)] for _ in range(n + 1)]
for i in range(n + 1):
    dp[i][0] = 0
for i in range(1, n + 1):
    m = 0
    for j in range(1, sumv + 1):
        if j >= p[i][1]:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - p[i][1]] + p[i][0])
        else:
            dp[i][j] = dp[i - 1][j]
for i in range(sumv, -1, -1):
    if not dp[n][i] == inf:
        print(i)
        exit()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
WV = [tuple(map(int, input().split())) for i in range(n)]
W = [w for w, v in WV]
V = [v for w, v in WV]
inf = 10**10
sumV = sum(V)
DP = [[inf for j in range(sumV+1)] for i in range(n+1)]
DP[0][0] = 0
for i in range(1, n+1):
    for j in range(V[i-1]):
        DP[i][j] = DP[i-1][j]
    for j in range(V[i-1], sumV+1):
        DP[i][j] = min(DP[i-1][j], DP[i-1][j-V[i-1]]+W[i-1])
for j in range(sumV, 0, -1):
    if DP[n][j] <= m:
        print(j)
        exit()

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(10e9)


def knapSack(V):
    for i in range(n + 1):
        for v in range(V + 1):
            if v == 0:
                K[i][v] = 0
            elif val[i - 1] <= v:
                K[i][v] = min(wt[i - 1] + K[i - 1][v - val[i - 1]], K[i - 1][v])
            else:
                K[i][v] = K[i - 1][v]

    return K[n][V]

n,w=mdata()
val=[0]*(n)
wt=[0]*(n)
for i in range(n):
    wt[i],val[i]=mdata()
V=100005
K = [[1000000007 for x in range(V + 1)] for x in range(n + 1)]
knapSack(V)
m=0
for i in range(n + 1):
    for v in range(V + 1):
        if 1<=K[i][v]<=w :
            m=max(m,v)
print(m)

Submission status: Accepted

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

    maxvalue = sum(value)
    dp = [[float('inf')]*(maxvalue+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][0] = 0

    for i in range(N):
        for v in range(maxvalue+1):
            if v - value[i] < 0:
                dp[i+1][v] = min(dp[i+1][v], dp[i][v])
            else:
                dp[i+1][v] = min(dp[i+1][v], dp[i][v-value[i]]+weight[i])
                dp[i+1][v] = min(dp[i+1][v], dp[i][v])
    
    ans = 0
    for i in range(N+1):
        for j in range(maxvalue+1):
            if dp[i][j] <= W:
                ans = max(ans, j)
    
    print(ans)
            
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

for i in range(N+1):
    w,v=items[i]
    dp[i][v]=w

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

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

Submission status: Accepted

Solution code:
N, W = [int(i) for i in input().split()]
noValue = [[W+1 for j in range(100001)] for i in range(N)] # 重さ[番号][価値]
w,v = [int(i) for i in input().split()]
maxValue = v
noValue[0][v] = w

for i in range(1,N) :	
	noValue[i][0] = 0
	w, v = [int(i) for i in input().split()] # w, v = w_i, v_i
	for j in range(1,min(maxValue+v+1, 100001)) : # 現在の価値の最大+今の入力の価値 or 価値の最大値 の小さいほう
		if j < v  :
			noValue[i][j] = noValue[i-1][j]
		else :
			if noValue[i-1][j - v] == W + 1 :
				if j == v :
					noValue[i][j] = w
					maxValue = max(maxValue, j)
				else :
					noValue[i][j] = noValue[i-1][j]
			elif noValue[i-1][j-v] + w > W :
				noValue[i][j] = noValue[i-1][j]
			else :
				noValue[i][j] = min(noValue[i-1][j - v] + w, noValue[i-1][j])
				maxValue = max(maxValue, j)
print(maxValue)

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())
mv = sum(v)
dp = [[float("INF")]*(mv+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for s in range(mv+1):
        if s - v[i] < 0: dp[i+1][s] = dp[i][s]
        else: dp[i+1][s] = min(dp[i][s], dp[i][s-v[i]] + w[i])
ans = 0
for x in range(1,mv+1):
    if dp[n][x] <= W: ans = x
print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
w, v = [], []
for _ in range(N):
    w_, v_ = map(int, input().split())
    w.append(w_)
    v.append(v_)
V = sum(v)
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):
        if j >= v[i]: 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 i in range(V+1):
    if dp[N][i]<=W: ans=i
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin


# 最小化問題
def chmin(a,b):
    if a > b: return b
    else: return a


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, W = list(map(int,_in[0].split(' ')))  # type:list(int)
    w_v_arr = []
    V = 0
    for i in range(N):
        _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
        w_v_arr.append(_)
        V += _[1]
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    dp = [[float('inf')] * (V+1) for _ in range(N+1)]  # 最小化問題
    #dp[i][v]:=(i-1)番目までの品物から価値がv以上になるよう選んだときの重さの総和の最小値
    dp[0][0] = 0  # 初期条件

    # 配るDP
    for i in range(N):
        for v in range(0,V+1):
            if v >= w_v_arr[i][1]:
                dp[i+1][v] = chmin(dp[i+1][v],dp[i][v-w_v_arr[i][1]]+w_v_arr[i][0])
            dp[i+1][v] = chmin(dp[i+1][v],dp[i][v])
    cnt = 0
    for v in range(0,V+1):
        if dp[N][v] <= W:
            cnt = v
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

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())
mv = n*max(v)
dp = [[float("INF")]*(mv+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for s in range(mv+1):
        if s - v[i] < 0: dp[i+1][s] = dp[i][s]
        else: dp[i+1][s] = min(dp[i][s], dp[i][s-v[i]] + w[i])
ans = 0
for x in range(1,mv+1):
    if dp[n][x] <= W: ans = x
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(1,n+1): w[i],v[i] = map(int,input().split())
mv = n*max(v)
dp = [[float("INF")]*(mv+1) for _ in range(n+1)]
for i in range(n): dp[i][0] = 0
for i in range(1,n+1):
    for s in range(1,mv+1):
        if s - v[i] < 0: dp[i][s] = dp[i-1][s]
        else: dp[i][s] = min(dp[i-1][s], dp[i-1][s-v[i]] + w[i])
ans = 0
for x in range(1,mv+1):
    if dp[n][x] <= W: ans = x
print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
w = [0]
v = [0]
for _ in range(N):
    x, y = map(int, input().split())
    w.append(x)
    v.append(y)

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n,w=map(int,input().split())
wv=[]
for _ in range(n):
    wv.append(list(map(int,input().split())))
dp=np.full(100001,w+1) # dp[j]:価値総和jをちょうど実現できる最小の重さ総和
dp[0]=0
for i in range(n):# i番目までの商品について全ての重さについて調べる
    w_=wv[i][0]
    v_=wv[i][1]
    dp[v_:]=np.minimum(dp[v_:],dp[:-v_]+w_)

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

Submission status: Accepted

Solution code:
def main():
    N, W = list(map(int, input().split()))
    INF = float("inf")
    DP = [[INF for i in range(10**5+1)] for j in range(N+1)]
    DP[0][0] = 0
    for i in range(N):
        w, v = list(map(int, input().split()))
        for sum_v in range(10**5+1):
            if sum_v - v >= 0:
                DP[i+1][sum_v] = min(DP[i][sum_v],DP[i][sum_v-v]+w)
            
            DP[i+1][sum_v] = min(DP[i+1][sum_v],DP[i][sum_v])
            
    for i in range(10**5+1):
        if DP[N][i] <= W:
            ans = i
    print(ans)

if __name__ == "__main__":
    main()
    pass

Submission status: Accepted

Solution code:
import copy
n,w = map(int,input().split())
V = n*10**3+2
b = [float("inf")]*V
b[0] = 0
a = [float("inf")]*V
a[0] = 0
for _ in range(n):
  wi,vi = map(int,input().split())
  for i in range(vi):
    a[i] = min(b[i],wi)
  for i in range(vi,V):
    a[i] = min(b[i],b[i-vi]+wi)
  b = copy.copy(a)
i = 0
while b[i] <= w:
  i += 1
print(i-1)

Submission status: Accepted

Solution code:
def solve():
    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)
    sum_value = sum(value)
    
    dp = [[float('inf')] * (sum_value+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][0] = 0

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

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import itertools
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

N, W = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]
# print(WV)
max_v = 0
for i in range(N):
    max_v += WV[i][1]
# print(max_v)
dp = [[INF]*(max_v+1) for _ in range(N+1)]
dp[0][0] = 0
# print(dp)
for n in range(N):
    for sum_v in range(max_v+1):
        weight = WV[n][0]
        value = WV[n][1]
        #print('weight', weight, 'value', value)
        if sum_v-value >= 0:
            dp[n+1][sum_v] = min(dp[n+1][sum_v], dp[n][sum_v-value]+weight)
        dp[n+1][sum_v] = min(dp[n+1][sum_v], dp[n][sum_v])
ans = 0
# print(dp)
for sum_v in range(max_v+1):
    if dp[N][sum_v] <= W:
        ans = sum_v
print(ans)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
k,l = 0,0
lv = [0] * N
lw = [0] * N
for i in range(N):
    lw[i],lv[i] = map(int,input().split())
V = sum(lv)
dp = [[float("inf") for i in range(V+1)] for j in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for sv in range(V+1):
        if sv-lv[i] < 0:
            dp[i+1][sv] = dp[i][sv]
        else:
            dp[i+1][sv] = min(dp[i][sv],(dp[i][sv-lv[i]]+lw[i]))

a = V
while a >= 0:
    if dp[-1][a] <= W:
        print(a)
        a = -1
    else:
        a -= 1

Submission status: Accepted

Solution code:
n,w = map(int,input().split())
weight = [0]*n
value = [0]*n
for i in range(n):
    weight[i],value[i] = map(int,input().split())
dp = [[1000000001 for i in range(max(value)*n+1)]for j in range(n+1)]
dp[0][0] = 0

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

ans = 0
for i,j in enumerate(dp[n]):
    if j <= w:
        ans = max(ans,i)

print(ans)

Submission status: Accepted

Solution code:
import copy

N,W=map(int,input().split())
G=[0]   #G[0]はダミー
for index1 in range(N):
    w,v=map(int,input().split())
    G.append((w,v))
sum_v=0
for index2 in range(1,N+1):
    sum_v+=G[index2][1]

#DP[i][j]=i番目までの品物を使って価値j以上の最小重量
DP=[]
inf=float('inf')
component=[0]+[inf]*sum_v
for index3 in range(N+1):
    DP.append(copy.copy(component))

for i in range(1,N+1):
    for j in range(1,sum_v+1):
        DP[i][j]=min(DP[i-1][j],DP[i-1][max(0,j-G[i][1])]+G[i][0])

#print(sum_v)
#print(DP[N][sum_v])
ans=0
for k in range(1,sum_v+1):
    #print(ans)
    if DP[N][k]<=W:
        ans=max(ans,k)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N, W = map(int, input().split())
dp = np.full(N * 10000 + 1, W + 1) 
dp[0] = 0
for n 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:
import numpy as np
n,w=map(int,input().split())
wv=[]
for _ in range(n):
      wv.append(list(map(int,input().split())))
# dp[i]:価値の総和をちょうどiにできる最小の重さ総和
# dp[i]=w+1となる価値総和iにはできない。
# 求めるのはdp[i]<=wとなる最大のi
dp=np.full(10**5+1,w+1) # ndarray(1000,1000,...,1000])
dp[0]=0
# 10**5:viの総和の最大
for i in range(n):
      w_=wv[i][0]
      v_=wv[i][1]
      # i番目までの商品を取るか取らないかの全ての組み合わせをためすことができる。
      dp[v_:]=np.minimum(dp[v_:], dp[:-v_]+w_)
print(np.where(dp<=w)[0][-1])

Submission status: Accepted

Solution code:
n,W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(n)]
dp = [[10 ** 18] * (10 ** 5 + 1) for i in range(n+1)]
dp[0][0] = 0
for i,(w,v) in enumerate(wv):
  for j in range(1000 * i + 1):
    dp[i+1][j+v] = min(dp[i+1][j+v],dp[i][j]+w)
    dp[i+1][j] = min(dp[i+1][j],dp[i][j])
ans = 0
for k,w in enumerate(dp[n]):
  if w <= W:
    ans = k
print(ans)

Submission status: Accepted

Solution code:
import sys


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

def main():

    # i have too make index as weight and value as value
    import numpy as np

    n, capacity = map(int, input().split())
    value_max = 10 ** 5
    dp = np.full(value_max + 1, capacity + 1)
    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 <= capacity)[0][-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# python3.4.2用
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')
def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N, W = imn()
weight = []
value = []
for _ in range(N):
    w,v = imn()
    weight.append(w)
    value.append(v)

max_v = 100*1000

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

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

Submission status: Accepted

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

max_v = N * 1000

ans_array = [[10 ** 12] * (max_v + 1) for _ in range(N + 1)]

ans_array[0][0] = 0

for n in range(1, N + 1):
    ans_array[n][0] = 0
    for v in range(1, max_v + 1):
        if wv_array[n - 1][1] > v:
            ans_array[n][v] = ans_array[n - 1][v]
        else:
            ans_array[n][v] = min(
                ans_array[n - 1][v], ans_array[n - 1][v - wv_array[n - 1][1]] + wv_array[n - 1][0])

for v in range(max_v, -1, -1):
    if ans_array[N][v] <= W:
        print(v)
        exit()

Submission status: Accepted

Solution code:
import numpy as np


n, capacity = map(int, input().split())
value_max = 10 ** 5
dp = np.full(value_max + 1, capacity + 1)
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 <= capacity)[0][-1])

Submission status: Accepted

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

def main():
    N, W = map(int, input().split())
    inf = float('inf')
    dp = [inf] * (10**5+1)
    dp[0] = 0
    for n in range(1, N+1):
        w, v = map(int, input().split())
        for i in range(v, 10**5+1)[::-1]:
            if dp[i-v] + w <= W:
                dp[i] = min(dp[i], dp[i-v] + w)
    for i in range(10**5+1)[::-1]:
        if dp[i] < inf:
            print(i)
            break
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    m = sum(v)
    dp = [[float("inf")] * (m+1) for _ in range(N + 1)]
    dp[0][0] = 0

    for n in range(N):
        for kati in range(m+1):
            if kati - v[n] >= 0:
                dp[n+1][kati] = min(dp[n+1][kati], dp[n][kati-v[n]] + w[n])
            dp[n+1][kati] = min(dp[n+1][kati], dp[n][kati])

    ans = 0
    for i in range(m+1):
        if dp[-1][i] <= W:
            ans = i

    print(ans)


# Generated by 1.1.6 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:
from sys import stdin

def main():
    n,w = map(int, input().split())
    ary = [list(map(int, stdin.readline().split())) for _ in range(n)]
    xmax = sum([i[1] for i in ary])
    dp = [[float('inf')] * (xmax+1) for _ in range(n+1)]
    dp[0][0]= 0
    for i in range(n):
        for j in range(xmax+1):
            if j - ary[i][1] >= 0:
                dp[i+1][j] = min(dp[i+1][j] , dp[i][j-ary[i][1]] + ary[i][0])
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
w_v = [list(map(int,input().split())) for i in range(N)]
INF = float("inf")
dp = [[INF]*100001 for i in range(N+1)]
dp[0][0]=0

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

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
import sys
inf = 10**9+7
mod = 10**9+7
V = 10**5
n,W = map(int, input().split())
dp = [[inf for j in range(V+1)] for i in range(n+1)]
dp[0][0] = 0
for i in range(n):
    dp[i+1][0] = 0
    w,v = map(int, input().split())
    for j in range(V):
        if j+1-v >= 0:
            dp[i+1][j+1] = min(dp[i][j+1-v]+w, dp[i][j+1])
        else:
            dp[i+1][j+1] = min(dp[i][j+1], w)
for j in range(V+1):
    if dp[n][j] > W:
        print(j-1)
        sys.exit()
        break
print(V)

Submission status: Accepted

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

n, W = [int(x) for x in input().split()]
wv = [[int(x) for x in input().split()] for _ in range(n)]

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

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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')
dp = [[INF for j in range(V+1)] for i in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for sum_v in range(V+1):
        # i番目の品を取る
        if v[i] <= sum_v:
            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])

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

Submission status: Accepted

Solution code:
n, W = map(int, input().split())
w, v = [], []
inf = 10 ** 13
for _ in range(n):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
V = sum(v)

#dp[i][j] = i個までで価値jの重みの最小値
dp = [[inf for _ in range(V+1)] for _ in range(n+1)]
dp[0][0] = 0
for i in range(1, n+1):
    for j in range(V+1):
        if j >= v[i-1]:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j - v[i-1]] + w[i-1])
        else:
            dp[i][j] = dp[i-1][j]

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

Submission status: Accepted

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

dp = np.full(N * 1001, W + 10000)
dp[0] = 0

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

ans = np.max(np.where(dp <= W))
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())
    
INF = 10 ** 15
dp = [[INF]*(10**5+1) for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
    for sum_v in range(10**5+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]

max_v =0
for sum_v in range(10**5+1):
    if dp[n][sum_v] <= W:
        max_v = sum_v

print(max_v)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys
from collections import defaultdict


def solve(values, _nb, max_capacity):
    dp = {}
    dp[0] = 0
    for w, v in values:
        keys = sorted(dp.keys(), reverse=True)
        for vk in keys:
            if vk + v in dp:
                dp[vk + v] = min(dp[vk + v], dp[vk] + w)
            else:
                dp[vk + v] = dp[vk] + w
    result = 0
    for v, w in dp.items():
        if w <= max_capacity and v > result:
            result = v
    return result


def solve_better(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        # dp = dp[:w] + [max(dp[j], dp[j - w] + v) for j in range(w, max_capacity + 1)]
        dp[w:] = [max(dpj, dpjw + v) for dpj, dpjw in zip(dp[w:], dp[:-w])]
    return dp[max_capacity]


def solve_slow(values, nb, max_capacity):
    dp = [[0 for _ in range(max_capacity + 1)] for _ in range(nb + 1)]
    for i in range(1, nb + 1):
        w, v = values[i - 1]
        for j in range(1, max_capacity + 1):
            if w <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            else:
                dp[i][j] = dp[i - 1][j]
    # print("\n".join(map(str, dp)))
    return dp[nb][max_capacity]


def do_job():
    "Do the work"
    # first line is number of test cases
    N, W = map(int, input().split())
    values = []
    for _ in range(N):
        values.append(list(map(int, input().split())))
    result = solve(values, N, W)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Submission status: Accepted

Solution code:
INF = 10 ** 9 + 1
MAV_V = 10 ** 5 + 1

def main():
    N, W = map(int, input().split())
    dp = [[INF] * MAV_V for _ in range(N+1)]
    dp[0][0] = 0

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

    ans = [i for i, v in enumerate(dp[-1]) if v != INF]
    print(max(ans))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
INF = 10**12 + 5
MAV_V = 100001

def main():
    N, W = map(int, input().split())
    dp = [[INF] * MAV_V for _ in range(N+1)]
    dp[0][0] = 0

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

    ans = [i for i, v in enumerate(dp[-1]) if v != INF]
    print(max(ans))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np

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

dp = np.full(N * 1000 + 1, W + 1, dtype=np.int64)
dp[0] = 0

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

print(((dp <= W) * np.arange(N * 1000 + 1)).max())