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())
wv = [[0 for i in range(2)] for j in range(N)]

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

dp = [[10**10 for i in range(10**5+100)] for j in range(150)]
dp[0][0] = 0

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

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

Submission status: Accepted

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

def main():
    N, W = tuple(map(int, input().rstrip().split()))
    A = tuple(tuple(map(int, input().rstrip().split())) for _ in range(N))
    lim = 10 ** 5
    dp = [0] + [float("inf")] * lim
    for i in range(N):
        for j in range(lim, A[i][1] - 1, -1):
            dp[j] = min(dp[j], dp[j - A[i][1]] + A[i][0])
    ans = [i for i, j in enumerate(dp) if j <= W]
    print(max(ans))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N, W = tuple(map(int, input().rstrip().split()))
    A = tuple(tuple(map(int, input().rstrip().split())) for _ in range(N))
    _, V = zip(*A)
    lim = 10 ** 5
    dp = [0] + [float("inf")] * lim
    for i in range(N):
        for j in range(lim, A[i][1] - 1, -1):
            dp[j] = min(dp[j], dp[j - A[i][1]] + A[i][0])
    ans = [i for i, j in enumerate(dp) if j <= W]
    print(max(ans))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N, W = tuple(map(int, input().rstrip().split()))
    A = tuple(tuple(map(int, input().rstrip().split())) for _ in range(N))
    _, V = zip(*A)
    lim = sum(V)  # the max value not considering weight
    dp = [0] + [float("inf")] * lim
    for i in range(N):
        for j in range(lim, A[i][1] - 1, -1):
            dp[j] = min(dp[j], dp[j - A[i][1]] + A[i][0])
    ans = [i for i, j in enumerate(dp) if j <= W]
    print(max(ans))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# dpE - Knapsack 2
import sys
input = sys.stdin.readline

def main():
    n, W = tuple(map(int, input().rstrip().split()))
    A = tuple(tuple(map(int, input().rstrip().split())) for _ in range(n))
    _, v = zip(*A)
    lim = sum(v)
    dp = [0] + [float("inf")] * lim
    for i in range(n):
        for j in range(lim, A[i][1] - 1, -1):
            dp[j] = min(dp[j], dp[j - A[i][1]] + A[i][0])
    ans = max(v for v, w in enumerate(dp) if w <= W)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
  n, w = [int(e) for e in input().split()]
  maxv = 10 ** 3 * n + 1
  t = [-1 for i in range(maxv)]
  t[0] = w
  cmaxv = 0
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(cmaxv, -1, -1):
      if t[i] == -1:
        continue
      if t[i + nv] < t[i] - nw:
        t[i + nv] = t[i] - nw
        if cmaxv < i + nv:
          cmaxv = i + nv
  print(cmaxv)
main()

Submission status: Accepted

Solution code:
def main():
  n, w = [int(e) for e in input().split()]
  maxv = 10 ** 3 * n + 1
  t = [-1 for i in range(maxv)]
  t[0] = w
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(maxv - 1, -1, -1):
      if t[i] == -1:
        continue
      if t[i + nv] < t[i] - nw:
        t[i + nv] = t[i] - nw
  for i in range(maxv - 1, 0, -1):
    if t[i] == -1:
      continue
    print(i)
    break
main()

Submission status: Accepted

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

# Wの最大が大きすぎて計算間に合わないので最大最小変換を行う
# dp[i+1][j]：i番目までのアイテムをナップザックに入れられるとき、価値がjとなる最小の重み
dp = [{} for i in range(N+1)]
dp[0][0] = 0


for i, (w,v) in enumerate(wv):
    for v0, w0 in dp[i].items(): # dictのキーと値に対してfor、i-1番目までのアイテムについて考える
        if v0 in dp[i+1]: # 
            dp[i+1][v0] = min(dp[i+1][v0], w0) # 同じ価値でさらに軽いものがある場合はそれを最小の重みに指定
        else:
            dp[i+1][v0] = w0 # 価値v0のものが今までのアイテムになければ、それを最小の重みに指定
        
        if w0+w > W: # 或る価値に対する最小重みに、現在のアイテムの重みを足して上限を超える場合は、今の価値についてそのアイテムは選択対象外
            continue # 
        if v0+v in dp[i+1]: # 今までの価値+新しく選んだものの価値 がi番目までのアイテムを選んだ時に既に存在する場合
            dp[i+1][v0+v] = min(dp[i+1][v0+v], w0+w)
        else:
            dp[i+1][v0+v] = w0+w


