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:
N, W = map(int, input().split())
goods = [list(map(int, input().split())) for i in range(N)]
dp = [[0]*(N+1) for i in range(W+1)]
for i in range(W):
    for j in range(N):
        if i+1 >= goods[j][0]:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i+1-goods[j][0]][j]+goods[j][1])
        else:
            dp[i+1][j+1] = dp[i+1][j]
print(dp[W][N])

Submission status: Accepted

Solution code:
# dp[i][w]: i個目までの品物から、重さwの以下に収まる範囲で取れる価値の最大値

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 i in range(1,n+1):
  w,v=wv[i-1]
  for j in range(1,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[-1][-1])

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
import numpy as np
n,W = mi()
a = [tuple(int(i) for i in input().split()) for _ in range(n)]
dp = np.array([0]*(W+1))
for w,v in a:
    ed = W+1-w
    dp[w:W+1] = np.maximum(dp[w:W+1], dp[0:W+1-w] + v)
print(dp[W])

Submission status: Accepted

Solution code:
#EDPC D

#dp[ i ][ sum_w ] := i-1 番目までの品物から重さが 
# sum_w以下となるときの、価値の総和の最大値

#dpのindexはややこしくなりがち

N,W=map(int,input().split())
w,v=[0],[0]#w,vのindexと品物の番号を合わせるため、頭に0を追加
def main():
  for _ in range(N):
      wi,vi=map(int,input().split())
      w.append(wi)
      v.append(vi)

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


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

  print(dp[N][W])
main()

Submission status: Accepted

Solution code:
N, L = map(int, input().split())
W = []
V = []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)


dp = [[0] + [-1] * (L+3) for _ in range(N+3)]
dp[0] = [0] * (L+4)

for w in range(L+1):
    for i in range(1, N+1):
        dp[i][w] = max(dp[i-1][w], dp[i-1][w - W[i-1]] + V[i-1]
                       ) if w - W[i-1] >= 0 else dp[i-1][w]
#print(*dp, sep='\n')
print(dp[N][L])

Submission status: Accepted

Solution code:
#d
n,W=map(int,input().split())
w=[0]
v=[0]
for i in range(n):
    x,y=map(int,input().split())
    w.append(x)
    v.append(y)

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

for i in range(1,n+1):
    for j in range(W+1):
        dp[i][j]=dp[i-1][j]#if文Falseのときの値に困らないように
        if j-w[i]>=0:
            dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i])
print(dp[n][W])

Submission status: Accepted

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

#output
import numpy as np
dp = np.zeros((N+1, W+1), int)

for i in range(N):
    dp[i+1, w[i]:] = np.maximum(dp[i, w[i]:], dp[i, :-w[i]] + v[i])
    dp[i+1, :w[i]] = dp[i, :w[i]]

print(dp[-1, -1])

Submission status: Accepted

Solution code:
import sys

import numpy as np

input = sys.stdin.readline
N, weights = map(int, input().split())

# dp = [0] * (weights + 1)
dp = np.zeros(weights + 1, dtype=np.int64)

while N:
    w, v = map(int, input().split())
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
    # for i in range(weights, -1, -1):
    #     if i - w >= 0:
    #         dp[i] = max(dp[i], dp[i - w] + v)
    # print(dp)
    N -= 1
print(dp[-1])

Submission status: Accepted

Solution code:
import numpy as np

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

# dp = [0] * (weights + 1)
dp = np.zeros(weights + 1, dtype=np.int64)

while N:
    w, v = map(int, input().split())
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
    # for i in range(weights, -1, -1):
    #     if i - w >= 0:
    #         dp[i] = max(dp[i], dp[i - w] + v)
    # print(dp)
    N -= 1
print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

N, W = MAP()
wv = [LIST() for _ in range(N)]

dp = np.zeros(W+1, dtype=np.int64)
for w, v in wv:
	np.maximum(dp[w:], dp[:-w]+v, out=dp[w:])

