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
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, W = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    dp=[0]*(W+1)
    for i in range(N):
        w,v=S[i]
        j=W
        while j-w>=0:
            dp[j]=max(dp[j-w]+v,dp[j])
            j-=1

    print(dp[-1])



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
N, W = map(int, input().split())
dp = np.zeros((N, W+1), dtype = "int64")
for i in range(N):
    w, v = map(int, input().split())
    dp[i,-w:] = dp[i-1, -w:] #残りの重さW-w以上にするためには、荷物を入れられない。
    dp[i, :W-w+1] = np.fmax(dp[i-1, :W-w+1], dp[i-1, w:]+v)
print(dp[N-1, 0])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
Ws = []
Vs = []

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

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

for i in range(W+1):
  if i >= Ws[0]:
    Ans[0][i] = Vs[0]

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

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

Submission status: Accepted

Solution code:
def knapsack(w,val,W,n,t):
    for i in range(1,n+1):
        for j in range(1,W+1):
            if w[i-1]<=j:
                t[i][j]=max(val[i-1]+t[i-1][j-w[i-1]],t[i-1][j])
            else:
                t[i][j]=t[i-1][j]
    return t[n][W]            
n,W=map(int,input().split())                
w=[]
val=[]
t=[[0 for x in range(W+1)] for x in range(n+1)] 
for i in range(0,n):
    a,b=map(int,input().split())
    w.append(a)
    val.append(b)
ans=knapsack(w,val,W,n,t)
print(ans)

Submission status: Accepted

Solution code:
[n, w] = map(int, input().split())
weights = []
values = []
for i in range(n):
    weight, value = [int(i) for i in input().split()]
    weights.append(weight)
    values.append(value)
dp = [[0 for _ in range(w+1)] for _ in range(n+1)]
for i in range(n):
    for weight in range(w+1):
        if weight - weights[i] >= 0:
            dp[i+1][weight] = max(dp[i][weight-weights[i]] + values[i], dp[i+1][weight])
        dp[i+1][weight] = max(dp[i+1][weight], dp[i][weight])

print(dp[n][w])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N, W = MI()
inp = LI2(N)
w = [inp[i][0] for i in range(N)]
v = [inp[i][1] for i in range(N)]
dp = FILL2(0,N+1,W+1)
for i in range(N):
    for j in range(W+1):
        if j+w[i]<=W:
            dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]],dp[i][j]+v[i])
        dp[i+1][j] = max(dp[i+1][j],dp[i][j])
print(max(dp[N]))

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
val=[0]*n
wt=[0]*n
dp=[[0 for x in range(w+1)] for x in range(n+1)] 
for i in range(n):
  a,b=map(int,input().split())
  wt[i]=a
  val[i]=b
for i in range(1,n+1):
    for j in range(1,w+1):
        if(wt[i-1] <= j):
            dp[i][j]=max(val[i-1] + dp[i-1][j-wt[i-1]] , dp[i-1][j])
        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] * (W+1) for _ in range(n+1)]
w = []
v = []
for i in range(n):
    w_,v_ = map(int,input().split())
    w.append(w_)
    v.append(v_)
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:
def mips():
    return map(int,input().split())
def chmax(DP,b,weight,number):
    if DP[number+1][weight] < b : 
        DP[number+1][weight] = b
        return True
    return False    
N,W = mips()
Poids = []
Valeur = []
for i in range(N):
    weight,value = mips()
    Poids.append(weight)
    Valeur.append(value)
DP = [[0] * (2*W) for i in range(N+1)]
for i in range(N):
    for sum_p in range(0,W+1):
        if sum_p - Poids[i] >= 0:
            chmax(DP,DP[i][sum_p-Poids[i]] + Valeur[i],sum_p,i)
        chmax(DP,DP[i][sum_p],sum_p,i)
print(DP[N][W])

Submission status: Accepted

Solution code:
from sys import stdin, stdout
from collections import deque, defaultdict
import math as m

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

INF, NINF = float('inf'), float('-inf')