print(max(dp[-1].keys())) # 全部選んでいいときに価値として起こりうるものの最大

Submission status: Accepted

Solution code:
import numpy as np

n, ww = map(int, input().split())

s = np.full(1000*100+1, 10**11, dtype=np.int64)
s[0] = 0
for i in range(n):
    w, v = map(int, input().split())
    s[v:] = np.minimum(s[v:], s[:-v] + w)

print(np.max(np.where(s<=ww)))

Submission status: Accepted

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

max_v = 100005

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

for i in range(n):
    for sum_v in range(max_v):
        if sum_v - item[i][1] >= 0:
            dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v - item[i][1]] + item[i][0])
        dp[i + 1][sum_v] = min((dp[i + 1][sum_v], dp[i][sum_v]))

for sum_v in reversed(range(max_v)):
    if dp[-1][sum_v] <= w:
        print(sum_v)
        break

Submission status: Accepted

Solution code:
def solve():
    max_weight, list_of_weight_and_value = read()
    result = think(max_weight, list_of_weight_and_value)
    write(result)


def read():
    n, max_weight = read_int(2)
    list_of_weight_and_value = []
    for i in range(n):
        list_of_weight_and_value.append(read_int(2))
    return max_weight, list_of_weight_and_value


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(max_weight, list_of_weight_and_value):
    MAX_WEIGHT = 10 ** 9
    MAX_VALUE = 10 ** 3
    MAX_N = 100
    INVALID_VALUE = MAX_WEIGHT * MAX_N + 1

    # dp[v] means minimum weight achieves total value 'v'
    dp = [INVALID_VALUE for x in range(MAX_VALUE * len(list_of_weight_and_value) + 1)]
    dp[0] = 0

    for weight, value in list_of_weight_and_value:
        for i in range(len(dp) - 1, -1, -1):
            if dp[i] != INVALID_VALUE and i + value < len(dp):
                if dp[i + value] == INVALID_VALUE:
                    dp[i + value] = dp[i] + weight
                else:
                    dp[i + value] = min(dp[i + value], dp[i] + weight)
    for i in range(len(dp) - 1, -1, -1):
        if dp[i] != INVALID_VALUE and dp[i] <= max_weight:
            return i


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def number():
    return int(input())


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


def seq_space(n):
    return [list(map(int, input().split())) for _ in range(n)]


N, W = space()
WV = seq_space(N)

V = N*1000+1
DP = [float('inf')] * V
DP[0] = 0

for i in range(N):
    w, v = WV[i]
    for j in range(V-1, v-1, -1):
        DP[j] = min(DP[j-v]+w, DP[j])

for i in range(V-1, -1, -1):
    if DP[i] <= W:
        print(i)
        exit()

Submission status: Accepted

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

DP = [[float("inf")]*(N*(10**3)+1)for i in range(N+1)]
DP[0][0] = 0
for i in range(N):
    w,v = wv[i]
    for j in range(N*10**3+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)
ans = 0

for i in range(N*10**3+1):
    if DP[-1][i] <= W:
        ans = i
print(ans)

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
wv=[]
m=1
for i in range(n):
    p=[int(j) for j in input().split()]
    wv.append(p)
    m+=p[1]

dp=[10**100 for i in range(m)]
dp[0]=0

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

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

Submission status: Accepted

Solution code:
import numpy as np

N, W = map(int, input().split())
inputs = np.array([np.array([int(i) for i in input().split()]) for _ in range(N)])

dp = np.full(N*1000+1, 10 ** 10, dtype=np.int64)
dp[0] = 0
for n in range(1, N+1):
    weight, value = inputs[n-1][0], inputs[n-1][1]
    dp[value:] = np.minimum(dp[value:], dp[:-value] + weight)

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

Submission status: Accepted

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

INF = float("inf")
dp = [INF] * (10 ** 5 + 1)
dp[0] = 0

mv = 0
for m, v in Ls:
    mv += v
    for i in range(mv, v - 1, -1):
        dp[i] = min(dp[i], dp[i - v] + m)

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

Submission status: Accepted

Solution code:
import math
import sys

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

items= [list(map(int, sys.stdin.readline().split()) )for _ in range(N)]
s  =0
for i in range(N):
    s += items[i][1]
