Problem:


Score : 100 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

1 \leq N \leq 100

1 \leq W \leq 10^9

1 \leq w_i \leq W

1 \leq v_i \leq 10^3

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

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

Sample Input 1

3 8
3 30
4 50
5 60

Sample Output 1

90

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

Sample Input 2

1 1000000000
1000000000 10

Sample Output 2

10

Sample Input 3

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

Sample Output 3

17

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



Sample input:
3 8
3 30
4 50
5 60


Sample output:
90

Submission status: Accepted

Solution code:
import 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 m_add(a,b): return (a+b) % MOD

N,W = imn()
wv = [iln() for _ in range(N)]
maxv = 100 * 1000 + 1

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

dp[0][0] = 0

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

Submission status: Accepted

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

dp = [[10**12]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
# dp[i][j]:i番目以前の商品を見たときの価値総和jとしたときの重さの最小値

ans = 0
for i in range(1,N+1):
    for j in range(V+1): # なんか間違えて1スタートにしててハマった
        if v[i] <= j: #v[i]が入るとjになるときの計算なので，v[i]がjよりでかいのはあり得ない。j-v[i]>0だしね。
            # i-1番目までの商品で価値jの場合とi番目の商品を入れて価値jの場合の比較
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i]] + w[i])
        else:
            dp[i][j] = dp[i-1][j]


for j in range(V+1):
    if dp[N][j] <= W:
        ans = max(ans, j)

print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
dp = [10**9+7] * (10**5+2)
dp[0] = 0

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

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

print(ret)

Submission status: Accepted

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

MAX_V = N * (10 ** 3)
wv = [list(map(int, input().split())) for _ in range(N)]

dp = [10**9+7 for _ in range(MAX_V + 1)]
dp[0] = 0

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

mv = 0
for i in range(MAX_V + 1):
    if dp[i] <= W:
        mv = i

print(mv)

Submission status: Accepted

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

MAX_V = N * (10 ** 3)
w, v = [], []
for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

dp = [10**9+7 for _ in range(MAX_V + 1)]
dp[0] = 0

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

mv = 0
for i in range(MAX_V + 1):
    if dp[i] <= W:
        mv = i

print(mv)

Submission status: Accepted

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

MAX_V = N * (10 ** 3)
w, v = [], []
for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

dp = [10**9+7 for _ in range(MAX_V + 1)]
dp[0] = 0

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

mv = 0
for i in range(MAX_V + 1):
    if dp[i] <= W:
        mv = i

print(mv)

Submission status: Accepted

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

MAX_V = N * (10 ** 3)
w, v = [], []
for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

dp = [[10**9+7 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):
        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] = dp[i][j]

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

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,w = get_nums_l()
ppp = list(map(lambda s: tuple(map(int,s.strip().split())), sys.stdin.readlines()))

# dp[i] = 価値iを得られる最小の重さ
dp = [9999999999999999999] * (n*1000+1)
dp[0] = 0

for p in ppp:
    we = p[0]
    va = p[1]
    for i in reversed(range(len(dp))):
        if i+va >= len(dp):
            continue
        ne = i+va
        dp[ne] = min(dp[ne], dp[i]+we)

# log(dp)

for i,we in reversed(list(enumerate(dp))):
    if we <= w:
        print(i)
        exit()

Submission status: Accepted

Solution code:
def main():

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

    INF = 10 ** 20
    dp = [INF] * (n * 100001)
    dp[0] = 0

    max_vi = 0
    for _ in range(n):
        wi, vi = map(int, input().split())
        max_vi += vi

        for vj in range(max_vi + 1, vi - 1, -1):
            nw = dp[vj - vi] + wi
            if dp[vj] > nw:
                dp[vj] = nw

    for i in range(max_vi, -1, -1):
        if dp[i] <= w:
            print(i)
            return

main()

Submission status: Accepted

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

MAX_V = N * (10 ** 3)
w, v = [], []
for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

