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:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,w=MI()
WV=[LI() for i in range(n)]
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):
        if j-WV[i][1]>=0:
            dp[i+1][j]=min(dp[i+1][j],dp[i][j],dp[i][j-WV[i][1]]+WV[i][0])
        else:
            dp[i+1][j]=min(dp[i+1][j],dp[i][j])
for i in range(10**5+1):
    j=10**5-i
    if dp[-1][j]<=w:
        print(j)
        sys.exit()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, w = LI()
wv = LIR(n)
vv = 10 ** 5
dp = [INF] * (vv + 1)
dp[0] = 0
for i in range(n):
    wi, vi = wv[i]
    for j in range(vv, vi - 1, -1):
        dp[j] = min(dp[j], dp[j - vi] + wi)

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

Submission status: Accepted

Solution code:
INF = 10**15
N, W = map(int, input().split())
value, weight = [0], [0]
for _ in range(N):
  w, v = map(int, input().split())
  weight.append(w)
  value.append(v)
dp = [[INF]*100100 for _ in range(N+1)]
dp[0][0] = 0

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

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

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
W, V = [], []
sum_v = 0
for i in range(n):
  wi, vi = map(int ,input().split())
  W.append(wi)
  V.append(vi)
  sum_v += vi

memo = [[10**9] * (sum_v + 1) for _ in range(n+1)]
memo[0][0] = 0

for i in range(n):
  for v_i in range(sum_v + 1):
    memo[i+1][v_i] = min(memo[i+1][v_i], memo[i][v_i])
    if v_i - V[i] >= 0:
      memo[i+1][v_i] = min(memo[i+1][v_i], memo[i][v_i-V[i]] + W[i])

ans = 0
for i in range(sum_v + 1):
  if memo[-1][i] <= w:
    ans = i
print(ans)

Submission status: Accepted

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

item_ls = [[0,0]]
total_value = 0
for i in range(n):
    cost, value = map(int,input().split())
    item_ls.append([cost, value])
    total_value += value