INF = 10 **15
dp = [[ INF for _ in range(s +1)] for _ in range(N + 1) ]
#dp[今何個目か][価値] = その時の重さの最小値 重さの最小値がW以下の中で価値最大を出力
dp[0][0] = 0

for j in range(N):  # j 個目の荷物で
    for i in range(s + 1): # 価値

        w,v = items[j]
        if i >= v:
        #遷移 d[j + 1][i] =  (d[j][i - v] + w ) 新しい荷物を選んだ場合
            dp[j + 1 ][i] = dp[j][i - v]  + w  # dp[j][i - w]  + v → j 個持ったところに、更に 価値v のitemが追加されて j+ 1になった
        dp[j + 1][i] =  min(dp[j + 1][i] ,dp[j][i]) #選ばなかった場合
ans = 0
for i in range(s + 1): #価値i
    for j in range(N + 1):  # j 個目の荷物で
        if dp[j][i] <= W:
            ans = max(i,ans)

print(ans)

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
dp=[[100000000001]*100001for _ in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
  a,b=map(int,input().split())
  for j in range(100001):
    if j>=b:dp[i][j]=min(dp[i-1][j],dp[i-1][j-b]+a)
    else:dp[i][j]=dp[i-1][j]
i=10**5
while dp[n][i]>w:i-=1
print(i)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
L = []
for _ in range(N):
    A,B = map(int,input().split())
    L.append((A,B))

dp = [[10**12+1 for i in range(10 ** 5 + 100)] for i in range(N + 10)]

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


for j in reversed(range(10** 5 + 10)):
    if dp[N][j] != 10**12 + 1:
        print(j)
        quit()

Submission status: Accepted

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

IN = list(list(map(int, input().split())) for _ in range(N))
sumw = 0
sumv = 0
for w, v in IN:
    sumw += w
    sumv += v

DP = dict()
DP[sumv] = sumw

def minv(i, v):
    if not DP.get(i):
        DP[i] = v
    else:
        if v < DP[i]:
            DP[i] = v

for w, v in IN:
    DPpre = DP.copy()
    for i in DPpre:
        minv(i-v, DPpre[i]-w)

for v in sorted(DP, reverse=True):
    if DP[v] <= W:
        print(v)
        break

Submission status: Accepted

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

IN = list(list(map(int, input().split())) for _ in range(N))
sumw = 0
sumv = 0
for w, v in IN:
    sumw += w
    sumv += v

DP = dict()
DP[sumv] = sumw

def minv(i, v):
    if not DP.get(i):
        DP[i] = v
    else:
        if v < DP[i]:
            DP[i] = v

if sumw <= W:
    ans = sumv
else:
    ans = 0
    for w, v in IN:
        DPpre = DP.copy()
        for i in DPpre:
            answ = i - v
            minv(answ, DPpre[i]-w)
            if answ > ans:
                if DP[answ] <= W:
                    ans = answ
                    continue

print(ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n, w = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(n)]

    sum_value = sum([v for (_, v) in wv])

    dp = [[10**9 + 7 for _ in range(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 >= wv[i][1]:
                dp[i + 1][j] = min(dp[i][j - wv[i][1]] + wv[i][0], dp[i][j])
            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())
weight = []
value = []

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



#dp[i][j] i番目までの品物から価値がjを達成するように選んだときの重さの最小値を保存
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):
        # j -> now value
        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())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

INF = 10 ** 10
dp = [[INF] * (10**5+1) for i 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+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])

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

print(res)

Submission status: Accepted

Solution code:
N, maxW = map(int, input().split())
maxV = 10**3*100
dp = [[float('inf') for i in range(maxV+1)] for j in range(N+1)]
W = [0 for i in range(N+1)]
V = [0 for i in range(N+1)]
for i in range(1, N+1):
    W[i], V[i] = map(int, input().split())

nv = 0
nw = 0
dp[0][0] = 0
for i in range(1, N+1):
    for v in range(maxV+1):
        dp[i][v] = min(dp[i-1][v], dp[i][v])
        nv = v + V[i]
        if nv <= maxV:
            dp[i][nv] = dp[i-1][v] + W[i]