# dp[in_n_items][above_v_value] = min_weight
dp = [[float('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):
        if j - v[i] >= 0:
            if dp[i][j - v[i]] + w[i] < dp[i][j]:
                dp[i + 1][j] = dp[i][j - v[i]] + w[i]
            else:
                dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = dp[i][j]

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

Submission status: Accepted

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

from collections import defaultdict

dp = defaultdict(lambda : 10**100)
dp[0] = 0
for w, v in WV:
  ndp = defaultdict(lambda : 10**100)
  for k in dp:
    ndp[k] = min(dp[k], ndp[k])
    if dp[k] + w <= W:
   	  ndp[k+v] = min(dp[k] + w, ndp[k+v])
  dp = ndp
print(max(dp.keys()))

Submission status: Accepted

Solution code:
def main():
    #1:初期化
    N,W = map(int,input().split())
    dp = [W+1]*(N*10**3+1)

    #2:初期値
    dp[0] = 0

    #3:dp実行部(貰うDP)
    for i in range(N):
        w, v = map(int,input().split())
        for i in range(N*10**3, v-1, -1):
            tmp = dp[i-v] + w
            if dp[i] > tmp:
                dp[i] = tmp
        #print(dp,sep="\n")

    #4:出力
    output = 0
    for i in range(N*10**3+1):
        if dp[i] <= W:
            output = i
    print(output)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

import numpy as np

INF = 10 ** 18

N, W = map(int, input().split())
lst = np.array([0] + [INF] * (10 ** 5 + 9), dtype = np.int64)
for _ in range(N):
    w, v = map(int, input().split())
    lst[v:] = np.minimum(lst[v:], lst[:10 ** 5 + 10 -v] + w)
    lst[1:v] = np.minimum(lst[1:v], w)

# print (lst[:10])
for i in range(10 ** 5 + 9, -1, -1):
    if lst[i] <= W:
        print (i)
        exit()

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
import copy
input = sys.stdin.readline
INF = 10**9+7
N, W = map(int, input().split())
weight = []
value = []
for i in range(N):
    tempW, tempV = map(int, input().split())
    weight.append(tempW)
    value.append(tempV)

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

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
import copy
INF = float("inf")
N, W = map(int, input().split())
weight = []
value = []
for i in range(N):
    tempW, tempV = map(int, input().split())
    weight.append(tempW)
    value.append(tempV)

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

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
import copy
input = sys.stdin.readline
INF = float("inf")
N, W = map(int, input().split())
weight = []
value = []
for i in range(N):
    tempW, tempV = map(int, input().split())
    weight.append(tempW)
    value.append(tempV)

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

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
import copy

INF = 10 ** 9 + 7
N, W = map(int, input().split())
weight = []
value = []
for i in range(N):
    tempW, tempV = map(int, input().split())
    weight.append(tempW)
    value.append(tempV)

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

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

Submission status: Accepted

Solution code:
INF = float('inf')
MAX_N = 110
MAX_V = 100100

# input
N, W = map(int, input().split())
weight, value = [0]*N, [0]*N

for i in range(N):
    tmp_w, tmp_v = map(int, input().split())
    weight[i] = tmp_w
    value[i] = tmp_v

dp = [[INF for _ in range(MAX_V)] for _ in range(MAX_N)]
dp[0][0] = 0


for i in range(N):
    for sum_v in range(MAX_V):
        # i番目の品物を選ぶ場合
        if sum_v - value[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - value[i]] + weight[i])
        # i番目の品物を選ばない場合
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])


answer = 0
for sum_v in range(MAX_V):
    if dp[N][sum_v] <= W:
        answer = sum_v

print(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,w=map(int,input().split())
WV=[tuple(map(int,input().split())) for i in range(n)]
dp=[inf]*(10**5+1); dp[0]=0
for i in range(n):
  wi,vi = WV[i]
  for di in range(10**5,-1,-1):
    if not (0<=di-vi<10**5+1): continue
    # if dp[di-vi]==-1: continue
    dp[di]=min(dp[di],dp[di-vi]+wi)
for i,di in enumerate(dp):
  if di <= w:
    ans = max(ans,i)
# print(dp[:110])
print(ans)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
INF = 10**9+7
NV = (10**3)*N
dp = [[INF for j in range(NV+1)] for i 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(NV+1):
        if j < v:
            dp[i][j] = min(dp[i-1][j], w)
        else:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-v]+w)