print(dp[W])

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

N, W = MAP()
w, v = ZIP(N)

dp = [0]*(W+1)

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

Submission status: Accepted

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

dp = []
for i in range(n+1):
    o = []
    for j in range(w+1):
        o.append(0)

    dp.append(o)


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

        else:
            dp[i+1][j] = max(a[i] + dp[i][j - p[i]], dp[i][j])

print(dp[n][w])

Submission status: Accepted

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

dp = []
for i in range(n+1):
    o = []
    for j in range(w+1):
        o.append(0)

    dp.append(o)


for i in range(n):
    for j in range(w+1):
        if p[i] > j:
            dp[i+1][j] = dp[i][j]

        else:
            dp[i+1][j] = max(a[i] + dp[i][j - p[i]], dp[i][j])

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

Submission status: Accepted

Solution code:
# 埋める配列
# dp[i][w] : i番目までのお菓子で、重さの総和がw以下となる選び方の最大値

# 計算方法
# dp[0][j] = 0
# dp[i][j] = max(dp[i - 1][j],              #i番目のお菓子を使わないパターン
#               dp[i - 1][j - wi] + vi)     #i番目のお菓子を使ったパターン

# 埋める順序
# iが小さい順、jは好きな順

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

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

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

answer = -1
for d in dp:
    answer = max(answer, max(d))
print(answer)

Submission status: Accepted

Solution code:
# 埋める配列
# dp[w] : 入っている重さがwのときの価値の最大値

# 計算方法
# dp[0][0] = 0
# dp[w] = max(dp[w - wi] + vi)

# 埋める順序
# 後ろから

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

dp = [0] * (W + 1)
for i in range(N):
    wi, vi = wv[i]
    for j in range(W, -1, -1):
        if j - wi >= 0:
            dp[j] = max(dp[j], dp[j - wi] + vi)
            
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 for _ in range(100005)] for _ in range(105)]
for i in range(N):
    for j in range(W+1):
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if j - weight[i] >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-weight[i]]+value[i])
print(dp[N][W])

Submission status: Accepted

Solution code:
def knapSack(W, wt, val, n): 
    K = [[0 for x in range(W+1)] for x in range(n+1)] 
  
    # Build table K[][] in bottom up manner 
    for i in range(n+1): 
        for w in range(W+1): 
            if i==0 or w==0: 
                K[i][w] = 0
            elif wt[i-1] <= w: 
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]) 
            else: 
                K[i][w] = K[i-1][w] 
  
    return K[n][W] 
n,w=map(int,input().split())

wt = []
val = []

for i in range(n):
    wtt,vall=map(int,input().split())
    wt.append(wtt)
    val.append(vall)
ans = knapSack(w,wt,val,n)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

W, V = [0], [0]
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
# dp[i][sum_w] := i-1 番目までの品物から重さが sum_w を超えないように選んだときの、価値の総和の最大値
# dp[i + 1][sum_w], dp[i][sum_w - w[i]] + v[i]

dp = np.array([0] * (_W + 1))
for i in range(1, N + 1):
    w, v = W[i], V[i]
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
    # print(dp)

# print('dp')
print(dp.max())

Submission status: Accepted

Solution code:
import numpy as np

N, W = map(int, input().split())
dp = np.zeros(W + 1, dtype=np.int)
for _ in range(N):
  w, v = map(int, input().split())
  dp[w:] = np.maximum(dp[w:], dp[:-w] + v)
print(dp[W])

Submission status: Accepted

Solution code:
# D - Knapsack 1
def solve_knapsack(weight_limit: int, weights: list, values: list) -> int:
    dp = [0] * (weight_limit + 1)  # dp[i] := optimum value at weight i
    for w, v in zip(weights, values):
        for cur_w in range(weight_limit, w - 1, -1):
            dp[cur_w] = max(dp[cur_w], dp[cur_w - w] + v)
    return dp[-1]


