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:
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)]

    dp = [-1 for _ in range(w + 1)]
    dp[0] = 0

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

    print(max(dp))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,p = map(int,input().split())
dp = [[0]*(p+1) for _ in range(n)]
W,V = [],[]
for _ in range(n):
    w,v = map(int,input().split())
    W.append(w)
    V.append(v)
for i in range(n):
    for j in range(p+1):
        if j -W[i]>=0:
            dp[i][j] = max(dp[i][j], dp[i-1][j],dp[i-1][j-W[i]] + V[i])
        else:
            dp[i][j] = max(dp[i][j], dp[i-1][j])
print(max(dp[-1]))

Submission status: Accepted

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

dp = [[0 for _ in range(W)] for _ in range(N)]

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

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

Submission status: Accepted

Solution code:
import numpy as np
N, W = map(int, input().rstrip().split(' '))
weight_array = np.zeros(W+1)

for _ in range(N):
  w, v = map(int, input().rstrip().split(' '))
  weight_array[w:] = np.maximum(weight_array[:-w]+v, weight_array[w:])
print(int(weight_array[-1]))

Submission status: Accepted

Solution code:
import numba as nb
import sys
import numpy as np
@nb.njit
def solve(w,weight,value):
    total=w
    dp = np.zeros(shape=(n + 1, w + 1), dtype=np.int64)
    for i in range(l):
        for w in range(total+1):
            if weight[i]<=w:
                dp[i][w]=max(value[i]+dp[i-1][w-weight[i]],dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    print(dp[l-1][total])
n,w=map(int,sys.stdin.readline().split())
weight=[0]*n
value=[0]*n
total=w
for i in range(n):
    x,y=map(int,sys.stdin.readline().split())
    weight[i]=x
    value[i]=y
l=len(weight)
solve(w,weight,value)

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

D = [0] * (w+1)

for i in range(n):
    for j in range(w,-1,-1):
        if j-A[i][0] >= 0:
            D[j] = max(D[j], D[j-A[i][0]] + A[i][1])
print(D[-1])

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
w, v = zip(*(map(int, input().split()) for _ in range(N)))

dp = [0] * (W+1)

for i in range(N):
    for j in range(W,0,-1):
        if j - w[i] >= 0 and dp[j] < dp[j - w[i]] + v[i]:
            dp[j] = dp[j - w[i]] + v[i] #jは重さ、w[i]も重さ、dp[j]は重さjの時の価値、v[i]は重さw[i]の時の価値
    if dp[w[i]] == 0 or dp[w[i]] < v[i]:
        dp[w[i]] = v[i]
print(max(dp))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
dp=[[0]*(w+1) for _ in range(n+1)]
for i in range(n):
    for j in range(w+1):
        if j>=wv[i][0]:
            dp[i+1][j]=max(dp[i][j],dp[i][j-wv[i][0]]+wv[i][1])
        else:
            dp[i+1][j]=dp[i][j]
print(dp[-1][-1])

Submission status: Accepted

Solution code:
n,k=map(int,input ().split())
w=[]
v=[]
for _ in range(n):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
dp=[[-1 for i in range(k+1)] for j in range(n+1)]
for i in range(k+1):
    dp[0][i]=0
for i in range(n+1):
    dp[i][0]=0
for j in range(1,k+1):
    for i in range(1,n+1):
        if j>=w[i-1]:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])
        else:
            dp[i][j]=dp[i-1][j]

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

Submission status: Accepted

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

    N, W = map(int, readline().split())
    lst = [list(map(int, readline().split())) for _ in [0] * N]
    
    dp = [[0] * (W + 1) for _ in [0] * N]

    for i in range(N):
        w, v = lst[i][0], lst[i][1]
        for sum_w in range(W + 1):
            if sum_w >= w:
                dp[i][sum_w] = max(dp[i][sum_w],
                                   dp[i - 1][sum_w - w] + v)
            dp[i][sum_w] = max(dp[i][sum_w], dp[i - 1][sum_w])
    print(max(dp[-1]))


resolve()

Submission status: Accepted

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

dp = np.zeros(W + 1, dtype = int)

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

for i in range(1, N+1):
    item[i][0], item[i][1] = map(int, input().split())

DP = [[0]*(W+1) for _ in range(N+1)]

for i in range(1, N+1):
    for w in range(0, W+1):
        DP[i][w] = DP[i-1][w]
        if w >= item[i][0]:
            DP[i][w] = max(DP[i][w], DP[i-1][w - item[i][0]] + item[i][1])