ans = 0
for j in range(NV+1):
    if dp[N][j] <= W:
        ans = j
print(ans)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
INF = 10**9+7
NV = (10**3)*N
dp = [[0]+[INF for j in range(NV)] for i in range(N+1)]

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

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

Submission status: Accepted

Solution code:
import sys

N, W = map(int, input().split())
WEIGHTS = list(list(map(int, input().split())) for _ in range(N))
M = len(WEIGHTS)
MAX_VALUE = sum(value for (weight, value) in WEIGHTS)

INF = sys.maxsize
DP = [[INF for _ in range(MAX_VALUE + 1)] for _ in range(M + 1)]

for i, (weight, value) in enumerate(WEIGHTS):
    for v in range(MAX_VALUE + 1):
        if v - value >= 0:
            DP[i+1][v] = min(DP[i][v - value] + weight, DP[i][v])
        else:
            DP[i+1][v] = min(DP[i][v], weight)

res = 0
for v, w in enumerate(DP[M]):
    if w <= W:
        res = max(res, v)

print(res + 1)

# dp_ij := 1~jまでのアイテムからいくつかを選んで総価値iを超えないようにしたときの最少重量

Submission status: Accepted

Solution code:
import sys

N, W = map(int, input().split())
WEIGHTS = list(list(map(int, input().split())) for _ in range(N))
M = len(WEIGHTS)
MAX_VALUE = sum(value for (weight, value) in WEIGHTS)

INF = sys.maxsize
DP = [[INF for _ in range(MAX_VALUE + 1)] for _ in range(M + 1)]

for i, (weight, value) in enumerate(WEIGHTS):
    for v in range(MAX_VALUE + 1):
        if v - value >= 0:
            DP[i+1][v] = min(DP[i][v - value] + weight, DP[i][v])
        else:
            DP[i+1][v] = min(DP[i][v], weight)

res = 0
for v, w in enumerate(DP[M]):
    if w <= W:
        res = max(res, v)

print(res + 1)

Submission status: Accepted

Solution code:
# E - Knapsack 2
N,W=map(int,input().split())
w,v=[],[]
inf=10**10
for i in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
L = 100000
dp = [[1000000001 for _ in range(L+1)] for _ in range(N+1)]
W, V = [], []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
dp[0][0] = 0
for i in range(N):
    for j in range(L+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] = dp[i][j]
for i, d in enumerate(dp[N]):
    if d <= M:
        maxv = i
print(maxv)

Submission status: Accepted

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

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



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

    dp = dp[N]
    for i in reversed(range(MV)):
        if dp[i] <= W:
            print(i)
            exit()
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
# E - Knapsack 2

N, W = map(int, input().split())
knapsack_list = []
value_max = 0
max_cost = 0
for i in range(N):
    knap =  list(map(int, input().split()))
    knapsack_list.append(knap)
    value_max = value_max + knap[1]

cost_list = [[10**12]*(value_max+1) for _ in range(N+1)]

cost_list[0][0] = 0
for i in range(N):
    cost_list[i+1][0] = 0
    weight = knapsack_list[i][0]
    value = knapsack_list[i][1]
    for j in range(value_max+1):
        if j<value:
            cost_list[i+1][j] = cost_list[i][j] # そのまま遷移させる
            continue
        new_cost = cost_list[i][j-value] + weight
        new_cost = min(cost_list[i][j], new_cost)
        cost_list[i+1][j] = new_cost # 次の遷移状態へコストを渡す

for i in range(value_max+1):
    weight = cost_list[N][i]
    if weight<=W:
        max_cost = i

print(max_cost)

Submission status: Accepted