dp = [[float('inf')] * (total_value+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(1,n+1):
    item_cost, item_value = item_ls[i]
    for sum_value in range(0,total_value+1):
        if sum_value-item_value >= 0:
            dp[i][sum_value] = min(dp[i][sum_value], dp[i-1][sum_value-item_value] + item_cost)
        dp[i][sum_value] = min(dp[i][sum_value], dp[i-1][sum_value])

ans = 0
for value, cost in enumerate(dp[n]):
    if cost <= w_limit:
        ans = max(ans, value)
print(ans)

Submission status: Accepted

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

weights = [0]*n
values = [0]*n

for i in range(n):
    weights[i], values[i] = map(int, input().split())

v = sum(values)

dp = [[float('inf') for _ in range(v+1)] for _ 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, v+1):
        if values[i-1] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = min(weights[i-1] + dp[i-1][j-values[i-1]], dp[i-1][j])

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

Submission status: Accepted

Solution code:
import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
#sys.setrecursionlimit(200000000)
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
#def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])
    
def knapsack(wts,P,N,W):
    if N==0 or W == 0:
        return 0
    dp = list2d(100,100001,1e10) #dp[item][val] = weight
    dp[0][0] = 0
    dp[0][P[0]] = wts[0]
    ##we have to minimize the weight
    for i in range(1,N):
        dp[i][0] = 0
        for j in range(1,100000+1):
            dp[i][j] = dp[i-1][j] # discarding current
            if P[i] <= j:
                dp[i][j] = min(wts[i] + dp[i-1][j - P[i]] , dp[i][j])
            
    #minimum weight
    for val in range(100000,-1,-1):
        if dp[N-1][val] <= W:
            return val #returning the val at maximum weight
    

N,W = ilele()
P = []
A = []
for i in range(N):
    a,b =ilele()
    A.append(a)
    P.append(b)
print(knapsack(A,P,N,W))

Submission status: Accepted

Solution code:
import numpy as np
 
N, W = map(int, input().split())
dp = np.ones(int(1e5+1)) * np.inf
dp[0] = 0
total = 0
for i in range(N):
    w, v = map(int, input().split())
    dp[v:total+v+1] = np.minimum(dp[v:total+v+1], dp[:total+1] + w)
    total += v
 
print(int(np.where(dp<=W)[0][-1]))

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq

N, W = list(map(int, input().split()))
INF = 10**10

dp = [[INF]*(100005) for i in range(N+5)]

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

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

for i in range(1000001):
    if dp[N][i] > W:
        print(i-1)
        exit()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
N,W = map(int, input().split())
v_max = (10**3)*N
inf = float('inf')
dp = [inf for _ in range(v_max+1)]
dp[0] = 0
for _ in range(N):
	w,v = map(int, input().split())
	for j in range(v_max,v-1,-1):
		b = w + dp[j-v]		
		if b<dp[j]:
			dp[j] = b

ans = None
for i in range(v_max+1):
	z = dp[i]
	if z<=W:
		ans = i

print(ans)

Submission status: Accepted

Solution code:
INF_V = 1000*100
N, W = list(map(int, input().split()))
dp = [[W+1]*(INF_V+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    w, v = list(map(int, input().split()))
    for j in range(INF_V-1000+1):
        dp[i+1][j+v] = min(dp[i+1][j+v], dp[i][j] + w)
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
print([i for (i, w) in enumerate(dp[N]) if w <= W][-1])

Submission status: Accepted

Solution code:
N, W = list(map(int, input().split()))
dp = [[W+1]*(100000+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    w, v = list(map(int, input().split()))
    for j in range(100000+1):
        if j+v <= 100000:
            dp[i+1][j+v] = min(dp[i+1][j+v], dp[i][j] + w)
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
i = -1
while True:
    if dp[N][i] <= W:
        print(100000+1+i)
        break
    else:
        i -= 1

Submission status: Accepted

Solution code:
# Author: S Mahesh Raju
# Username: maheshraju2020
# Date: 31/07/2020

from sys import stdin,stdout
from math import gcd, ceil, sqrt
from collections import Counter
from bisect import bisect_left, bisect_right
ii1 = lambda: int(stdin.readline().strip())
is1 = lambda: stdin.readline().strip()
iia = lambda: list(map(int, stdin.readline().strip().split()))
isa = lambda: stdin.readline().strip().split()
mod = 1000000007

n, w = iia()
wt, val = [], []
for i in range(n):
    a, b = iia()
    wt.append(a)
    val.append(b)
tot = sum(val)
dp = [[float('inf') for i in range(tot + 1)] for j in range(n + 1)]

dp[0][0] = 0
for i in range(1, n + 1):
    for j in range(tot + 1):
        if j < val[i - 1]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = min(dp[i - 1][j], wt[i - 1] + dp[i - 1][j - val[i - 1]])

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

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,W = IL()
data = ILL(N)

dp = [[INF for v in range(110000)] for i in range(N+1)]
for i in range(N+1):
  dp[i][0] = 0
for i in range(N):
  w0,v0 = data[i]
  for v in range(110000):
    dp[i+1][v] = min(dp[i+1][v],dp[i][v])
    if v+v0 < 110000:
      dp[i+1][v+v0] = min(dp[i][v+v0],dp[i][v]+w0)

v = 110000-1
while dp[-1][v] > W:
  v -= 1
print(v)

Submission status: Accepted

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

# dp[i][sum_v]:
# i-1番目までの品物から価値がsum_v以上を達成するように選んだ時の、重さの最小値
# sum_v <= max_N * max_v = 10^5
dp = [[INF]*100100 for _ in range(110)]

# 初期条件
dp[0][0] = 0

# DPループ
for i in range(N):
    weight, value = map(int, input().split())
    for sum_v in range(10**5+1):

        # i番目の品物を選ぶ場合
        if sum_v - value >= 0:
            dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v - value] + weight)

        # 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:
"""
    Satwik_Tiwari ;) .
    24th july , 2020  - Friday
"""

#===============================================================================================
#importing some useful libraries.
from __future__ import division, print_function

from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
from itertools import combinations as comb # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
from itertools import permutations as permutate
from bisect import bisect_left as bl
#If the element is already present in the list,
# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect
#If the element is already present in the list,
# the right most position where element has to be inserted is returned

#==============================================================================================
#fast I/O region
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

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


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        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")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")

#===============================================================================================
#some shortcuts

mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") #for fast input
def out(var): sys.stdout.write(str(var))  #for fast output, always take string
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())
# def graph(vertex): return [[] for i in range(0,vertex+1)]
def zerolist(n): return [0]*n
def nextline(): out("\n")  #as stdout.write always print sring.
def testcase(t):
    for p in range(t):
        solve()
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def lcm(a,b): return (a*b)//gcd(a,b)
def power(a,b):
    ans = 1
    while(b>0):
        if(b%2==1):
            ans*=a
        a*=a
        b//=2
    return ans
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) :
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True

#===============================================================================================
# code here ;))

def solve():
    n,W = sep()
    w = [0]
    v = [0]
    for i in range(n):
        a,b = sep()
        w.append(a)
        v.append(b)
    s = sum(v)
    dp = [[10**10]*((n+1)) for i in range(s+1)]

    for i in range(n+1):
        dp[0][i] = 0
    # for i in range(s+1):
    #     dp[i][0] = 0

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

    # for i in range(len(dp)):
    #     print(dp[i])
    ans = 0
    for i in range(1,s+1):
        for j in range(1,n+1):
            if(dp[i][j] <= W):
                ans = max(ans,i)

    print(ans)


testcase(1)
# testcase(int(inp()))

Submission status: Accepted

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
import math

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')
def pprint(M):
	for row in M:
		print(row)
	print("~~~")


def main():
	n, W = rli()
	weights, vals = [], []
	for _ in range(n):
		w, v = rli()
		weights.append(w)
		vals.append(v)
	maxval = 10**5 + 100
	dp = [INF for _ in range(maxval+1)]
	dp[0] = 0
	for w, v in zip(weights, vals):
		for i in range(maxval, -1, -1):
			if i - v < 0: continue
			dp[i] = min(dp[i], dp[i-v] + w)
	for i in range(maxval, -1, -1):
		if dp[i] <= W:
			print(i)
			break
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
def solve():
  N, W = map(int, input().split())
  dp = [[float('inf')]*(10**5+1) for _ in range(N+1)]
  for i in range(N+1):
    dp[i][0] = 0
  for i in range(N):
    w,v = map(int, input().split())
    for j in range(10**5+1):
      dp[i+1][j] = min(dp[i][j],dp[i+1][j])
      if j+v<=10**5:
        dp[i+1][j+v] = min(dp[i][j+v],dp[i][j]+w)
  for i in range(10**5,-1,-1):
    if dp[-1][i]<=W:
      ans = i
      break
  return ans
print(solve())

Submission status: Accepted

Solution code:
import sys

# input処理を高速化する
input = sys.stdin.readline

# 入力
N, W = map(int, input().split())
# sum_vの取りうる上限値
MAX_V = (10**3) * N +1
# 最小値を求めるので無限大の値
f_inf = float('inf')

def knapsack(n, w):
    # dpの初期化　dp[sum_v]は重さの総和の最小値
    dp = [f_inf] * MAX_V
    # 初期条件
    dp[0] = 0
    sum_v = 0
    # forは全て関数の中で回す。
    # 入力
    for i in range(N):
        w, v = map(int, input().split())
        for j in range(MAX_V, v-1, -1):
            new_weight = dp[j - v] + w
            if new_weight > W:
                continue
            if dp[j] > new_weight:
                dp[j] = new_weight

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

knapsack(N, W)

Submission status: Accepted

Solution code:
x,size=map(int,input().split())
weight=[]
value=[]
weight.append(0)
value.append(0)
for i in range(x):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
max_value=sum(value)
dp=[[float('inf') for i in range(max_value+1)] for j in range(x+1)]
for i in range(x+1):
    dp[i][0]=0
for i in range(1,x+1):
    w=weight[i]
    v=value[i]
    for knap_v in range(1,max_value+1):
        if v<=knap_v:
            dp[i][knap_v]=min(dp[i-1][knap_v],w+dp[i-1][knap_v-v])
        else:
            dp[i][knap_v]=dp[i-1][knap_v]
ans=0
# print(dp)
for i in range(max_value+1):
    if dp[x][i]<=size:
        ans=i
print(ans)

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]#w重さ v価値
dp=[[10**11+100 for _ in range(10**5+15)] for _ in range(n+1)]#各iで価値vを達成する最小のw
dp[0][0]=0
for i in range(n):#番目
  for j in range(10**5+15):#価値
      dp[i+1][j]=min(dp[i][j],dp[i][max(j-a[i][1],0)]+a[i][0])
