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:
def knapsack(N,W,weight,value):
    inf=float("inf")
    V=sum(value)
    dp=[[inf for i in range(V+1)] for j in range(N+1)]
    dp[0][0]=0
    # dp[i][j]:i番目までの品物から価値がj以上になるよう選んだときの重さの総和の最小値
    for i in range(N):
        for j in range(V+1):
            if j-value[i]>=0: # i+1番目を選ぶ場合
                dp[i+1][j]=min(dp[i][j-value[i]]+weight[i], dp[i+1][j])
            # i+1番目を選ばない場合
            dp[i+1][j]=min(dp[i][j],dp[i+1][j])

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

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())
print(knapsack(n,w,weight,value))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,W = map(int,input().split())
weight = []
val = []
for i in range(n):
    a,b = map(int,input().split())
    weight.append(a)
    val.append(b)
max_v = sum(val) + 10 # 全部使ったとしてもこれ以上の勝ちにはならない
# point : v < =10^3 でn <= 10^2なので、n**2 vでもOK
# wが使えないときには変数を入れ替える
INF = 10**12+7 #Wより大きな値
dp = [[INF]*(max_v+1) for i in range(n+1)]
#初期化は 価値が0になる最小の重さが0なので、dp[i][0] = 0
# 漸化式：dp[i+1][j] = min(dp[i][j],dp[i][j-v[i]]+w[i])
# i+1　は i番目までの品物を使うとする
# 先にどっちからループを回した方が良い？価値か、品数か
#　品数が全部埋まってから、価値を更新する方が楽そう
for i in range(n+1):
    dp[i][0] = 0
for i in range(n):
    for j in range(max_v+1):
        if j-val[i] >= 0:
            #print("yes")
            dp[i+1][j] = min(dp[i][j],dp[i][j-val[i]]+ weight[i])
        else: dp[i+1][j] = dp[i][j]
    if i == n-1:
        #print("Yes")
        #print(dp[i+1])
        #大きい方から見ていく
        for j in range(max_v,-1,-1):
            #print(j)
            if dp[i+1][j] <= W:
                print(j)
                break

Submission status: Accepted

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

x = float("inf")

dp = [[x] * (100100) for i in range(110)]

dp[0][0] = 0
for i in range(n):
    for j in range(100100):
        if j - v[i] >= 0:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v[i]] + w[i])
        
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

ans = 0
for i in range(100100):
    if dp[n][i] <= ww:
        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)]
V = sum([v for _, v in wv])

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

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


def main():
    N, W = MI()
    V = 10 ** 3 * N
    dp = [IINF] * (V + 1)
    w = [0] * N
    v = [0] * N
    dp[0] = 0

    for i in range(N):
        w[i], v[i] = MI()

    for i in range(N):
        dp_next = [IINF] * (V + 1)
        for j in range(V+1):
            dp_next[j] = min(dp_next[j], dp[j])
            if j + v[i] <= V:
                dp_next[j+v[i]] = min(dp[j] + w[i], dp_next[j+v[i]])
        #     print(dp_next)
        # print('===========')
        dp = dp_next

    ans = 0
    for i in range(V+1):
        if dp[i] != IINF and dp[i] <= W:
            ans = i

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for i in range(N)]
DP = [[10**18 for i in range(10**5+1)] for j in range(N+1)]
for i in range(N+1):
  DP[i][0] = 0
for i in range(1,N+1):
  for j in range(1,10**5+1):
    DP[i][j] = min(DP[i][j],DP[i-1][j])
    if j-wv[i-1][1] >= 0:
      DP[i][j] = min(DP[i][j],DP[i-1][j-wv[i-1][1]]+wv[i-1][0])
for i in range(10**5+1):
  if DP[N][i] <= W:
    ans = i
print(ans)

Submission status: Accepted

Solution code:
# dp[i][j] := i番目までのitemを使って価値がj以下の時の最小の重み
N, W = map(int, input().split())
weight = []
value = []
for _ in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)
dp = [[10**12] * (sum(value)+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(sum(value)+1 - value[i]):
        # i番目のitemを使わない場合
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])  # 重みを最小にしたい
        # i番目のitemを使う場合
        dp[i+1][j+value[i]] = min(dp[i][j] + weight[i], dp[i+1][j+value[i]])  # 重みを最小にしたい