print(DP[N][W])

Submission status: Accepted

Solution code:
def main():
    N, W = map(int, input().split())
    dp = [0]*(W+1)

    for _ in range(N):
        w, v = map(int, input().split())
        for j in range(W,-1,-1):# 後ろから更新しないとダメ
            if j - w >= 0:
                dp[j] = max(dp[j], dp[j-w]+v)
    print(dp[W])    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N, W = map(int, input().split())
    w = [None] * N
    v = [None] * N

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

if __name__ == "__main__":
    main()

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 for i in range(w+1)] for i in range(n+1)]
#print(dp)
for i in range(n):
    weight,value=map(int,input().split())
    for j in range(w+1):
        if j < weight:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j],dp[i][j-weight]+value)
print(dp[n][w])

Submission status: Accepted

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


def max2(x, y):
    """ pythonの組み込み関数 max は2変数に対しては遅い！！ """
    if x > y:
        return x
    else:
        return y


def knapsack_weight(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    N, W = map(int, input().split())  # N: 品物の種類 W: 重量制限

    """ dp[weight <= W] = 重さ上限を固定した時の最大価値 """
    dp_min = 0  # 総和価値の最小値
    dp = [dp_min] * (W + 1)

    for _ in range(N):
        w, price = map(int, input().split())
        S = reversed(range(w, W + 1))
        for weight in S:
            dp[weight] = max2(dp[weight], dp[weight - w] + price)
    return dp[W]

#######################################################################################################


print(knapsack_weight(single=True))

Submission status: Accepted

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


def max2(x, y):
    """ pythonの組み込み関数 max は2変数に対しては遅い！！ """
    if x > y:
        return x
    else:
        return y


def knapsack_weight(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    N, W = map(int, input().split())  # N: 品物の種類 W: 重量制限

    """ dp[weight <= W] = 重さ上限を固定した時の最大価値 """
    dp_min = 0  # 総和価値の最小値
    dp = [dp_min] * (W + 1)

    for _ in range(N):
        w, price = map(int, input().split())
        if single:
            S = reversed(range(w, W + 1))
        else:
            S = range(w, W + 1)
        for weight in S:
            dp[weight] = max2(dp[weight], dp[weight - w] + price)
    return dp[W]

#######################################################################################################


print(knapsack_weight(single=True))

Submission status: Accepted

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


def max2(x, y):
    """ pythonの組み込み関数 max は2変数に対しては遅い！！ """
    if x > y:
        return x
    else:
        return y


def knapsack_weight(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    """ dp[weight <= W] = 重さ上限を固定した時の最大価値 """
    dp_min = 0  # 総和価値の最小値
    dp = [dp_min] * (W + 1)

    for item in range(N):
        if single:
            S = reversed(range(weight_list[item], W + 1))
        else:
            S = range(weight_list[item], W + 1)
        for weight in S:
            dp[weight] = max2(dp[weight], dp[weight - weight_list[item]] + price_list[item])
    return dp[W]

#######################################################################################################


N, W = map(int, input().split())                                # N: 品物の種類 W: 重量制限

price_list = []
weight_list = []
for _ in range(N):
    weight, price = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)

print(knapsack_weight(single=True))

################################################################################################################################################

Submission status: Accepted

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



N, W = map(int, input().split())                                # N: 品物の種類 W: 重量制限

price_list = []
weight_list = []
for _ in range(N):
    weight, price = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)


################################################################################################################################################

def max2(x,y):
    """ pythonの組み込み関数 max は２変数に対しては遅い！！ """
    if x>y:
        return x
    else:
        return y


dp_min = 0                                                      # 総和価値の最小値

""" dp[weight <= W] = 重さ上限を固定した時の"最大"価値 """
dp = [dp_min] * (W + 1)

for item in range(N):
    for weight in reversed(range(weight_list[item], W + 1)):
        dp[weight] = max2(dp[weight], dp[weight - weight_list[item]] + price_list[item])


print(dp[W])

Submission status: Accepted

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



M, W = map(int, input().split())                                # M: 品物の種類 W: 重量制限
single = True                                                   # True = 重複なし

price_list = [0]
weight_list = [0]
for _ in range(M):
    weight, price = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)


################################################################################################################################################

dp_min = 0                                                      # 総和価値の最小値