def main():
    N, W, *WV = map(int, open(0).read().split())
    print(solve_knapsack(W, WV[::2], WV[1::2]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
N, W = map(int, input().split())
def knapsack(n, w):
    # dp[i][j] : i番目の品物で重さj以下の価値の最大値
    dp = np.zeros([N+1, W+1], dtype='int64')
    # forは関数の中で回す。
    for i in range(N):
        w, v = map(int, input().split())
        # i+1番目でwより小さい場合は、i番目と変更なし
        dp[i+1][:w] = dp[i][:w]
        dp[i+1][w:] = np.maximum(dp[i][w:], dp[i][:-w] + v)
    return dp[-1][-1]

print(knapsack(N, W))

Submission status: Accepted

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

#print(dp)
ans = 0
for val in dp[n-1]:
    if val > ans:
        ans = val
print(ans)

Submission status: Accepted

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

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

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

# print(*dp, sep='\n')
print(dp[N][W])

Submission status: Accepted

Solution code:

import numpy as np

n, w = map(int, input().split())
dp = np.full(w + 1, 0, dtype=int)

# dp[w] : wまでitemを取捨選択した際の最大価値

for _ in range(n):
    wi, vi = map(int, input().split())
    dp[wi:] = np.maximum(dp[:-wi] + vi, dp[wi:])
print(dp[-1])

Submission status: Accepted

Solution code:
def submit():
    n, w = map(int, input().split())
    dp = [[0] * (w + 1) for _ in range(n + 1)]

    # dp[i][j] = item iまでで重さjの時に実現する最大価値
    for i in range(1, n + 1):
        wi, vi = map(int, input().split())
        for j in range(1, w + 1):
            if 0 <= j - wi <= w:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wi] + vi)
            else:
                dp[i][j] = dp[i - 1][j]    
    print(max(dp[n]))

submit()

Submission status: Accepted

Solution code:
from numpy import*
f=lambda:map(int,input().split())
N,W=f()
T=zeros(W+1,int)
exec('w,v=f();T[w:]=maximum(T[w:],T[:-w]+v);'*N)
print(T[-1])

Submission status: Accepted

Solution code:
from numpy import *
N,W=map(int,input().split())
dp=zeros(W+1,int)
for i in range(N):
    w,v=map(int,input().split())
    dp[w:]=maximum(dp[:-w]+v,dp[w:])
print(dp[-1])

Submission status: Accepted

Solution code:
from numpy import *
N,W=map(int,input().split())
dp=zeros(W+1,"i8")
for i in range(N):
    w,v=map(int,input().split())
    dp[w:]=maximum(dp[:-w]+v,dp[w:])
print(dp[-1])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N,W=map(int,input().split())

jwels=[]

for _ in range(N):
    jwels.append(list(map(int,input().split())))

dp=[-1]*(W+1)
dp[0]=0

for w,v in jwels:
    for i in range(W+1)[::-1]:
        if dp[i]!=-1 and i+w<=W:
            dp[i+w]=max(dp[i]+v,dp[i+w])
            
print(max(dp))

Submission status: Accepted

Solution code:
from numpy import *
N,W=map(int,input().split())
dp=zeros(W+1)
for i in range(N):
    w,v=map(int,input().split())
    dp[w:]=maximum(dp[:-w]+v,dp[w:])
print(int(dp[-1]))

Submission status: Accepted

Solution code:
from numpy import *
N,W=map(int,input().split())
dp=zeros(W+1,dtype=int)
for i in range(N):
    w,v=map(int,input().split())
    dp[w:]=maximum(dp[:W-w+1]+v,dp[w:])
print(dp[-1])

Submission status: Accepted

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

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

dp=[[0]*(W+1) for _ 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+1][j],dp[i][j-w[i]]+v[i])
    dp[i+1][j]=max(dp[i+1][j],dp[i][j])
print(dp[N][W])

Submission status: Accepted