ans = 0
for v in range(maxV, -1, -1):
    if maxW >= dp[N][v]:
        ans = v
        break

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def main():
	N, W = map(int, input().split())
	wv = []
	for i in range(N):
		w, v = map(int, input().split())
		wv.append((w,v))
		
	DP = [[1000000000000000000000000 for _ in range(100001)] for _ in range(N)]
	
	for i, val in enumerate(wv):
		w, v = val
		if i == 0:
			DP[i][v] = w
			DP[i][0] = 0
			continue
		
		for j in range(100001):
			DP[i][j] = min(DP[i][j], DP[i-1][j])
			if j+v < 100001:
				DP[i][j+v] = min(DP[i][j+v], DP[i-1][j] + w)
				
	ans = -1
	for i, val in enumerate(DP[N-1]):
		if val <= W:
			#print("{} {}".format(val, i))
			if ans == -1 or ans < i:
				ans = i
		
	print(ans)
	#print(DP[N-1][0])
	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
# Educational DP Contest E-knapsack 2


N,W=list(map(int,input().split()))
items=[]
for _ in range(N):
    w,v=list(map(int,input().strip().split()))
    items+=[(w,v)]
    
MAX_val=N*10**3+1 # 最大の価値
dp=[[10**9+1]*MAX_val for i in range(N)] # 最大の価値でinitialize(価値の表）
dp[0][items[0][1]]=items[0][0] # 最初の品物の価値の場所に、最初の品物の重さを入れる
for i in range(1,N):
    for val in range(1,MAX_val):
        if val-items[i][1]>0: # アイテムの価値がvalを上回っていた場合
            dp[i][val]=min(dp[i-1][val],dp[i-1][val-items[i][1]]+items[i][0])
        elif val==items[i][1]: # アイテムの価値がvalと同様の場合
            dp[i][val]=min(items[i][0],dp[i-1][val])
        dp[i][val]=min(dp[i][val],dp[i-1][val])

MAX=0
for i in range(len(dp[-1])): # dpの最終行の数を調べて、最もWに近いものを出力
    if dp[-1][i]<=W:
        #print(i)
        MAX=i
print(MAX)

Submission status: Accepted

Solution code:
n,w = map(int, input().split())
l = [tuple(map(int, input().split())) for _ in range(n)]
inf = float("inf")
dp = [inf]*(10**5+1)
dp[0] = 0
mv = 0
for x,v in l:
  mv += v
  for i in range(mv,v-1,-1):
    dp[i] = min(dp[i],dp[i-v]+x)
    
for i in range(mv,-1,-1):
  if dp[i]<=w:
    print(i)
    break

Submission status: Accepted

Solution code:
n,w = map(int,input().split())

lis = [list(map(int,input().split())) for i in range(n)]
lis.sort(key = lambda x:x[1])

dp = {0:0}

for weight ,value in lis:
    gone = dp.copy()
    for key in dp:
        gone[key+value] = min(dp[key] + weight, dp.get(key+value, float("inf")))
    dp = gone
for key in sorted(dp.keys(), reverse = True):
    if dp[key] <= w:
        print(key)
        exit()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    n, w = map(int, input().split())
    ws = [0 for _ in range(n)]
    vs = [0 for _ in range(n)]
    inf = 10 ** 12
    dp = [[inf for _ in range(((n + 1) * 10 ** 3) + 1)] for _ in range(n + 1)]

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

    dp[0][0] = 0

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

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

    ans = 0

    for index, d in enumerate(dp[n]):
        if d <= w:
            ans = index

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,W = inpl()
wvs = [inpl() for _ in range(N)]
dp = [INF]*(10**5+5)
dp[0] = 0

for w,v in wvs:
    for i in reversed(range(10**5+5)):
        dp[i] = min(dp[i-v] + w,dp[i])
        if i == v:
            break
ans = 0
for i in range(10**5+5):
    if dp[i] <= W:
        ans = i

print(ans)

Submission status: Accepted

Solution code:
N,W=list(map(int,input().strip().split(" ")))
items=[]
for _ in range(N):
    w,v=list(map(int,input().strip().split(" ")))
    items+=[(w,v)]

MAX_val=N*10**3+1
dp=[[10**9+1]*MAX_val for i in range(N)]
dp[0][items[0][1]]=items[0][0]
for i in range(1,N):
    for val in range(1,MAX_val):
        if val-items[i][1]>0:
            dp[i][val]=min(dp[i-1][val],dp[i-1][val-items[i][1]]+items[i][0])
        elif val==items[i][1]:
            dp[i][val]=min(items[i][0],dp[i-1][val])
        dp[i][val]=min(dp[i][val],dp[i-1][val])