""" dp[item <= M ][weight <= W] = 重さ上限を固定した時の"最大"価値 """
dp = [[dp_min] * (W + 1) for _ in range(M + 1)]                 # 左端と上端の境界条件で W, M を一個ずつ多めに取る

""" 重さ 0 の時の境界条件 """
for item in range(M+1):
    dp[item][0] = 0                                             # 重さ 0 を実現するのに必要な品物の個数は 0 個

""" 品物 0 個の時の境界条件 """
# for weight in range(W+1):
#     dp[0][weight] = dp_min                                    # 0 種類の品物で実現できる重量は存在しない　（dpの初期化で自動的に課せる場合が多い）


for item in range(1,M+1):                                       # 境界条件を除いた M 回のループ（※ f[item] = g.f[item-i] の漸化式なので、list index out of range となる）
    for weight in range(1, W + 1):
        if weight < weight_list[item]:                          # weight (重量価値) < weight_list[item] (品物の重量) の時は無視してよい
            dp[item][weight] = dp[item - 1][weight]
        else:
            temp = dp[item - single][weight - weight_list[item]] + price_list[item]  # single = True: 重複なし
            if temp > dp[item-1][weight]:                       # max(dp[item-1][weight], temp)
                dp[item][weight] = temp
            else:
                dp[item][weight] = dp[item-1][weight]

print(dp[M][W])

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
dp = [0] * (w + 1)
for _ in range(n):
    wi, vi = map(int, input().split())
    for i in range(w, wi - 1, -1):
        dp[i] = max(dp[i], dp[i-wi] + vi)
print(dp[w])

Submission status: Accepted

Solution code:
def main():
    N, W = (int(i) for i in input().split())
    VW = [[int(i) for i in input().split()] for j in range(N)]
    dp = [[0]*(W+1) for _ in range(N+1)]

    for i in range(N):
        for j in range(W+1):
            if 0 <= j - VW[i][0]:
                dp[i+1][j] = max(dp[i][j], dp[i][j - VW[i][0]] + VW[i][1])
            else:
                dp[i+1][j] = dp[i][j]

    print(dp[N][W])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

dp = [[-1] * (W + 1) for i in range(N + 1)]
dp[0][0] = 0

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

print(max(dp[N]))

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
w = [None] * N
v = [None] * N

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

dp = [[-1] * (W + 1) for i in range(N + 1)]
dp[0][0] = 0

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

print(max(dp[N]))

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_d
N,W = map(int,input().split())
Goods_List=[]
for i in range(N):
    Goods_List.append(list(map(int,input().split())))

Sum_Weight = sum(map(lambda x:x[0],Goods_List))
dp = [[-1] * (W + 1) for i in range(N)]

for i in range(N):
    Current_Weight = Goods_List[i][0]
    Current_Value  = Goods_List[i][1]
    dp[i][0] = 0
    if (i == 0) & (Current_Weight <= W) :
        dp[i][Current_Weight] = Current_Value
    elif i > 0:
        Last_Search_List = [j for j, x in enumerate(dp[i-1]) if x > -1]
        Current_Search_List = list(map(lambda x:x+Current_Weight,Last_Search_List))
        ##まずは前回値を入れる
        for l in range(len(Last_Search_List)):
            Last_Search_Weight =  Last_Search_List[l] 
            dp[i][Last_Search_Weight] = dp[i-1][Last_Search_Weight]
        ##今回値と比べる
        for k in range(len(Current_Search_List)):
            Last_Search_Weight =  Last_Search_List[k] 
            Current_Search_Weight = Current_Search_List[k]
            if Current_Search_Weight > W:
                break
            else:
                dp[i][Current_Search_Weight] = max((dp[i-1][Last_Search_Weight] + Current_Value),
                                                   dp[i-1][Current_Search_Weight])


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

Submission status: Accepted

Solution code:
#n=int(input())
#n,k=map(int, input().split())
#a=[[0]*n for _ in range(3)]
n,we=map(int,input().split())
w=[0]*n
v=[0]*n
for i in range(n):
  w[i],v[i]=map(int,input().split())
dp=[[0]*(n+1) for _ in range(we+1)]
for i in range(1,we+1):
  for j in range(1,n+1):
    if(w[j-1]<=i):
    	dp[i][j]=max(v[j-1]+dp[i-w[j-1]][j-1],dp[i][j-1])
    else:
      dp[i][j]=dp[i][j-1]
print(dp[-1][-1])

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
w=[]
v=[]
jmax=100010
nmax=110
 
for i in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
    