Solution code:
# 1つづつ順に
# V << W なので、 dp[N][W]ではなく、 dp[N][V]で作成
def resolve():
    N, W = map(int, input().split())
    w_l = []
    v_l = []
    for _ in range(N):
        w, v = map(int, input().split())
        w_l.append(w)
        v_l.append(v)

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

    for i in range(N):
        for j in range(max_v):
            #print(i, j)
            w = w_l[i]
            v = v_l[i]
            if j < v:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i][j - v] + w)
 
    res = 0
    for j in range(max_v):
        if dp[N][j] <= W:
            res = j

    print(res)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    maxv=sum(v)+1
    dp=[[2**60]*maxv for _ in range(N+1)]
    dp[0][0]=0
    for i in range(N):
        for j in range(maxv):
            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 j in range(maxv):
        if W >= dp[N][j]:
            ans=j
    print(ans)
    return


# 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:
N,W = map(int, input().split())

import numpy as np
dp = np.full(1000*N+1, W+1, dtype=int)
dp[0]=0

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

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wv = []
for _ in range(N):
  wv += list(map(int, input().split()))
MAX_N, MAX_V = 110, 100100
dp = [[10e+09 for i in range(MAX_V)] for j in range(MAX_N)]
dp[0][0] = 0
for i in range(N):
  for v in range(MAX_V):  
    if v-wv[2*i+1] >= 0:
      dp[i+1][v] = min(dp[i+1][v], dp[i][v-wv[2*i+1]]+wv[2*i])
    dp[i+1][v] = min(dp[i+1][v], dp[i][v])
for v in range(MAX_V):
  if dp[N][v] <= W: res = v
print(res)

Submission status: Accepted

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

import numpy as np
dp = np.full(N*1000+1, W+1, dtype=int)
dp[0] = 0

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

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

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
w_list = []
v_list = []
for _ in range(N):
    w,v = map(int,input().split())
    w_list.append(w)
    v_list.append(v)
