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^5

1 \leq w_i \leq W

1 \leq v_i \leq 10^9

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

5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

Sample Output 2

5000000000

The answer may not fit into a 32-bit integer type.

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=[[0]*(w+1) for i in range(n+1)]
for i in range(n):
    for j in range(w+1):
        if j-WV[i][0]>=0:
            dp[i+1][j]=max(dp[i+1][j],dp[i][j],dp[i][j-WV[i][0]]+WV[i][1])
        else:
            dp[i+1][j]=max(dp[i+1][j],dp[i][j])
    #print(dp)
print(max(dp[-1]))

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)
dp = [0] * (w + 1)
for i in range(n):
    wi, vi = wv[i]
    for j in range(w, wi - 1, -1):
        dp[j] = max(dp[j], dp[j - wi] + vi)

print(max(dp))

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
wt,p=[],[]
for _ in range(n):
    a,b=map(int,input().split())
    wt.append(a)
    p.append(b)
dp=[0 for i in range(W+1)]
for x in range(1,n+1):
  
  for y in range(W,0,-1):
    if wt[x-1]<=y:
        
      dp[y]=max(dp[y-wt[x-1]]+p[x-1],dp[y])
    else:

      dp[y]=dp[y]
print(dp[-1])

Submission status: Accepted

Solution code:
# what is dp relation 
# dp[n][w]=max(dp[n-1][w-wt[n]]+p[n],dp[n-1][w])

n,W=map(int,input().split())
wt,p=[],[]
for _ in range(n):
    a,b=map(int,input().split())
    wt.append(a)
    p.append(b)
dp=[[0 for i in range(W+1)]for j in range(n+1)]
for x in range(1,n+1):
    for y in range(1,W+1):
        if wt[x-1]<=y:
            dp[x][y]=max(dp[x-1][y-wt[x-1]]+p[x-1],dp[x-1][y])
        else:
            dp[x][y]=dp[x-1][y]
print(dp[-1][-1])

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
t = [[-1 for i in range(W + 1)] for j in range(n + 1)] 
  
def dp(n,W,w,p):
  
  if n==0 or W==0:
    return 0
  elif t[n][W]!=-1:
    return t[n][W]
  else:
    if w[n-1]<=W:
      t[n][W]=max(p[n-1]+dp(n-1,W-w[n-1],w,p),dp(n-1,W,w,p))
      return t[n][W]
    else:
      t[n][W]=dp(n-1,W,w,p)
      return t[n][W]

weight,profit=[],[]
for _ in range(n):
  w,p=map(int,input().split())
  weight.append(w)
  profit.append(p)
print(dp(n,W,weight,profit))

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
t = [[-1 for i in range(W + 1)] for j in range(n + 1)] 
  
  
def knapsack(wt, val, W, n):     
  
    # base conditions 
    if n == 0 or W == 0: 
        return 0
    if t[n][W] != -1: 
        return t[n][W] 
  
    # choice diagram code 
    if wt[n-1] <= W: 
        t[n][W] = max(val[n-1] + knapsack(wt, val, W-wt[n-1], n-1),knapsack(wt, val, W, n-1)) 
        return t[n][W] 
    elif wt[n-1] > W: 
        t[n][W] = knapsack(wt, val, W, n-1) 
        return t[n][W] 

weight,profit=[],[]
for _ in range(n):
  w,p=map(int,input().split())
  weight.append(w)
  profit.append(p) 
print(knapsack(weight,profit, W, n))

Submission status: Accepted

Solution code:
def input_li():
    return list(map(int, input().split()))

def input_int():
    return int(input())

N, W = input_li()
# dp[n][w] ... 荷物nまでの容量wの価値の最大値を格納する
dp = [[0] * (W + 1) for _ in range(N + 1)]
wv_li = [input_li() for _ in range(N)]
now_w = 0
for i in range(N):
    for sum_w in range(W + 1):
        w, v = wv_li[i]
        if w > sum_w:
            # 容量オーバー
            dp[i + 1][sum_w] = dp[i][sum_w]
        else:
            dp[i + 1][sum_w] = max(dp[i][sum_w], dp[i][sum_w - w] + v)
print(dp[N][W])

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
W = []
V = []

for _ in range(n):
    x, y = map(int, input().split())
    W.append(x)
    V.append(y)
dp = [[0] * (w + 1) for _ in range(n + 1)]

for i in range(n):
    for sum_w in range(w + 1):
        if W[i] > sum_w:
            dp[i + 1][sum_w] = dp[i][sum_w]
        else:
            dp[i + 1][sum_w] = max(dp[i][sum_w], dp[i][sum_w - W[i]] + V[i])