DP= [[0]*jmax for i in range(nmax)]
 
 
def chmax(a,b):
    if a>b:
        return a
    else:
        return b
 
 
for i in range(N):
    for j in range(jmax):
        if  j-w[i]>=0:
            DP[i+1][j]=chmax(DP[i][j],DP[i][j-w[i]]+v[i])
        else:
            DP[i+1][j]=DP[i][j]
 
            
print(DP[N][W])

Submission status: Accepted

Solution code:
"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i,v_i<=100, 1<=W<=10000
"""
#-------------------------------------------------------------------------------
n ,W = map(int, input().split())
w=[0]*n
v=[0]*n
for i in range(n):
    x,y = map(int, input().split())
    w[i] = x
    v[i] = y
dp = [[0 for i in range(W+1)] for j in range(n+1)]
for i in range(n):
    for j in range(W+1):
        if j < w[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
#print(dp)
print(dp[n][W])

Submission status: Accepted

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

Submission status: Accepted

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

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

# dp[w]: n番目までのを使用して、重さwの時の価値
dp = [-1]*(W+1)

dp[0] = 0
for i in range(N):
    for j in reversed(range(W+1)):
        prew = j - w[i] 
        if ((prew >= 0) and (dp[prew] >= 0)):
            dp[j] = max(dp[j], dp[prew] + v[i])

ans = 0
for val in dp:
    ans = max(ans, val)

print(ans)

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
w,v=[],[]
for i in range(N):
  ww,vv=map(int,input().split())
  w.append(ww)
  v.append(vv)
dp=[[0]*(W+1) for i in range(N+1)]

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

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

Submission status: Accepted

Solution code:
def MI(): return map(int, input().split())
import sys
input = sys.stdin.readline
n,w = map(int,input().split())
#wv = [tuple(map(int,input().split())) for i in range(n)]
W=[]
V=[]
for i in range(n):
  a,b=MI()
  W.append(a)
  V.append(b)
dp = [0]*(w+1)
for i in range(n):
    for j in range(w,W[i]-1,-1):
        dp[j] = max(dp[j],dp[j-W[i]]+V[i])
print(max(dp))

Submission status: Accepted

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

dp = [[0 for i in range(W + 1)] for j in range(N + 1)]

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

print(dp[N][W])

Submission status: Accepted

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

dp = [[0 for i in range(W + 1)] for j in range(N + 1)]

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

print(max(dp[N]))

Submission status: Accepted

Solution code:
import numpy as np

N, W = [int(x) for x in input().split()]
items = [tuple(map(int, input().split())) for _ in range(N)]

#topdown
memo = np.zeros(shape = W+1, dtype = np.int64)

for w,v in items:
    memo[w:] = np.maximum( memo[w:], memo[:-w] + v)

print(memo[-1])

Submission status: Accepted

Solution code:
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8,i8,i8[:,:])")
def solve(N, W, wv):
    dp = np.zeros(shape=(N + 1, W + 1), dtype=np.int64)
    for i in range(1, N + 1):
        w, v = wv[i - 1]
        for j in range(1, W + 1):
            if j < w:
                dp[i, j] = dp[i - 1, j]
            else:
                dp[i, j] = max(dp[i - 1, j - w] + v, dp[i - 1, j])
    return dp[-1, -1]


def main():
    N, W = map(int, input().split())
    wv = np.zeros(shape=(N, 2), dtype=np.int64)
    for i in range(N):
        w, v = map(int, input().split())
        wv[i] = w, v

    ans = solve(N, W, wv)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8, i8)")
def chmax(a, b):
    if a > b:
        return a
    else:
        return b


@nb.njit("i8(i8,i8,i8[:,:])")
def solve(N, W, wv):
    dp = np.zeros(shape=(N + 1, W + 1), dtype=np.int64)
    for i in range(1, N + 1):
        w, v = wv[i - 1]
        for j in range(1, W + 1):
            if j < w:
                dp[i, j] = dp[i - 1, j]
            else:
                dp[i, j] = chmax(dp[i - 1, j - w] + v, dp[i - 1, j])
    return dp[-1, -1]


def main():
    N, W = map(int, input().split())
    wv = np.zeros(shape=(N, 2), dtype=np.int64)
    for i in range(N):
        w, v = map(int, input().split())
        wv[i] = w, v

    ans = solve(N, W, wv)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8, i8)")
def chmax(a, b):
    if a > b:
        return a
    else:
        return b


@nb.njit("i8(i8,i8,i8[:,:])")
def solve(N, W, wv):
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        w, v = wv[i - 1]
        for j in range(1, W + 1):
            if j < w:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = chmax(dp[i - 1][j - w] + v, dp[i - 1][j])
    return dp[-1][-1]


def main():
    N, W = map(int, input().split())
    wv = np.zeros(shape=(N, 2), dtype=np.int64)
    for i in range(N):
        w, v = map(int, input().split())
        wv[i] = w, v

    ans = solve(N, W, wv)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

N,W=map(int,input().split())
w=[]
v=[]
jmax=100010
nmax=110

for i in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
    
DP= [[0 for j in range(jmax)] for i in range(nmax)]


def chmax(a,b):
    if a>b:
        return a
    else:
        return b


for i in range(N):
    for j in range(jmax):
        if  j-w[i]>=0:
            DP[i+1][j]=chmax(DP[i][j],DP[i][j-w[i]]+v[i])
        else:
            DP[i+1][j]=DP[i][j]

            
print(DP[N][W])

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
dp=[0]+[-1]*w
for i in range(n):
    weight,value=map(int,input().split())
    for j in range(w-weight,-1,-1):
        if dp[j]!=-1:
            sum_weight=j+weight
            dp[sum_weight]=max(dp[sum_weight],dp[j]+value)

print(max(dp))

Submission status: Accepted

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

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

weight = []
value = []

for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

#dp = [[0]*110]*11010
dp=[[0 for _ in range(W+1)] for _ in range(N+1)]
#dp=[[0 for _ in range(110)] for _ in range(11010)]


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

print(dp[N][W])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)


# map(int, sys.stdin.read().split())


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


def main():
    N, W = map(int, input().split())
    item = []
    dp = [[0] * (W + 1) for _ in range(N)]

    for i in range(N):
        w, v = map(int, input().split())
        item.append((w, v))

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
#import numpy as np



def main():

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

    dp = [0] * (W+2)

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

        for j in range(W+1,w-1,-1):
            dp[j] =max(dp[j-w] +v ,dp[j])

    print(dp[W])



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
S = [[0 for j in range(2)] for i in range(N+1)]

DP= [[0 for j in range(100010)] for i in range(110)]
def chmax(a,b):
    if a>b:
        return a
    else:
        return b


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


for i in range(N):
    for j in range(W+1):
        if j-S[i][0]>=0:
            
            DP[i+1][j]=chmax(DP[i][j],DP[i][j-S[i][0]]+S[i][1])
        
        else:
            DP[i+1][j]=DP[i][j]
        
print(DP[N][W])

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wv = [[0 for i in range(2)] for j in range(N)]
dp = [[0 for i in range(N+1)] for j in range(W+1)]

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

for i in range(N):
  for w in range(1,W+1):
    if w < wv[i][0]:
      dp[w][i+1] = dp[w][i]
    else:
      dp[w][i+1] = max(dp[w-wv[i][0]][i]+wv[i][1], dp[w][i])

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
dp = [[0 for _ in range(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):
        if j - w >= 0:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
        else:
            dp[i][j] = dp[i-1][j]

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())
dp = [[0] * (W+1) for _ in range(N+1)]
for i in range(N):
    for sum_w in range(W+1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w-w[i]] + v[i])
        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,k = map(int,input().split())
m = [0]*n
v = [0]*n
dp = [[0] * (k+1) for i in range(n)]
for i in range(n):
    m[i],v[i] = map(int,input().split())

for j in range(k+1):
    dp[0][j] = v[0] if j >= m[0] else 0

for i in range(1,n):
    for j in range(k+1):
        if j >= m[i]:
            dp[i][j] = max(dp[i-1][j-m[i]]+v[i],dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
#print(dp)
print(dp[i][j])

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**7)
inf = 10**17
mod = 10**9+7

n, w = map(int, input().split())
weight = []
value = []
for _ in range(n):
    x, y = map(int, input().split())
    weight.append(x)
    value.append(y)


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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
w=0
v=0
w_list=[]
v_list=[]
dp=[0]*(W+1)
for i in range (N):
    w,v=map(int,input().split())
    w_list.append(w)
    v_list.append(v)
for i in range (N):
    for j in range(W,-1,-1):
        if j>=w_list[i]:
            dp[j]=max(dp[j],dp[j-w_list[i]]+v_list[i])
print(dp[-1])

Submission status: Accepted

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

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

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

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

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