ans = 0
for j in range(sum(value)+1):
    if dp[N][j] > W:
        continue
    ans = max(ans, j)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #整数1つinput
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii())
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #文字列1つinput
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

n,w = mii()
wei=[]
val=[]
for i in range(n):
    ww,vv=map(int,input().split())
    wei.append(ww)
    val.append(vv)
#dp[i][j]:i番目まで選んで、価値がj以上となる最小の重さ
dp=[[10**10]*(sum(val)+1) for i in range(n+1)]
dp[0][0]=0
for i in range(n):
    for j in range(sum(val)+1):
        if j>=val[i]:
            dp[i+1][j]=min(dp[i][j-val[i]]+wei[i],dp[i][j])
        else:
            dp[i+1][j]=dp[i][j]
ans=[]
for i in range(sum(val)+1):
    if dp[n][i]<=w:
        ans.append(i)
print(max(ans))

Submission status: Accepted

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

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

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

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] >= 0:
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v[i]] + w[i])
		dp[i + 1][j] = min(dp[i + 1][j], dp[i][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())
K = 10**5
dp = [[10**100 for i in range(K+1)] for j in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    w,v = map(int,input().split())
    for j in range(K+1):
        dp[i][j] = dp[i-1][j]
        if j < v:
            continue
        else:
            dp[i][j] = min(dp[i-1][j-v] + w,dp[i-1][j])
for i in range(K+1):
    x = dp[N][-i-1]
    if x <= W:
        print(K-i)
        quit()

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

M=sum(v)
#i番目までの商品で価値の総和をjにしたときの重さ（W以下の範囲で）
dp=[[10**9]*(M+1) for _ in range(N+1)]

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

print(ans)

Submission status: Accepted

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

dp = np.full(N * max_V + 1, 10**10, dtype=np.int64)
dp[0] = 0
for w, v in WV:
    np.minimum(dp[v:], dp[:-v] + w, out=dp[v:])

dp[dp > W] = 0
ans = np.nonzero(dp)[0][-1]

print(ans)

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
data = []
v_sum = 0
inf = 10**12
for i in range(n):
    data.append(list(map(int, input().split())))
    v_sum += data[i][1]

dp = [[inf for i in range(v_sum+1)] for j in range(n+1)]
dp[0][0] = 0
for i in range(1,n+1):
    weight, v = data[i-1]
    for j in range(v_sum+1):
        if j - v >= 0:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-v] + weight)
        else:
            dp[i][j] = dp[i-1][j]
ans = 0
for i in range(v_sum+1):
    if dp[-1][i] <= w:
        ans = max(ans, i)
print(ans)

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().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 add_mod(a,b): return (a+b) % MOD

N,W = imn()
wv = [iln() for _ in range(N)]
max_v = 10**3*100+1
dp =[[10**10 for _ in range(max_v)] for _ in range(N+1)]
dp[0][0] = 0

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""


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

#L = sorted([list(map(int,input().split())) for i in range(N)])

M=int(sum(vi))
dp=[W+1]*(M+1)
dp[0]=0
   
#L = sorted([list(map(int,input().split())) for i in range(N)])
s=0

for w, v in zip(wi,vi):
    s+=v
    for j in range(min(s,M),v-1,-1):
        if dp[j] > dp[j-v]+w: dp[j]=dp[j-v]+w
    #print(dp)

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

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
WV = []
for i in range(N):
    WV.append(list(map(int,input().split())))
dp = [[float('inf') for j in range(100001)] for i in range(N)]
dp[0][0] = 0
for i in range(N):
    w,v = WV[i]
    if i == 0:
        dp[i][v] = w
    else:
        for j in range(100001):
            if j-v >= 0:
                dp[i][j] = min(dp[i-1][j-v]+w,dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]

ans = 0
for i,e in enumerate(dp[-1]):
    if W >= e:
        ans = i