MAX=0
for i in range(len(dp[-1])):
    if dp[-1][i]<=W:
        #print(i)
        MAX=i
print(MAX)

Submission status: Accepted

Solution code:
from __future__ import division, print_function
def main():
    dp=[10**18]*(10**5+1)
    dp[0]=0
    n,w=map(int,input().split())
    l1=[]
    s=0
    for _ in range(n):
        l1.append(list(map(int,input().split())))
        s+=l1[_][1]
    for i in range(n):
        for j in range(s,l1[i][1]-1,-1):
            dp[j]=min(dp[j],dp[j-l1[i][1]]+l1[i][0])
    for j in range(10**5,-1,-1):
        if dp[j]<=w:
            print(j)
            sys.exit()


######## Python 2 and 3 footer by Pajenegod and c1729

# Note because cf runs old PyPy3 version which doesn't have the sped up
# unicode strings, PyPy3 strings will many times be slower than pypy2.
# There is a way to get around this by using binary strings in PyPy3
# but its syntax is different which makes it kind of a mess to use.

# So on cf, use PyPy2 for best string performance.

py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
sys.setrecursionlimit(10**5)
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'

# Read all remaining integers in stdin, type is given by optional argument, this is fast
def readnumbers(zero = 0):
    conv = ord if py2 else lambda x:x
    A = []; numb = zero; sign = 1; i = 0; s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'0' [0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-' [0]: sign = -1
            elif s[i] != b'\r' [0]:
                A.append(sign*numb)
                numb = zero; sign = 1
            i += 1
    except:pass
    if s and s[-1] >= b'0' [0]:
        A.append(sign*numb)
    return A

if __name__== "__main__":
  main()

Submission status: Accepted

Solution code:
# @author 

import sys

class EKnapsack2:
    def solve(self):
        n, W = [int(_) for _ in input().split()]
        w = [0] * (n + 1)
        v = [0] * (n + 1)
        for i in range(1, n + 1):
            w[i], v[i] = [int(_) for _ in input().split()]

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

        for ve in range(V + 1):
            dp[0][0] = 0
            for k in range(1, n + 1):
                dp[ve][k] = dp[ve][k - 1]
                if ve >= v[k]:
                    dp[ve][k] = min(dp[ve][k], dp[ve - v[k]][k - 1] + w[k])

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

        print(ans)

solver = EKnapsack2()
input = sys.stdin.readline

solver.solve()

Submission status: Accepted

Solution code:
inf = float('inf')

N,W = map(int,input().split())
w, v = [], []
for _ in range(N):
    wi, vi = map(int,input().split())
    w.append(wi)
    v.append(vi)

M = sum(v)

dp = [[inf]*(M+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(1,N+1):
    for j in range(M+1):
        if j - v[i-1] >= 0:
            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 j in range(M+1)[::-1]:
    if dp[N][j] <= W:
        ans = j
        break

print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
INF = float('inf')
weight = [0] * N
value = [0] * N
Max_v = 0
for i in range(N):
    w, v = map(int, input().split())
    weight[i], value[i] = w, v
    Max_v += v

dp = [[INF]*(Max_v+1) for _ in range(N)]
# dp[i][vs] : i番目までの品物から総価値がvs以上になるように選んだ時の総重量の最小値

for i in range(0, value[0]+1):
    dp[0][i] = weight[0] if i else 0

for i in range(1, N):
    for vs in range(Max_v+1):
        if vs - value[i] >= 0:
            dp[i][vs] = dp[i-1][vs - value[i]] + weight[i]
        else:
            dp[i][vs] = weight[i]
        dp[i][vs] = min(dp[i][vs], dp[i-1][vs])

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

Submission status: Accepted

Solution code:
# import numpy as np
#
# N, W = map(int, input().split())
#
# dp = np.zeros(W+1, dtype=np.int64)
#
# for _ in range(N):
#     w, v = map(int, input().split())
#     np.maximum(dp[:-w]+v, dp[w:], out=dp[w:])
#
# print(dp[-1])


import numpy as np

N, W = map(int, input().split())
dp = np.full(N * 1000 + 1, 10 ** 10, dtype=np.int64)
# print(dp)
# print(len(dp))
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())

Submission status: Accepted

Solution code:
import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, log2, factorial

sys.setrecursionlimit(1000000)
# MOD = 10 ** 9 + 7
# INF = float('inf')
# N = int(input())
# A = [int(x) for x in input().split()]
# A = [int(input()) for _ in range(N)]
# dp = [[0] * 100 for _ in range(100)]
# dp = defaultdict(lambda: float('inf'))

N, W = [int(x) for x in input().split()]

dp = defaultdict(lambda: float('inf'))
dp[0] = 0

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

    add = defaultdict(lambda: float('inf'))
    for vv in list(dp.keys()):
        if dp[vv + v] > dp[vv] + w:
            add[vv + v] = dp[vv] + w
    dp.update(add)

print('hoge', file=sys.stderr)

print(max(filter(lambda i: i[1] <= W, dp.items()), key=lambda x:x[0])[0])

Submission status: Accepted

Solution code:
import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, log2, factorial
from pprint import pprint

sys.setrecursionlimit(1000000)
# MOD = 10 ** 9 + 7
# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

N, W = [int(x) for x in input().split()]

dp = defaultdict(lambda: float('inf'))
dp[0] = 0

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

    add = defaultdict(lambda: float('inf'))
    for vv in list(dp.keys()):
        if dp[vv + v] > dp[vv] + w:
            add[vv + v] = dp[vv] + w
    dp.update(add)

print(max(filter(lambda i: i[1] <= W, dp.items()), key=lambda x:x[0])[0])

Submission status: Accepted

Solution code:
import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, log2, factorial
from pprint import pprint

sys.setrecursionlimit(1000000)
# MOD = 10 ** 9 + 7
# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

N, W = [int(x) for x in input().split()]

dp = [float('inf')] * 1000 * 100*10
vs = set()
vs.add(0)
dp[0] = 0

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

    tmpDP = dp.copy()
    for vv in list(vs):
        if dp[vv + v] > dp[vv] + w:
            tmpDP[vv + v] = dp[vv] + w
            vs.add(vv + v)
    dp = tmpDP


ans = 0
for v in list(vs):
    if dp[v] <= W:
        ans = max(ans, v)
print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
weight = []
value = []
for _ in range(N):
    w_tmp, v_tmp = map(int, input().split())
    weight.append(w_tmp)
    value.append(v_tmp)

INF = float('inf')

dp = [[INF 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 - value[i]] + weight[i], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

for j in range(sum(value)+1):
    if dp[N][j] <= W:
        res = j

print(res)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for x in range(N)]
ws = [x[0] for x in wv]
vs = [x[1] for x in wv]

# # depthまでの荷物で、value以上になる重さの最小
dp = [[None] * (sum(vs) + 1) for _ in range(N + 1)]
# def dfs(value=0, depth=N - 1):
#     if value <= 0:
#         return 0
#
#     if depth == -1:
#         return float("inf")
#
#     if dp[depth][value] is not None:
#         return dp[depth][value]
#
#     weight = min(dfs(value, depth - 1), dfs(value - vs[depth], depth - 1) + ws[depth])
#     dp[depth][value] = weight
#     return weight
#
# for i in range(sum(vs) + 1):
#     if dfs(i) > W:
#         print(i - 1)
#         break
# else:
#     print(i)

dp[-1] = [float("inf")] * len(dp[-1])
s = sum(vs)
for depth in range(N):
    for value in range(s + 1):
        if value - vs[depth] >= 0:
            dp[depth][value] = min(dp[depth - 1][value], dp[depth - 1][value - vs[depth]] + ws[depth])
        else:
            dp[depth][value] = min(dp[depth - 1][value], ws[depth])


import bisect
print(bisect.bisect_left(dp[N - 1], W + 1))

Submission status: Accepted

Solution code:
N, W = [int(i) for i in input().split()]
w, v = [0]*N, [0]*N
 
for i in range(N):
  w[i], v[i] = [int(_) for _ in input().split()]
V = sum(v)
 
dp = [[float('inf')] * (V+1) for _ in range(N+1)]
# dp[i][j] i番目までの荷物で価値がj以上になるように選んだときの重さの最小値
dp[0][0] = 0
for i in range(N):
  for j in range(V+1):
    if v[i] <= j:# 荷物v[i]の価値がjに足りてないので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 j in range(V + 1):
  if dp[N][j] <= W:
    ans = j    
      
print(ans)