print(dp[n][w])

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
dp = [[0] * (W+1) for _ in range(N+1)]
for i in range(N):
    w, v = map(int, input().split())
    for w_lim in range(W+1):
        if w <= w_lim:
            dp[i+1][w_lim] = max(dp[i][w_lim-w]+v, dp[i][w_lim])
        else:
            dp[i+1][w_lim] = dp[i][w_lim]
print(dp[N][W])

Submission status: Accepted

Solution code:
n, W = map(int,input().split())
items = [[0,0] for _ in range(n+1)]
for i in range(n):
    items[i+1] = list(map(int, input().split()))

dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1,n+1):
    weight, value = items[i][0], items[i][1]
    for w_limit in range(1,W+1):
        if w_limit - weight >= 0:
            dp[i][w_limit] = max(dp[i-1][w_limit], dp[i-1][w_limit-weight] + value)
        else:
            dp[i][w_limit] = dp[i-1][w_limit]
print(dp[n][W])

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
dp = [0] * (w + 1)
for j in range(n):
	w1, v1 = map(int, input().split())
	i = w
	while i >= 0 and i - w1 >= 0:
		dp[i] = max(dp[i - w1] + v1, dp[i])
		i -= 1
print(max(dp))

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
dp = [0] * (W + 1)
def dp_opt(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for j in range(W, w-1, -1):
            tmp = dp[j-w] + v
            if tmp > dp[j]:
                dp[j] = tmp
    print(dp[-1])
dp_opt(N,W)

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 fun(A,P,W,N):
    if N == 0 or W == 0:
        return 0
    dp = list2d(N+1,W+1,0)
    for i in range(1,N+1):
        for j in range(1,W+1):
            if A[i-1] <= j:
                dp[i][j] = max(dp[i-1][j] , P[i-1] + dp[i-1][j - A[i-1]])
            else:
                dp[i][j] = dp[i-1][j]
    return dp[N][W]
N,W = ilele()
P = []
A = []
for i in range(N):
    a,b =ilele()
    A.append(a)
    P.append(b)
print(fun(A,P,W,N))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
 
N,W = map(int,readline().split())
 
import numpy as np
dp = np.zeros(W + 1, dtype = int)
 
for i in range(N):
  w,v = map(int,readline().split())
  np.maximum(dp[:-w] + v, dp[w:], out = dp[w:])
  
print(dp.max())

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
dp=[[0]*(W+1) for _ in range(N+1)]
# dp[n][w] := n個の品物のうち上限の容量wのときの価値の最大値
 
for i in range(1,N+1):
    w,v=map(int,input().split())
    for j in range(1,W+1):
        if j>=w:
            dp[i][j]=max(dp[i-1][j-w]+v, dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
    
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
dp = [0] * (W + 1)
def dp_opt(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for j in range(W, w-1, -1):
            tmp = dp[j-w] + v
            if tmp > dp[j]:
                dp[j] = tmp
    print(dp[-1])
dp_opt(N,W)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
	N,W = map(int, input().split())
	dp = [0 for _ in range(W+1)]
	for _ in range(N):
		w,v = map(int, input().split())
		for i in range(W,0,-1):
			if i>=w:
				a = dp[i]
				b = dp[i-w]+v
				if a>b:
					dp[i] = a
				else:
					dp[i] = b
		
	print(dp[-1])
 
if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
	N,W = map(int, input().split())
	dp = [0 for _ in range(W+1)]
	for _ in range(N):
		w,v = map(int, input().split())
		for i in range(W,0,-1):
			if i>=w:
				a = dp[i]
				b = dp[i-w]+v
				if a>b:
					dp[i] = a
				else:
					dp[i] = b
		
	print(dp[-1])

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
import numpy as np

def main():
    n, w = map(int, sys.stdin.buffer.readline().split())
    dp = np.zeros(w+1, dtype = int)

    for x in sys.stdin.buffer.readlines():
        w, v = map(int, x.split())
        np.maximum(dp[w:] , dp[:-w] + v, out = dp[w:])
    print(dp.max())

if __name__ == '__main__':
    main()

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 = [[0 for w in range(W+1)] for i in range(N+1)]

for i in range(N):
  w0,v0 = data[i]
  for w in range(W+1):
    dp[i+1][w] = max(dp[i+1][w],dp[i][w])
    if w+w0 <= W:
      dp[i+1][w+w0] = max(dp[i][w+w0],dp[i][w]+v0)

print(max(dp[-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()
dp = [[0 for i in range(w + 1)] for j in range(n + 1)]
arr = []
for i in range(n):
    arr.append(iia())
for i in range(1, n + 1):
    for j in range(w + 1):
        if j < arr[i - 1][0]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], arr[i - 1][1] + dp[i - 1][j - arr[i - 1][0]])
print(dp[-1][-1])

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
dp = [[0]*100100 for _ in range(110)]

for i in range(N):
    weight, value = map(int, input().split())
    for sum_w in range(W+1):
        if sum_w - weight >= 0:
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - weight] + value)

        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])