print(ans)

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
dp=[[float('inf')]*(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-l[i-1][1]>=0:
      dp[i][j]=min(dp[i-1][j-l[i-1][1]]+l[i-1][0],dp[i][j])
    dp[i][j]=min(dp[i][j],dp[i-1][j])
for i in range(10**5+1):
  if w>=dp[n][10**5-i]:
    print(10**5-i)
    exit()

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().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点間の距離
MOD = 10**9+7

N,W = imn()
wv = [iln() for _ in range(N)]
max_v = 10**3*100+1

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

for i in range(N):
    for sum_v in range(max_v):
        if wv[i][1] <= sum_v: 
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v-wv[i][1]]+wv[i][0])
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])
ans = 0
for v in range(max_v):
    if dp[N][v] <= W: ans = v
print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
items = sorted([list(map(int, input().split())) for i in range(N)])
V = 10**5

dp = [[float("inf")]*(N + 1) for i in range(V + 1)]
dp[0] = [0]*(N + 1)
for i in range(V + 1):
    for j in range(N):
        k = i - items[j][1]
        dp[i][j + 1] = min(dp[i][j + 1], dp[i][j])
        if k < 0:
            break
        else:
            dp[i][j + 1] = min(dp[i][j + 1], dp[k][j] + items[j][0])

for i in range(V, -1, -1):
    for j in range(N + 1):
        if dp[i][j] <= W:
            print(i)
            exit()

Submission status: Accepted

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

N, W = list(map(int, input().split()))
item_list = []

for _ in range(N):
    w, v = list(map(int, input().split()))
    item_list.append((w, v))

max_v = (10 ** 3) * 100
dp_table = [[0] + [float("inf")] * (max_v + 1) for _ in range(N + 1)]
total_v = 0

for i in range(1, N + 1):  # 最大で10**2
    w, v = item_list[i - 1]
    # 品物iまで考慮したときの価値の最大値
    total_v += v
    for j in range(total_v + 1):  # 最大で10 ** 5
        # 品物iを入れない場合
        dp_table[i][j] = dp_table[i - 1][j]
        before_min_weight = dp_table[i - 1][j]
        # dp_table[i][j] = before_min_weight
        # 品物iを入れる場合
        if j - v < 0:
            continue
        weight = dp_table[i - 1][j - v] + w
        min_weight = min(before_min_weight, weight)
        dp_table[i][j] = min_weight
        if i == N:
            if min_weight <= W:
                max_value = j

ans = max_value
print(ans)

Submission status: Accepted

Solution code:
def solve():
    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 = [W+1] * (V + 1)
    dp[0] = 0
    for i in range(N):
        for j in range(V, -1, -1):
            if dp[j] + w[i] <= W:
                dp[j + v[i]] = min(dp[j + v[i]], dp[j] + w[i])
    
    for i in range(V, -1, -1):
        if dp[i] <= W:
            print(i)
            exit()


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
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)) #組み合わせの総数

N,W = imn()
max_v = 100001
wv = [iln() for _ in range(N)]
max_w = 10**10
dp = [[max_w for _ in range(max_v+1)] for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for sum_v in range(max_v):
        if sum_v - wv[i][1] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v-wv[i][1]]+wv[i][0])
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])

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

Submission status: Accepted

Solution code:
def solve(N, W, weight_values):
  sum_values = 0
  for w_v in weight_values:
    sum_values += w_v[1]

  # dp[i] maximum total weight with total value exactly i
  dp = [float('inf') for _ in range(sum_values + 1)]
  dp[0] = 0

  for i in range(N):
    i_weight, i_value = weight_values[i]
    for v in range(sum_values, i_value - 1, -1):
      temp = dp[v - i_value] + i_weight
      if temp < dp[v]:
        dp[v] = temp

  ans = 0
  for v in range(sum_values + 1):
    if dp[v] <= W:
      ans = max(ans, v)

  print(ans)

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


N, W = iln()
w_v = []
for i in range(N):
  w_v.append(iln())
  
solve(N, W, w_v)

Submission status: Accepted

Solution code:
import numpy as np

N,W = map(int,input().split())
item = []
V_MAX = 0
for _ in range(N):
    w, v = map(int,input().split())
    V_MAX += v
    item.append([w,v])