Solution code:
n,w = map(int,input().split())
w_i = [0]
v_i = [0]
for i in range(n):
  temp = list(map(int,input().split()))
  w_i.append(temp[0])
  v_i.append(temp[1])

dp = []
for i in range(n+1):
  temp = []
  for j in range(w+1):
    temp.append(0)
  
  dp.append(temp)

for i in range(1,n+1):
#  print(dp)
  for j in range(w+1):
    temp_1 = -float("inf")
    if j-w_i[i] >= 0:
      temp_1 = dp[i-1][j-w_i[i]] + v_i[i]
    
    temp_2 = dp[i-1][j]
    
    if temp_1 <= temp_2:
      dp[i][j] = temp_2
    elif temp_2 < temp_1:
      dp[i][j] = temp_1
      
print(dp[n][w])

Submission status: Accepted

Solution code:
N, W = [int(i) for i in input().split()]
weight, value = [0] * (N + 1), [0] * (N + 1)
for i in range(1, N + 1):
    weight[i], value[i] = [int(i) for i in input().split()]
#%%
dp = [[0] * (W + 1) for _ in range(N + 1)]

#%%
for i in range(1, N + 1):
    for j in range(1, W + 1):
        if weight[i] <= j:
            dp[i][j] = max(value[i] + dp[i - 1][j - weight[i]], dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]
print(int(dp[-1][-1]))

Submission status: Accepted

Solution code:
from sys import stdin
#from collections import deque
#from math import sqrt, floor, ceil, log, log2, log10, pi, gcd, sin, cos, asin
def ii(): return int(stdin.readline())
def fi(): return float(stdin.readline())
def mi(): return map(int, stdin.readline().split())
def fmi(): return map(float, stdin.readline().split())
def li(): return list(mi())
def lsi():
    x=list(stdin.readline())
    x.pop()
    return x
def si(): return stdin.readline()
############# CODE STARTS HERE #############
n, w=mi()
a=[[0] for _ in range(n+1)]
for _ in range(w):
    a[0].append(0)
for i in range(1, 1+n):
    x, v=mi()
    for j in range(1, 1+w):
        if j>=x:
            a[i].append(max(a[i-1][j-x]+v, a[i-1][j]))
        else:
            a[i].append(a[i-1][j])
print(a[-1][-1])

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
a = [[int(i) for i in input().split(" ")] for j in range(n)]
dp = [[0]*(w+1) for i in range(n+1)]
for i in range(1, n+1):
    w_, v_ = a[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])
print(dp[n][w])

Submission status: Accepted

Solution code:
# edpc e dp

import itertools
from math import factorial
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce

sys.setrecursionlimit(4100000)
INF = 1 << 60
MOD = 10 ** 9 + 7

# ここから書き始める
N, W = map(int, input().split())
w = [0 for _ in range(N)]
v = [0 for _ in range(N)]
for i in range(N):
    w[i], v[i] = map(int, input().split())
dp = [[0 for j in range(W + 1)] for i in range(N)]
for i in range(W + 1):
    if i == w[0]:
        dp[0][i] = v[0]
    else:
        dp[0][i] = 0
for i in range(1, N):
    for j in range(W + 1):
            dp[i][j] = dp[i - 1][j]
            if j >= w[i]:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i])
ans = -INF
for i in range(W + 1):
    ans = max(ans, dp[-1][i])
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, k = map(int, readline().split())
dp = np.zeros(k + 1)

for i in range(n):
    w, c = map(int, readline().split())
    dp[w:] = np.maximum(dp[w:], dp[:-w] + c)

print(int(dp[-1]))

Submission status: Accepted

Solution code:
def main():
    n, w = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(n)]
    dp = [[None]*(w+1) for _ in range(n+1)]
    dp[0] = [0]*(w+1)
    for i in range(1, n+1):
        wi, vi = wv[i-1]
        di = dp[i]
        dio = dp[i-1]
        for j in range(wi):
            di[j] = dio[j]
        for j in range(wi, w+1):
            dion = dio[j-wi]+vi
            if dion > dio[j]:
                di[j] = dion
            else:
                di[j] = dio[j]
    print(dp[-1][-1])