an=0


for j in range(10**5+15):
  if dp[n][j]<=w and j>an:
    an=j
print(an)

Submission status: Accepted

Solution code:

N,W=list(map(int,input().split()))
weights=[]
value=[]
for i in range(N):
    w,v=list(map(int,input().split()))
    weights.append(w)
    value.append(v)
t=sum(value)
maxa=10**18
dp=[maxa for i in range(t+1)]
dp[0]=0
for i in range(N):
    for val in range(t-value[i],-1,-1):
       dp[val+value[i]] = min(dp[val+value[i]],dp[val]+weights[i])
ans=0
for i in range(t+1):
    if(dp[i]<=W):
        ans=max(ans,i)
# print(dp)
print(ans)

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_e
import copy
N,W = map(int,input().split())
Goods_List=[]
for i in range(N):
    Goods_List.append(list(map(int,input().split())))
 
Sum_Value = sum(map(lambda x:x[1],Goods_List))
dp = [[0] * (Sum_Value + 1) for i in range(N)]

for i in range(N):
    if i == 0:
        dp[i][Goods_List[i][1]] = Goods_List[i][0]
    else:
        dp[i] = copy.copy(dp[i-1])
        Valid_List = [k for k, x in enumerate(dp[i]) if x != 0]
        Valid_List.append(0)
        for j in Valid_List:
            if dp[i][j + Goods_List[i][1]] == 0:
                dp[i][j + Goods_List[i][1]] = dp[i-1][j] + Goods_List[i][0]
            else:
                dp[i][j + Goods_List[i][1]] = min(dp[i-1][j] + Goods_List[i][0],dp[i][j + Goods_List[i][1]])
        