dp = np.array([float('inf')]*(V_MAX+1))
dp[0] = 0
pos = np.zeros(V_MAX+1, dtype = "int32")
pos[0] = 1
for w,v in item:
    dp = np.minimum(dp, np.concatenate([np.array([np.inf]*v),np.roll(dp,v)[v:]]) + np.dot(np.concatenate([np.zeros(v),np.roll(pos,v)[v:]]),w))
    pos = (pos + np.concatenate([np.zeros(v),np.roll(pos,v)[v:]]))
    pos[pos > 0] = 1
res = 0
for i in range(V_MAX + 1):
    if dp[i]<=W and res < i : res = i
print(res)

Submission status: Accepted

Solution code:
import numpy as np

N,W = map(int,input().split())
item = []
V_MAX = 0
for _ in range(N):
    w, v = map(int,input().split())
    V_MAX += v
    item.append([w,v])
dp = np.array([float('inf')]*(V_MAX+1))
dp[0] = 0
pos = np.array([0]*(V_MAX+1))
pos[0] = 1
for w,v in item:
    dp = np.minimum(dp, np.concatenate([np.array([np.inf]*v),np.roll(dp,v)[v:]]) + np.dot(np.concatenate([np.zeros(v),np.roll(pos,v)[v:]]),w))
    pos = (pos + np.concatenate([np.zeros(v),np.roll(pos,v)[v:]]))
    pos[pos > 0] = 1
res = 0
for i in range(V_MAX + 1):
    if dp[i]<=W and res < i : res = i
print(res)

Submission status: Accepted

Solution code:
#Educational DP Contest
#E-Knapsack2

#n = int(input())
N,W = map(int,input().split())
#lst1 = list(map(int,input().split()))

#dp table
#内側が価値v,外側がその品物をいれるかどうかのループを作る
#いきなりループに入れるように、内外共に0配列を余分に用意する
#価値vの総和はたかだか10*3*100=10**5なので、それだけ用意する
#なお、今回目指すのは価値の最大化ではなく、重さの最小化なので、infで初期化
dp = [[float("inf")]*(10**5+1) for _ in range(N+1)]
dp[0][0] = 0 #最小値を選んでいくため、0の初期化はここだけ

#process1
for i in range(1,N+1):
    w,v = map(int,input().split())
    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]


#output process
for i,j in enumerate(dp[-1]):
    if j <= W: #infの連続列の中に、たまにweightが紛れてる感じ
        ans = i
print(ans)

Submission status: Accepted

Solution code:
# E - Knapsack 2
from collections import defaultdict


def main():
    INF = 1 << 30
    N, W, *WV = map(int, open(0).read().split())
    dp = defaultdict(lambda: INF)  # dp[i] := minimum weight at value i
    dp[0] = 0
    for w, v in zip(*[iter(WV)] * 2):
        for cur_v, cur_w in tuple(dp.items()):
            if w + cur_w <= W:
                dp[v + cur_v] = min(dp[v + cur_v], w + cur_w)
    print(max(dp.keys()))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import unittest


class TestE(unittest.TestCase):
    def test_1(self):
        self.assertEqual(
            think(8, [[3, 30], [4, 50], [5, 60]]),
            90
        )

    def test_2(self):
        self.assertEqual(
            think(1000000000, [[1000000000, 10]]),
            10
        )

    def test_3(self):
        self.assertEqual(
            think(15, [[6, 5], [5, 6], [6, 4], [6, 6], [3, 5], [7, 2]]),
            17
        )


def solve():
    w, list_of_w_and_v = read()
    result = think(w, list_of_w_and_v)
    write(result)


def read():
    n, w = read_int(2)
    list_of_w_and_v = []
    for _ in range(n):
        list_of_w_and_v.append(read_int(2))
    return w, list_of_w_and_v


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


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


def think(w, list_of_w_and_v):
    w_max = 10 ** 9
    invalid = w_max + 1
    v_max = 10 ** 3
    n_max = 100

    # dp[value] = min weight at 'value'
    dp = [invalid for _ in range(v_max * n_max + 1)]
    dp[0] = 0

    for weight, value in list_of_w_and_v:
        for i in range(len(dp) - 1, -1, -1):
            if dp[i] == invalid:
                continue
            if i + value >= len(dp):
                continue
            dp[i + value] = min(
                    dp[i + value],
                    dp[i] + weight
            )

    for i in range(len(dp) - 1, -1, -1):
        if dp[i] == invalid:
            continue
        if dp[i] > w:
            continue
        return i