dp = [[10**12]*(10**5+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    w = w_list[i-1]
    v = v_list[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]
maxer = 0
for j in range(10**5+1):
    if dp[i][j] <= W:
        maxer = j
print(maxer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
INF=10**9+1
def main():
    n, W = map(int, input().split())
    dp = np.full(n*1000+1,INF,dtype=int)
    dp[0]=0
    for i in range(1,n+1):
        w,v=map(int,input().split())
        dp[v:]=np.minimum(dp[v:],dp[:-v]+w)
    for i in range(len(dp)-1, -1, -1):
        if dp[i] <= W:
            print(i)
            break

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_e
import sys
inf = sys.maxsize

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

mv = 1000 * n

dp = [[inf for _ in range(mv+ 1)] for _ in range(n + 1)] #dp[i番目まで][価値sv以上の重さの最小値]

dp[0][0] = 0

for i in range(n):
    w, v = map(int,input().split())
    for sv in range(mv + 1):
        if sv - v >= 0:
            dp[i + 1][sv] = min(dp[i][sv], dp[i][sv - v] + w)
        else:
            dp[i + 1][sv] = dp[i][sv]

ans = 0
for sv in range(mv + 1):
    if dp[n][sv] <= mw:
        ans = sv

print(ans)

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
w_list=[0]*N
v_list=[0]*N
for i in range(N):
    w_list[i],v_list[i]=map(int,input().split())
    
V=N*1000
inf=float("inf")
dp=[[inf]*(V+1) for _ in range(N+1)]
dp[0][0]=0

for v in range(V+1):
    for n in range(N):
        if v>=v_list[n]:
            dp[n+1][v] = min(dp[n][v-v_list[n]]+w_list[n],dp[n][v])
        else:
            dp[n+1][v]=dp[n][v]

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

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

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

#print(dp)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import namedtuple


INF = sys.maxsize
Item = namedtuple('Item', 'w v')

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

items = []

for _ in range(N):
  w, v = map(int, input().split())
  items.append(Item(w, v))
  
max_value = 10 ** 3 * 100  

memo = [0] + [INF] * max_value

for item in items:
  for v in range(max_value, item.v - 1, -1):
    memo[v] = min(memo[v], memo[v - item.v] + item.w)
  
print(max([v for v, w in enumerate(memo) if w <= W]))

Submission status: Accepted

Solution code:
# input
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 = 1000 * N

# DP
dp = [[float('inf')] * (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] = 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())
dp=[[float('inf')]*(sum(v)+1) for i in range(N+1)]

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

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

Submission status: Accepted

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

v = sum(list(map(lambda x: x[1], wv)))
dp = [[float("inf")]*(v+1) for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
    a = wv[i]
    for j in range(v+1):
        if a[1] <= j:
            dp[i+1][j] = min(dp[i][j], dp[i][j- a[1]] + a[0])
        else:
            dp[i+1][j] = dp[i][j]

dpl = dp[-1]
for i in range(v, -1, -1):
    if dpl[i] <= w:
        print(i)
        break

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy

def main():
  n, w = map(int, input().strip().split())
  Ws, Vs = numpy.array([[int(x) for x in input().strip().split()] for _ in range(n)]).T
  v_max = 10**5
  dp = numpy.full((n, v_max+1), 10**9+1, dtype=numpy.int)
  dp[0, 1:Vs[0]+1] = Ws[0]
  dp[:, 0] = 0
  for i in range(1, n):
    dp[i, :Vs[i]+1] = numpy.minimum(dp[i-1, :Vs[i]+1], Ws[i])
    if v_max - Vs[i] + 1 > 0:
      dp[i, Vs[i]:v_max+1] = numpy.minimum(dp[i-1, Vs[i]:v_max+1], dp[i-1,:v_max-Vs[i]+1]+Ws[i])
  print(numpy.max(numpy.where(dp[n-1] <= w)))


if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
#PythonだとTLE、PyPyだとAC
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 i in range(V)] for j in range(N)]

for i in range(N):
    for j in range(v[i]):
        dp[i][j] = w[i]

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

cnt = 0
for i in dp[-1]:
    if i <= W:
        cnt += 1
print(cnt)

Submission status: Accepted

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

N, W = map(int, input().split())
B = [list(map(int, input().split())) for _ in range(N)]
INF = 10**10
dp = [[INF]*(10**5+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    w, v = B[i]
    for j in range(10**5+1):
        if j-v >= 0:
            dp[i+1][j] = min(dp[i][j], dp[i][j-v]+w)
        else:
            dp[i+1][j] = dp[i][j]
for i in range(10**5, -1, -1):
    if dp[N][i] <= W:
        print(i)
        break

Submission status: Accepted

Solution code:
N, W = [int(i) for i in input().split()]
weight = []
value = []
for i in range(N):
  w, val = [int(i) for i in input().split()]
  weight.append(w)
  value.append(val)
# changing to value max as W_max ~ 10^9 and val_max ~= 1000 * next
val_max = 0
for i in range(N):
  val_max += value[i]
dp = [float('inf') for i in range(val_max+1)] # dp[i] is the min weight required for the value 
# hence our ans would be in the max value where the weight < knapsack weight
dp[0] = 0
for i in range(N):
  for v in range(val_max-value[i], -1, -1): # range of kanpsack weight in which i can push the current item
    dp[v + value[i]] = min(dp[v + value[i]], dp[v] + weight[i])
    #print(dp)
sol = 0
for i in range(val_max+1):
  if dp[i] <= W:
    sol = i
print("%s" % sol)

Submission status: Accepted

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

N, W = [int(x) for x in input().split()]
wv = []
for _ in range(N):
    wv.append([int(x) for x in input().split()])
V = 10 ** 5
inf = float("inf")

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

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

Submission status: Accepted

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

    maxw = 10 ** 11  # 重さの最小化なので、初期値は最大重さとすることにdebugで気づいた
    maxv = 10 ** 5

    n, w = map(int, readline().split())

    dp = [[maxw] * (maxv + 1) for _ in range(n + 1)]
    dp[0][0] = 0

    for i in range(1, n + 1):  # i個目の品物を選ぶかどうか決めた後の重さの総和の最小値,1-indexed
        wi, vi = map(int, readline().split())
        for j in range(vi):
            dp[i][j] = dp[i - 1][j]
        for j in range(vi, maxv + 1):
            dp[i][j] = min(
                dp[i - 1][j],
                dp[i - 1][j - vi] + wi
            )

    ret = next(j for j in reversed(range(maxv + 1)) if dp[n][j] <= w)

    print(ret)


if __name__ == '__main__':
    main()