for k in range(len(dp[-1])-1,0,-1):
    if (dp[-1][k] != 0) & (dp[-1][k] <= W):
        print(k)
        break

Submission status: Accepted

Solution code:
from sys import stdin
from math import inf
n,W = map(int,stdin.readline().split())
dp = [inf]*(1000*n)
for _ in range(n):
    w,v = map(int,stdin.readline().split())
    for i in range(1000*n-v-1,-1,-1):
        if dp[i] and dp[i]+w <= W:
            dp[i+v] = min(dp[i+v],dp[i]+w)
    dp[v-1] = min(dp[v-1],w)
for i in range(len(dp)-1,-1,-1):
    if dp[i] != inf:
        print(i+1)
        break

Submission status: Accepted

Solution code:
INF, NVINF = float("inf"), 10**5
N, W = map(int,input().split())
dp = [0] + [INF] * NVINF
for _ in [None]*N:
  w, v = map(int,input().split())
  for j in range(NVINF, v-1, -1):
    dp[j] = min(dp[j], dp[j - v] + w)
for v, w in list(enumerate(dp))[::-1]:
    if w <= W:
      exit(print(v))

Submission status: Accepted

Solution code:

def resolve():
    N, max_W = map(int, input().split())
    W, V = zip(*[list(map(int, input().split())) for _ in range(N)])
    max_V = sum(V)
    dp = [[1 << 60] * (max_V + 1) for _ in range(N + 1)]
    dp[0][0] = 0

    for i in range(N):
        for v in range(max_V + 1):
            dp[i + 1][v] = min(dp[i + 1][v], dp[i][v])
            if V[i] <= v:
                dp[i + 1][v] = min(dp[i + 1][v], dp[i][v - V[i]] + W[i])

    # ミス： range関数の時[0, 8)で +1をして調整している。if文でもmax_W+1で調整しWA
    ans = 0
    for v in range(max_V + 1):
        if dp[N][v] <= max_W:
            ans = max(ans, v)
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
import bisect


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