def main():
	n, W = rli()
	items = []
	for _ in range(n):
		w, v = rli()
		items.append((w, v))
	dp = [0 for _ in range(W + 1)]
	for w, v in items:
		for i in range(W, -1, -1):
			if i - w >= 0:
				dp[i] = max(dp[i], dp[i-w] + v)
	print(dp[-1])
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,W= map(int,input().split())
ans=[[0 for e in range(W+1)] for f in range(N+1)]
for i in range(N):
 w,v=map(int,input().split())
 for k in range(0,w):
  ans[i+1][k]=ans[i][k]
 for j in range(w,W+1):
  ans[i+1][j]=max(ans[i][j-w]+v,ans[i][j])
print(max(ans[N]))

Submission status: Accepted

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

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

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
import numpy as np
 
N,Max_W = map(int,input().split())
 
dp = [0 for _ in range(Max_W + 1)]
dp = np.array(dp)
 
for i in range(N):
    w,v = map(int,input().split())
    a = dp[:-w] + v
    b = dp[w:]
    m = np.maximum(a,b)
    dp[w:] = m
print(dp[-1])

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
kpsk_list = [list(map(int, input().split())) for _ in range(N)]
#print(kpsk_list)
dp = [[0]*(W+1) for _ in range(N+1)]
#print(dp)
for n in range(1, N+1): #何個目までのアイテムを考慮するか
  for w in range(W+1): #各重さでの価値の最大値を求める.
    #print(f"n:{n},w:{w}")
    if w - kpsk_list[n-1][0] < 0: 
      dp[n][w] = dp[n-1][w]
    else:
      dp[n][w] = max(dp[n-1][w], dp[n-1][w - kpsk_list[n-1][0]] + kpsk_list[n-1][1])
    #print(dp)

print(dp[N][W])
#dp[n]について各重さsum_w(=0~W)の時の最大価値をdpテーブルに保存していく.

Submission status: Accepted

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

Ws = []
Vs = []

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


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

if Ws[0] <= W:
  for i in range(Ws[0], W+1):
    S[0][i] = Vs[0]

for weight in range(W+1):
  for item_num in range(N-1):
    if weight - Ws[item_num+1] < 0:
      S[item_num+1][weight] = max(S[item_num+1][weight], S[item_num][weight])
    else:
      S[item_num+1][weight] = max(S[item_num+1][weight], S[item_num][weight-Ws[item_num+1]] + Vs[item_num+1], S[item_num][weight])

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
WV=[]
for i in range(N):
    WV.append(list(map(int,input().split())))
dp=[[0 for j in range(W+1)] for i in range(N+1)]
dp[0]=[-1e-30 for i in range(W+1)]
dp[0][0]=0
for i in range(1,N+1):
    for j in range(W+1):
        if j-WV[i-1][0]>=0:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-WV[i-1][0]]+WV[i-1][1])
        else:
            dp[i][j]=dp[i-1][j]
print(int(dp[N][W]))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_d

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

weights, profits = [], []

for i in range(N):
    w, p = map(int, input().split())
    weights.append(w)
    profits.append(p)

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

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

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

Submission status: Accepted

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

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

for i in range(n):
    for j in range(w + 1):
        if j == 0:
            nw = wv[i][0]
            if nw <= w:
                dp[i][nw] = wv[i][1]

        elif dp[i - 1][j] != 0:
            nw = wv[i][0] + j
            if nw <= w:
                dp[i][nw] = max(dp[i][nw], dp[i - 1][j] + wv[i][1])

        dp[i][j] = max(dp[i - 1][j], dp[i][j])
print(max(dp[-1]))

Submission status: Accepted

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

K = [[0 for x in range(W+1)] for y in range(N+1)]

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:
#			print("ayo")
			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]
print(K[N][W])

Submission status: Accepted

Solution code:
n,W=[int(j) for j in input().split()]
wv=[[int(j) for j in input().split()]for i in range(n)]
import numpy as np
dp=np.zeros(W+1,dtype=np.int64)
for w,v in wv:
    dp[w:]=np.maximum(dp[w:],dp[:-w]+v)
print(dp.max())

Submission status: Accepted

Solution code:
import numpy as np

n, w = map(int, input().split())
DP = np.zeros((n, w + 1), dtype="int64")
for i in range(n):
    weight, value = map(int, input().split())
    DP[i, :weight] = DP[i - 1, :weight]
    DP[i, weight:] = np.fmax(DP[i - 1, weight:], DP[i - 1, : w - weight + 1] + value)