if __name__ == "__main__":
    main()

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())
  dp[w:] = np.maximum(dp[w:],dp[:-w]+v)
print(dp[-1])

Submission status: Accepted

Solution code:
n,wei = [int(x) for x in input().split()]
w = []
v = []
for _ in range(n):
    a,b = [int(x) for x in input().split()]
    w.append(a)
    v.append(b)
dp = [[-1]*(wei+1) for x in range(n+1)]
for i in range(wei+1):
    dp[0][i] = 0

for i in range(n):
    for j in range(wei+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[n][wei])

Submission status: Accepted

Solution code:
N, W, *A = map(int, open(0).read().split())
A = zip(*[iter(A)]*2)

# dp[i][j] iまでの品物からいくつか選んで重さの総和がjのときの価値の最大値
dp = [[0]*(W+1) for _ in range(N+1)]

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

print(max(dp[N]))

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
weight=[]
value=[]
for i in range(n):
    x,v=map(int,input().split())
    weight.append(x)
    value.append(v)
    
dp=[[0 for i in range(w+1)]for i in range(n+1)]

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

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

Submission status: Accepted

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

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

def main(): #startline-------------------------------------------
    n,W = map(int,input().split())
    wv = [list(map(int,input().split())) for i in range(n)]
    w = [wv[i][0] for i in range(n)]
    v = [wv[i][1] for i in range(n)]
    dp = [[0]*(W+1) for i in range(n+1)]
    for i in range(W):
        dp[n][i] = 0
    for i in range(n-1,-1,-1):
        for j in range(W+1):
            if j < w[i]:
                dp[i][j] = dp[i+1][j]
            else:
                dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])
    print(dp[0][W])
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

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

Submission status: Accepted

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

w = [0] * (N + 1)
v = [0] * (N + 1)
for i in range(1, N + 1):
    w[i], v[i] = map(int, input().split())
MAX_W = 1000000
dp = [[0] * (W + 1) for _ in range(N + 1)]

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

print(dp[N][W])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
inf = 10**8
dp = [-inf] * (m + 1)
dp[0] = 0

for i in range(n):
    w, v = map(int, input().split())
    for j in range(m - w, -1, -1):
        if dp[j] != -inf:
            dp[j + w] = max(dp[j + w], dp[j] + v)
print(max(dp))

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 j in range(W + 1):
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        if j + w[i] <= W:
            dp[i + 1][j + w[i]] = max(dp[i + 1][j + w[i]], dp[i][j] + v[i])
print(dp[N][W])

Submission status: Accepted

Solution code:
MAX_N = 110
MAX_W = 10 ** 5 + 100
N, W = map(int, input().split())
w = [0] * MAX_N
v = [0] * MAX_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, W = list(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 = list(map(int, input().split()))
    for j in range(0, W+1):
        if j >= w:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
        dp[i][j] = max(dp[i][j], dp[i-1][j])

print(dp[N][W])

Submission status: Accepted

Solution code:
MAX_N = 110
N, W = map(int, input().split())
weight = [0] * MAX_N
value = [0] * MAX_N
for i in range(N):
    weight[i], value[i] = map(int, input().split())
dp = [[0] * (W + 1) for _ in range(MAX_N)]
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])
# for l in dp:
#     print(l)
print(dp[N][W])

Submission status: Accepted

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

# dp[i][j]: i番目までの品物から重さの合計がj以下となるように選んだときの価値の最大値
dp = [[0]*(w+1) for _ in range(n+1)]

for i in range(n):
    w_i, v_i = wv[i]
    for j in range(w+1):
        # i番目の品物を選ぶ
        if j - w_i >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-w_i] + v_i)
        # i番目の品物を選ばない
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])

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