print(dp[N][W])

Submission status: Accepted

Solution code:
from pprint import pprint
import numpy as np
import numba as nb
@nb.njit
def Knapsack1(n,w,wl,vl):
  dp = np.zeros(shape=(n + 1, w + 1), dtype=np.int64)
  for wsum in range(1,w+1):
  	#print("i={}".format(i))    
    for i in range(n):
      #print("重さ：{}".format(wsum))
      if wsum >= wl[i]:
        if dp[i][wsum] < dp[i][wsum-wl[i]]+vl[i]:
          #print("選ぶ, (重さ：{}, 価値：{})".format(wv[i][0], wv[i][1]))
          dp[i+1][wsum] = dp[i][wsum-wl[i]]+vl[i]
        else:
          dp[i+1][wsum] = dp[i][wsum]
          
      else:
        dp[i+1][wsum] = dp[i][wsum]
  #print(dp)
  print(dp[-1][-1])

n,w=map(int, input().split())
wv=[list(map(int,input().split()))  for i in  range(n)]
wv.sort(key=lambda x:(x[1],x[0]))
wv=np.array(wv)
wv=wv.T
wl=wv[0]
vl=wv[1]
#print(wl)
#print(vl)
Knapsack1(n,w,wl,vl)

Submission status: Accepted

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

dp = [[0]*100100 for _ in range(110)]

for i in range(N):
    for sum_w in range(W+1):
        weight, value = item[i]
        if sum_w - weight >= 0:
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - weight] + value)

        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])

print(dp[N][W])

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

dp = [[0 for _ in range(w+1)] for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, w+1):
        if j < weights[i-1]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], values[i-1]+dp[i-1][j-weights[i-1]])

print(dp[-1][-1])

Submission status: Accepted

Solution code:
import numpy as np

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

dp = np.zeros(w+1)

for w, v in wv:
    dp[w:] = np.maximum(dp[:-w]+v,dp[w:])
print(int(dp[-1]))

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)

    dp = [[0]*(n+1) for i in range(W+1)]
    for i in range(1,W+1):
        for j in range(1,n+1):
            if(w[j] <= i):
                dp[i][j] = max(dp[i][j-1],dp[i-w[j]][j-1]+v[j])
            else:
                dp[i][j] = dp[i][j-1]
    print(dp[W][n])


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
## necessary imports
import sys
input = sys.stdin.readline
# from math import ceil, floor, factorial;

def ceil(x):
    if x != int(x):
        x = int(x) + 1;
    return x;
    
# swap_array function
def swaparr(arr, a,b):
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp

## gcd function
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b, a % b);

## nCr function efficient using Binomial Cofficient
def nCr(n, k): 
    if(k > n - k): 
        k = n - k 
    res = 1
    for i in range(k): 
        res = res * (n - i) 
        res = res / (i + 1) 
    return int(res) 

## upper bound function code -- such that e in a[:i] e < x;
def upper_bound(a, x, lo=0, hi = None):
    if hi == None:
        hi = len(a);
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x:
            lo = mid+1
        else:
            hi = mid
    return lo

## prime factorization
def primefs(n):
    ## if n == 1    ## calculating primes
    primes = {}
    while(n%2 == 0 and n > 0):
        primes[2] = primes.get(2, 0) + 1
        n = n//2
    for i in range(3, int(n**0.5)+2, 2):
        while(n%i == 0 and n > 0):
            primes[i] = primes.get(i, 0) + 1
            n = n//i
    if n > 2:
        primes[n] = primes.get(n, 0) + 1
    ## prime factoriazation of n is stored in dictionary
    ## primes and can be accesed. O(sqrt n)
    return primes

## MODULAR EXPONENTIATION FUNCTION
def power(x, y, p): 
    res = 1
    x = x % p  
    if (x == 0) : 
        return 0
    while (y > 0) : 
        if ((y & 1) == 1) : 
            res = (res * x) % p 
        y = y >> 1      
        x = (x * x) % p 
    return res 

## DISJOINT SET UNINON FUNCTIONS
def swap(a,b):
    temp = a
    a = b
    b = temp
    return a,b

# find function with path compression included (recursive)
# def find(x, link):
#     if link[x] == x:
#         return x
#     link[x] = find(link[x], link);
#     return link[x];

# find function with path compression (ITERATIVE)
def find(x, link):
    p = x;
    while( p != link[p]):
        p = link[p];
    
    while( x != p):
        nex = link[x];
        link[x] = p;
        x = nex;
    return p;