def main():
    N, W = map(int, input().split())
    vsup = 10 ** 3 * N + 2
    dp = [10 ** 12 + 1] * (vsup)  # 価値の総和を i (以上にするための重さの最小値
    dp[0] = 0

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

    print(bisect.bisect_right(dp, W) - 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import bisect


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


def main():
    N, W = map(int, input().split())
    vsup = 10 ** 3 * N + 2
    dp = [10 ** 12 + 1] * (vsup)  # 価値の総和を i (以上にするための重さの最小値
    dp[0] = 0

    for i in range(N):
        w, v = map(int, input().split())
        for j in range(vsup-2, -1, -1):
            if j - v >= 0:
                dp[j] = min(dp[j], dp[j - v] + w)
            dp[j] = min(dp[j],dp[j+1])

    print(bisect.bisect_right(dp,W)-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n, w = ns()
    a = [na() for _ in range(n)]

    idx = n * 10 ** 3 + 1
    dp = [INF for _ in range(idx)]
    dp[0] = 0

    for wi, vi in a:
        for i in range(idx - 1, -1, -1):
            if dp[i] + wi <= w and i + vi < idx and dp[i] > -1:
                dp[i + vi] = min(dp[i + vi], dp[i] + wi)

    for i in range(idx - 1, -1, -1):
        if dp[i] != INF:
            print(i)
            break


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
dp = [0] + [float('inf')]*10**5

for _ in range(N):
    w,v = map(int,input().split())
    for j in range(10**5,v-1,-1):
        dp[j] = min(dp[j], dp[j-v] + w)
for i,x in enumerate(dp):
    if x <=W: ans = i
print(ans)

Submission status: Accepted

Solution code:
n, W = map(int, input().split())
w, v = [], []
for i in range(n):
    w_, v_ = map(int, input().split())
    w.append(w_)
    v.append(v_)
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 - 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 i in range(100000, -1, -1):
    if dp[n][i] <= W:
        break
print(i)

Submission status: Accepted

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

n, w = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n)]

v = 10**5 + 4
D = [float("inf")] * v
D[0] = 0
for i in range(n):
    for j in range(v-1,-1,-1):
        if j-A[i][1] >= 0:
            D[j] = min(D[j], D[j-A[i][1]] + A[i][0])

ans = 0
for i in range(v):
    if D[i] <= w:
        ans = i
print(ans)

Submission status: Accepted

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

INF = int(1e16)

dp = [[INF] * (int(1e5) + 1) for _ in range(n + 1)]
# dp[i][v] minimum total weight of the first i items that sum value is exactly v

dp[0][0] = 0

for i in range(1, n + 1):
    weight, value = map(int, input().split())
    for v in range(int(1e5) + 1):
        dp[i][v] = min(dp[i-1][v], dp[i][v])
        if v >= value:
            dp[i][v] = min(dp[i][v], dp[i-1][v-value] + weight)

#print(*dp, sep = '\n')

for v in range(int(1e5), -1, -1):
    if dp[n][v] <= W:
        print(v)
        break

Submission status: Accepted

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

dp = np.full(10 ** 5 + 1, W + 1,dtype = int)
dp[0] = 0

for i in range(N):
  w,v = map(int,input().split())
  np.minimum(dp[:-v] + w,dp[v:],out = dp[v:])
  
for i in range(len(dp) - 1, -1, -1):
  if dp[i] <= W:
    print(i)
    break