Submission status: Accepted

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

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

for i in range(1, n+1):
    wi, vi = wv[i-1]
    for j in range(1, w+1):
        if j < wi:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] + vi)
print(dp[-1][-1])

Submission status: Accepted

Solution code:
def main():
    goods, weight_limit = map(int, input().split())
    weight = []
    value = []
    for _ in range(goods):
        w, v = map(int, input().split())
        weight.append(w)
        value.append(v)
    dp = [[0 for _ in range(weight_limit + 1)] for _ in range(goods + 1)]
    for i in range(goods):
        for j in range(weight_limit + 1):
            if j >= weight[i]:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])
            else:
                dp[i + 1][j] = dp[i][j]
    print(dp[-1][-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def rr(): return input().rstrip()
def rri(): return int(rr())
def rrl(): return list(map(int, rr().split()))
def rrt(): return tuple(map(int, rr().split()))
from collections import defaultdict
def mus(d=lambda: 0): return defaultdict(lambda: defaultdict(d))
def dd0(d=lambda: 0): return defaultdict(d)
def ms(x, y, d=0): return [[0]*y for i in range(x)]
def ar(x, d=0): return [d]*x
def ppm(m, n=0, x=0, y=0): print("\n".join(("\t".join((str(m[j][i]) for j in range(y or n))) for i in range(x or n))))
def ppa(a, n): print("\t".join(map(str, a[0:n])))
def ppl(a=0, x=[1]): x[0]=a or (x[0]+1); print("-"+"- -"*14+"-# "+str(x[0]-2)+" #-"+"- -"*14+"-")
def fltn(a): (i for sub in a for i in sub)
def yn(x): return "YES" if x else "NO"
from itertools import accumulate
from itertools import groupby
def grp(x): return ((i, sum(1 for _ in g)) for i, g in groupby(x))
import math
#def rnar(): return (*rrl(), rrl())
#def rn(): return (*rrl(),)
def dpp(a, b=""): print(")#| {} |#(o) ? {} ? (".format(a, b))

def read():
    n, w = rrl()
    l = [rrt() for _ in range(n)]

    return n, w, l

def solve(n, w, l):
    dp = ms(w+1, n+1)

    for wi in range(1, w+1):
        for ii in range(1, n+1):
            if l[ii-1][0] > wi:
                dp[wi][ii] = dp[wi][ii-1]
            else:
                dp[wi][ii] = max(
                        dp[wi][ii-1],
                        dp[wi-l[ii-1][0]][ii-1] + l[ii-1][1],
                        )
    #ppm(dp, w+1, n+1)

    ans = dp[w][n]
    return ans

if __name__ == "__main__":
    #test_count = rri()
    test_count = 1
    for _ in range(test_count):
        input_data = read()
        result = solve(*input_data)
        print(result)

Submission status: Accepted

Solution code:
def knapsack(N, W, weight, value):
  inf = float("inf")
  dp = [[-inf]*(W+1) for _ in range(N+1)]
  for i in range(W+1):
    dp[0][i] = 0
  
  for i in range(N):
    for j in range(W+1):
      if weight[i] <= j:
        dp[i+1][j] = max(dp[i][j], dp[i][j-weight[i]]+value[i])
      else:
        dp[i+1][j] = dp[i][j]
  return dp[N][W]
  
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)

print(knapsack(N, W, weight, value))

Submission status: Accepted

Solution code:
import sys


def main():
    input = sys.stdin.readline

    N, W = map(int, input().split())
    dp = [0] * (W + 1)

    WV = (map(int, input().split()) for _ in range(N))

    for w, v in WV:
        for j in range(W, w - 1, -1):
            tmp = dp[j - w] + v
            if tmp > dp[j]:
                dp[j] = tmp

    print(dp[-1])


main()

Submission status: Accepted

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

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] = max(dp[i][j-w[i]]+v[i], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[N][W])