# the union function which makes union(x,y)
# of two nodes x and y
def union(x, y, link, size):
    x = find(x, link)
    y = find(y, link)
    if size[x] < size[y]:
        x,y = swap(x,y)
    if x != y:
        size[x] += size[y]
        link[y] = x

## returns an array of boolean if primes or not USING SIEVE OF ERATOSTHANES
def sieve(n): 
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1
    return prime

#### PRIME FACTORIZATION IN O(log n) using Sieve ####
MAXN = int(1e5 + 5)
def spf_sieve():
    spf[1] = 1;
    for i in range(2, MAXN):
        spf[i] = i;
    for i in range(4, MAXN, 2):
        spf[i] = 2;
    for i in range(3, ceil(MAXN ** 0.5), 2):
        if spf[i] == i:
            for j in range(i*i, MAXN, i):
                if spf[j] == j:
                    spf[j] = i;
    ## function for storing smallest prime factors (spf) in the array

################## un-comment below 2 lines when using factorization #################
# spf = [0 for i in range(MAXN)]
# spf_sieve();
def factoriazation(x):
    ret = {};
    while x != 1:
        ret[spf[x]] = ret.get(spf[x], 0) + 1;
        x = x//spf[x]
    return ret
    ## this function is useful for multiple queries only, o/w use
    ## primefs function above. complexity O(log n)

## taking integer array input
def int_array():
    return list(map(int, input().strip().split()))
## taking string array input
def str_array():
    return input().strip().split();

#defining a couple constants
MOD = int(1e9)+7;
CMOD = 998244353;
INF = float('inf'); NINF = -float('inf');

################### ---------------- TEMPLATE ENDS HERE ---------------- ###################

n, w = int_array();
val = []; wts = [];
dp = [[0 for _ in range(w + 1)] for __ in range(n + 1)];

for _ in range(n):
    x, y = int_array();
    wts.append(x); val.append(y);

for i in range(1, n + 1):
    for j in range(1, w + 1):
        if j >= wts[i - 1]:
            dp[i][j] = max(dp[i - 1][j], val[i - 1] + dp[i - 1][j - wts[i - 1]]);
        else:
            dp[i][j] = dp[i - 1][j];
            
print(dp[n][w]);

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    wv = [None] * N
    for i in range(N):
        wv[i] = tuple(map(int, input().split()))

    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i, (w, v) in enumerate(wv, start=1):
        dp_i = dp[i]
        dp_im = dp[i - 1]
        for j in range(1, W + 1):
            if j < w:
                dp_i[j] = dp_im[j]
            else:
                a = dp_im[j - w] + v
                b = dp_im[j]
                if a > b:
                    dp_i[j] = a
                else:
                    dp_i[j] = b

    ans = dp[-1][-1]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
x,size=map(int,input().split())
weight=[]
value=[]
for i in range(x):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
dp=[[0 for i in range(size+1)] for j in range(len(weight))]
for i in range(len(weight)):
    dp[i][0]=0
for i in range(len(weight)):
    for j in range(1,size+1):
        if weight[i]>j:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])
print(dp[len(value)-1][size])

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)

dp=[[0]*(W+1) for i in range(N+1)]
for i in range(1,N+1):
    for j in range(1,W+1):
        if(j>=weights[i-1]):
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-weights[i-1]]+value[i-1])
        else:
            dp[i][j]=dp[i-1][j]
# print(dp[2][3])
print(dp[N][W])

Submission status: Accepted

Solution code:
from sys import stdin
n,w = map(int,stdin.readline().split())
dp = [0]*w
cou = []
for _ in range(n):
    cou.append(tuple(map(int,stdin.readline().split())))
for val in cou:
    for i in range(w-1,-1,-1):
        if dp[i] != 0 and i+val[0] < w:
            dp[i+val[0]] = max(dp[i+val[0]],dp[i]+val[1])
    dp[val[0]-1] = max(dp[val[0]-1],val[1])
print(max(dp))

Submission status: Accepted

Solution code:
N, W = map(int,input().split())
dp = [0]*-~W
for _ in [None]*N:
  w, v = map(int,input().split())
  for j in range(W, w-1, -1):
    dp[j] = max(dp[j], dp[j - w] + v)
print(max(dp))

Submission status: Accepted

Solution code:
import sys


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


def main():
    N, W = map(int, input().split())
    dp = [[0] * (N + 1) for _ in range(W + 1)]
    for i in range(1, N + 1):
        w, v = map(int, input().split())
        for j in range(W + 1):
            if j >= w:
                dp[j][i] = max(dp[j][i - 1], dp[j - w][i-1] + v)
            else:
                dp[j][i] = dp[j][i - 1]

    print(dp[W][N])


if __name__ == "__main__":
    main()