def write(result):
    print(result)


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Accepted

Solution code:
n=0
W=0
n,W=map(int,input().split())
dp=[W+1]*101010
dp[0]=0
for i in range(n):
    w,v=map(int,input().split())
    j=100000
    while j>=0:
        if dp[j+v]>dp[j]+w:
            dp[j+v]=dp[j]+w
        j-=1
ans=0
for v in range(len(dp)):
    if dp[v]<=W:
        ans=v
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N, W = map(int, input().split())
v_max = 10**3

dp = np.ones(v_max*N+1, dtype=int) * (10**9+1)
dp[0] = 0

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


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

Submission status: Accepted

Solution code:
import numpy as np
n, w = map(int, input().split())
v_max = 1000
num_v = v_max*n
INF = 10**9+1
dp = np.full(num_v+1, INF, dtype=int)
dp[0] = 0
for i in range(1,n+1):
  wn, vn = map(int, input().split())
  dp[vn:] = np.minimum(dp[vn:], dp[:-vn]+wn)
for i in range(len(dp)-1, -1, -1):
  if dp[i] <= w:
    print(i)
    break

Submission status: Accepted

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

INF = 10**15
dp = [INF for _ in range(10**5 + 1)] # dp[価値の総和]:= 重量の総和
dp[0] = 0

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

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

Submission status: Accepted

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

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

f_inf = float('inf')
max_v = 100000

dp = [f_inf]*(max_v+2)
dp[0] = 0

for i in range(1, n+1):
    for j in range(max_v+1, -1, -1):
        if j >= v[i-1]:
            dp[j] = min(dp[j], dp[j-v[i-1]]+w[i-1])

ans = 0
for i in range(max_v+1):
    if dp[i] <= max_w:
        ans = max(ans, i)
print(ans)

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
weight = []
value = []
for _ in range(n):
    wi, vi = map(int, input().split())
    weight.append(wi)
    value.append(vi)
weight.append(0)
value.append(0)
dp = [[float('inf')] * (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 - value[i] >= 0:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - value[i]] + weight[i])
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
for j in range(10 ** 5, -1, -1):
    if dp[n][j] <= w:
        print(j)
        break

Submission status: Accepted

Solution code:
def knapsack2(weight_value, w):
    v = sum(value for weight, value in weight_value)
    cur = [float("inf")] * (v + 1)
    cur[0] = 0

    for weight, value in weight_value:
        for i in reversed(range(value, v + 1)):
            cur[i] = min(cur[i], cur[i - value] + weight)

    for value in reversed(range(v + 1)):
        if cur[value] <= w:
            return value


def main():
    n, w = [int(x) for x in input().split()]
    weight_value = [None] * n
    for i in range(n):
        weight_value[i] = [int(x) for x in input().split()]
    return knapsack2(weight_value, w)


print(main())

Submission status: Accepted

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

dp = [[10**9]*(10**5+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(10**5+1):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        if dp[i][j] + lstW[i] <= W:
            dp[i+1][j+lstV[i]] = min(dp[i+1][j+lstV[i]], dp[i][j]+lstW[i])
ans = []
for i in range(max(lstV)*N+1):
    if dp[-1][i] <= W:
        ans.append(i)
print(max(ans))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    inf = W+1
    dp = [[inf] * (10**5+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        w, v = wv[i]
        for j in range(10**5+1):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if dp[i][j] + w <= W:
                dp[i+1][j+v] = min(dp[i+1][j+v], dp[i][j] + w)
    for v in range(10**5, -1, -1):
        if dp[-1][v] <= W:
            print(v)
            exit()


if __name__ == '__main__':
    main()

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)
dp = [[2**60]*(V+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V+1):
        if j - v[i] >= 0:
            dp[i+1][j] = min(dp[i][j],dp[i][j-v[i]]+w[i])
        else:
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])
ans = 0
for i in range(N+1):
    for j in range(V+1):
        if dp[i][j] <= W:
            ans = max(ans,j)
print(ans)

Submission status: Accepted

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