print(DP[-1][w])

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)] #1-index

def chmax(a,b):
    if a >= b:
        return a
    else:
        return b
# dp[i+1][w]: i番目までの品物を選びその重さがwを超えないときの最大価値
dp = [[0]*(W+10) for _ in range(N+10)]

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

print(dp[N][W])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections,itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)] #1_indexed
for i,j in itertools.product(range(1,N+1),range(W+1)):
    w,v = wv[i-1]
    if j-w>=0:
        dp[i][j] = max(dp[i][j],dp[i-1][j-w]+v)
    dp[i][j] = max(dp[i][j],dp[i-1][j])
print(dp[-1][-1])

Submission status: Accepted

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

    # min -> inf, max -> -1
    dp = [[-1]*(wmax+1) for _ in range(n+1)]

    # shoki joken
    dp[0] = [0]*(wmax+1)
    for i in range(n):
        w,v = wv[i]
        for j in range(wmax+1):
            # i select or not select
            if j-w >= 0:
                dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
            else:
                dp[i+1][j] = dp[i][j]

    print(max(dp[-1]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
n, W = map(int, input().split())
dp = np.zeros((n,W+1), dtype='int64')

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

    # print("left", dp[i, :w])
    # print("right", dp[i-1, :w])
    dp[i, :w] = dp[i-1, :w]
    dp[i, w:] = np.fmax(dp[i-1, w:], dp[i-1,:W-w+1]+v)

    # print(dp[i])
print(dp[n-1][W])

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
dp=[[0]*(w+1) for i in range(n+1)]
wet=[]
val=[]
for i in range(n):
  we,va=map(int,input().split())
  wet.append((we,va))
wet.sort()
#print(wet)
for i in range(n+1):
  for j in range(w+1):
    if(i==0 or j==0):
      continue
    dp[i][j]=dp[i-1][j]
    if(wet[i-1][0]<=j):
      #print(wet[i][1],wet[i][0])
      dp[i][j]=max(dp[i][j],dp[i-1][j-wet[i-1][0]]+wet[i-1][1])
print(dp[n][w])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    N, W = map(int, input().rstrip().split())
    item_list = []
    for _ in range(N):
        w, v = map(int, input().rstrip().split())
        item_list.append((w, v))

    # dp[i][w] = i番目まで見て重さwで持ち帰れる最大の価値
    dp = [[0] * (W + 1) for _ in range(N+1)]

    for i, item in enumerate(item_list, 1):
        for w in range(W+1):
            # もし品物iが入れられる
            if w + item[0] <= W:
                dp[i][w+item[0]] = max(dp[i][w+item[0]], dp[i-1][w]+item[1])
            # 入れないパターン
            dp[i][w] = max(dp[i][w], dp[i-1][w])
    print(dp[N][W])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    N, W = map(int, input().rstrip().split())
    item_list = []
    for _ in range(N):
        w, v = map(int, input().rstrip().split())
        item_list.append((w, v))

    # dp[i][w] = i番目まで見て重さwで持ち帰れる最大の価値
    dp = [[0] * (W + 1) for _ in range(N)]

    for i, item in enumerate(item_list):
        for w in range(W+1):
            # もし品物iが入れられる
            if w + item[0] <= W:
                dp[i][w+item[0]] = max(dp[i][w+item[0]], dp[i-1][w]+item[1])
            # 入れないパターン
            dp[i][w] = max(dp[i][w], dp[i-1][w])
    print(dp[N-1][W])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from collections import deque
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,w=mp()
dp=[0]*(w+1)
for i in range(n):
    x,y=mp()
    for k in range(w,x-1,-1):
        dp[k]=max(dp[k],dp[k-x]+y)
print(dp[-1])

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
items = [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 - items[i][0] >= 0:
            # 入れない時と入れる時
            dp[i + 1][j] = max(dp[i][j - items[i][0]] + items[i][1], dp[i][j])
        else:
            # 入れる時
            dp[i + 1][j] = dp[i][j]

print(dp[n][w])

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
w_list = [0]
v_list = [0]

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

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
w = []
v = []
for _ in range(N):
    weight,value = map(int,input().split())
    w.append(weight)
    v.append(value)
    
dp = [[0] * (W+1) for _ in range(N+1)] #dp[i+1][w]品物i番目までw以下になるように選んだ時の価値の最大値

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 = 3, 8
# ARR = [
#     [3, 30],
#     [4, 50],
#     [5, 60],
# ]
# #
N, W, = 6, 15
ARR = [
    [6, 5],
    [5, 6],
    [6, 4],
    [6, 6],
    [3, 5],
    [7, 2],
]



N,W = map(int,input().split())
ARR = []

for i in range(N):
    ARR.append(list(map(int,input().split())))


def calculate(n, w, arr):
    srr = [[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 - arr[i - 1][0] >= 0:
                s1 = srr[i - 1][j]
                s2 = srr[i - 1][j - arr[i - 1][0]] + arr[i - 1][1]
                srr[i][j] = max(s1, s2)
            else:
                srr[i][j] = srr[i-1][j]

    print(srr[-1][-1])


calculate(N, W, ARR)

Submission status: Accepted

Solution code:
# N, W = 3, 8
# ARR = [
#     [3, 30],
#     [4, 50],
#     [5, 60],
# ]
# #
# N, W, = 6, 15
# ARR = [
#     [6, 5],
#     [5, 6],
#     [6, 4],
#     [6, 6],
#     [3, 5],
#     [7, 2],
# ]



N,W = map(int,input().split())
ARR = []

for i in range(N):
    ARR.append(list(map(int,input().split())))

def calculate(n, w, arr):
    srr = [[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 - arr[i-1][0] >= 0:
                s1 = srr[i - 1][j]
                s2 = srr[i - 1][j - arr[i-1][0]] + arr[i-1][1]
                srr[i][j] = max(s1, s2)
            else:
                srr[i][j] = srr[i - 1][j]

    print(srr[-1][-1])

calculate(N, W, ARR)

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function
from collections import defaultdict, Counter, deque
from future_builtins import ascii, filter, hex, map, oct, zip
from itertools import imap as map, izip as zip, permutations, combinations, combinations_with_replacement
from __builtin__ import xrange as range
from math import ceil, factorial, log
from _continuation import continulet
from cStringIO import StringIO
from io import IOBase
import __pypy__
from bisect import bisect, insort, bisect_left, bisect_right
from fractions import Fraction
from functools import reduce
import string
import sys
import os
import re
inf = float('inf')
mod_ = int(1e9) + 7
mod = 998244353

def factors(n):
    from functools import reduce
    return set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

def sieve(m):
    n=1
    primes = {}
    arr=set([])
    for i in range(2, int(m ** 0.5) + 1):
        a = n // i
        b = m // i
        for k in range(max(2, a), b + 1):
            c = i * k
            primes[c] = 1

    for i in range(max(n, 2), m + 1):
        if i not in primes:
            arr.add(i)

    return arr


class DisjointSetUnion:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.num_sets = n
 
    def find(self, a):
        acopy = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a:
            self.parent[acopy], acopy = a, self.parent[acopy]
        return a
 
    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a != b:
            if self.size[a] < self.size[b]:
                a, b = b, a
 
            self.num_sets -= 1
            self.parent[b] = a
            self.size[a] += self.size[b]
 
    def set_size(self, a):
        return self.size[self.find(a)]
 
    def __len__(self):
        return self.num_sets


def main():
    n,W=map(int,input().split())
    wt=[]
    val=[]
    for i in range(n):
        w,v=map(int,input().split())
        wt.append(w)
        val.append(v)
    t=[[-1 for i in range(W+1)] for j in range(n+1)]
    for i in range(n+1):
        t[i][0]=0
    for i in range(W+1):
        t[0][i]=0
    for i in range(1,n+1):
        for j in range(1,W+1):
            if wt[i-1]<=j:
                t[i][j]=max(val[i-1]+t[i-1][j-wt[i-1]],t[i-1][j])
            else:
                t[i][j]=t[i-1][j]
    print(t[n][W])









        

        
    




    



# region fastio

BUFSIZE = 8192

class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

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


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    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()

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10**5)
# from collections import defaultdict
import sys
readline = sys.stdin.buffer.readline
geta = lambda fn: map(fn, readline().split())
gete = lambda fn: fn(readline())

def main():
    N, W = geta(int)
    cur = [0] * (W+1) 

    for i in range(N):
        w, v = geta(int)
        update = cur[:]
        for j in range(w,W+1):
            tmp = cur[j-w] + v
            if tmp > cur[j]: update[j] = tmp
        
        cur = update

    print(cur[W])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10**5)
# from collections import defaultdict
import sys
readline = sys.stdin.buffer.readline
geta = lambda fn: map(fn, readline().split())
gete = lambda fn: fn(readline())


N, W = geta(int)
cur = [0] * (W+1) 

for i in range(N):
    w, v = geta(int)
    update = cur[:]
    for j in range(w,W+1):
        tmp = cur[j-w] + v
        if tmp > cur[j]: update[j] = tmp
    
    cur = update

print(cur[W])

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10**5)
# from collections import defaultdict
geta = lambda fn: list(map(fn, input().split()))
gete = lambda fn: fn(input())

N, W = geta(int)
cur = [0] * (W+1) 

for i in range(N):
    w, v = geta(int)
    update = cur[:]
    for j in range(w,W+1):
        tmp = cur[j-w] + v
        if tmp > cur[j]: update[j] = tmp
    
    cur = update

print(cur[W])

Submission status: Accepted

Solution code:
import numpy as np
n, W = map(int, input().split())
dp = np.zeros((n,W+1), dtype='int64')
for i in range(n):
    w, v = map(int , input().split())
    dp[i, :w] = dp[i-1, :w]
    dp[i, w:] = np.fmax(dp[i-1, w:], dp[i-1,:W-w+1]+v)
print(dp[n-1][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] >= 0:
      dp[i+1][j] = max(dp[i+1][j], dp[i][j-wv[i][0]] + wv[i][1])
    dp[i+1][j] = max(dp[i+1][j], dp[i][j])
 
ans = 0

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

out=0
for i in range(W+1):
    out=max(out,dp[N][i])
print(out)

Submission status: Accepted

Solution code:
import numpy as np

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

dp = np.zeros((w + 1, n), dtype=np.int)
dp[wv[0, 0] :, 0] = np.full(dp[wv[0, 0] :, 0].shape, wv[0, 1])
for i in range(1, n):
    dp[:, i] = dp[:, i - 1]
    wNew, vNew = wv[i, 0], wv[i, 1]
    dp[wNew:, i] = np.fmax(dp[wNew:, i - 1], vNew + dp[:-wNew, i - 1])

print(dp[w, n - 1])

Submission status: Accepted

Solution code:
N, W = map(int, input().strip().split())
 
values = []
weights = []
 
for _ in range(N):
    w, v = map(int, input().strip().split())
    weights.append(w)
    values.append(v)
    
dp = [0]*(W+1)
for i in range(N):
    for w in range(W, weights[i] - 1, -1):
        dp[w] = max(dp[w], values[i] + dp[w - weights[i]])
print(dp[W])

Submission status: Accepted

Solution code:
import array
n,w=map(int,input().split())
weight=[]
value=[]
for _ in range(n):
    tempw,tempv=map(int,input().split())
    weight.append(tempw)
    value.append(tempv)
t=[[0 for i in range(n+1)] for j in range(w+1)]
for i in range(1,w+1):
    for j in range(1,n+1):
        if(weight[j-1]<=i):
            t[i][j]=max(value[j-1]+t[i-weight[j-1]][j-1],t[i][j-1])
        else:
            t[i][j]=t[i][j-1]
print(t[-1][-1])

Submission status: Accepted

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

Submission status: Accepted

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

N, W = map(int, input().split())
dp = np.zeros((N, W+1), dtype='int64')

def solve(N, W):
    for i in range(0, N):
        wi, vi = map(int, input().split())
        dp[i][:wi] = dp[i-1][:wi]
        dp[i][wi:] = np.fmax(dp[i-1][wi:],
                            dp[i-1][:W+1-wi] + vi)
    return dp[N-1][W]

print(solve(N, W))