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

Submission status: Accepted

Solution code:
def main():
    n,w = map(int, input().split())
    weight = []
    value = []
    for i in range(n):
        wi, vi = map(int, input().split())
        weight.append(wi)
        value.append(vi)
    
    def chmax(a, b):
        if a < b:
            a = b
        return a
    
    dp = [[0 for i in range(100100)] for j 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] = chmax(dp[i + 1][sum_w], dp[i][sum_w - weight[i]] + value[i])

            dp[i + 1][sum_w] = chmax(dp[i + 1][sum_w], dp[i][sum_w])
    
    print(dp[n][w])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np


def main():
    N, W = list(map(int, input().split(' ')))
    items = np.array([list(map(int, input().split(' '))) for _ in range(N)])
    dp = np.zeros((N, W + 1))
    dp[0, items[0, 0]:] = items[0, 1]
    for n in range(1, N):
        weight, value = items[n, 0], items[n, 1]
        dp[n, :] = dp[n - 1, :]
        dp[n, weight:] = np.fmax(
            dp[n, weight:],
            value + dp[n - 1, :(- weight)]
        )
    print(int(dp[N - 1, W]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin


def solve():
    n,mw = [int(i) for i in stdin.readline().split()]
    iw, iv = [], []
    for _ in range(n):
        w,v = [int(i) for i in stdin.readline().split()]
        iw.append(w)
        iv.append(v)
    dp = [[0 for _ in range(mw+1)] for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(mw+1):
            if iw[i-1] > j: dp[i][j] = dp[i-1][j]
            else: dp[i][j] = max(dp[i-1][j], iv[i-1] + dp[i-1][j-iw[i-1]])
    return dp[-1][-1]

print(solve())

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from pprint import pprint

n,w = map(int,input().split())

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


dp_table = [[-float("inf")]*(w+1) for _ in range(n+1)]

dp_table[0] = [0]*(w+1)

#sum_w以下の重さの時のvalueの合計の最大を求めていく。

for i in range(1,n+1):
    for sum_w in range(w+1):
        #i番目の品物を選ぶ場合
        if sum_w >= wv[i-1][0]:
            dp_table[i][sum_w] = max(dp_table[i-1][sum_w], dp_table[i-1][sum_w-wv[i-1][0]] + wv[i-1][1])
        else:
            #i番目の品物を選ばない場合
            dp_table[i][sum_w] = dp_table[i-1][sum_w]


result = dp_table[n][w]
print(result)

Submission status: Accepted

Solution code:
from pprint import pprint

n,w = map(int,input().split())

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


dp_table = [[-float("inf")]*(w+1) for _ in range(n+1)]

dp_table[0] = [0]*(w+1)

#sum_w以下の重さの時のvalueの合計の最大を求めていく。

for i in range(1,n+1):
    for sum_w in range(w+1):
        #i番目の品物を選ばない場合
        dp_table[i][sum_w] = max(dp_table[i][sum_w], dp_table[i-1][sum_w])
        #i番目の品物を選ぶ場合
        if sum_w >= wv[i-1][0]:
            dp_table[i][sum_w] = max(dp_table[i][sum_w], dp_table[i-1][sum_w-wv[i-1][0]] + wv[i-1][1])
        else:
            continue


result = dp_table[n][w]
print(result)

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][j], dp[i + 1][j])          
print(dp[n][w])

Submission status: Accepted

Solution code:
# coding:utf-8

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

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

for i in range(1, N+1):
	for j in range(W+1):
		# 品物を選ばない
		dp[i][j] = max(dp[i][j], dp[i-1][j])
		# 品物を選ぶ
		if j - w[i-1] >= 0:
			dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]] + v[i-1])

print(dp[N][W])

Submission status: Accepted

Solution code:
import numpy as np

# 入力
N, W = map(int, input().split())
wv = np.array([[int(i) for i in input().split()] for j in range(N)])

# DPテーブル
dp = np.zeros((N+1)*(W+1), dtype=int).reshape((N+1), (W+1))

# DPループ
for i in range(N):    # i番目の荷物について検討する
    dp[i+1][:wv[i-1][0]] = dp[i][:wv[i-1][0]]
    dp[i+1][wv[i-1][0]:] = np.maximum(dp[i][wv[i-1][0]:], dp[i][:(W+1)-wv[i-1][0]] + wv[i-1][1])
        
# 二次元リストの一番右下が最適解
print(dp[N][W])

Submission status: Accepted

Solution code:




def main():
    N,W = map(int, input().split())
    dp = [[0]*(W+1) for i in range(N+1)]
    weight = [0]
    value = [0]
    for i in range(N):
        w,v=map(int, input().split())
        weight.append(w)
        value.append(v)

    # dp[i][w] is the maximum value got with first i items stored in w weight of knapsack
    for i in range(1,N+1):
        for w in range(1,W+1):
            if w>=weight[i]:
                dp[i][w] = max(dp[i-1][w],dp[i-1][w-weight[i]]+value[i])
            else:
                dp[i][w] = dp[i-1][w]
    print(dp[N][W])





if __name__ == "__main__":
    main()

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

	
	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] 




q=list(map(int,input().split()))
n=q[0]
W=q[1]
v=[0]*n
w=[0]*n
for _ in range(n):
  r=list(map(int,input().split()))
  w[_]=r[0]
  v[_]=r[1]
  




print(knapSack(W,w,v,n))

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
wvs = [[0, 0] for _ in range(n)]  # 0がw 1がv
for i in range(n):
    wi, vi = map(int, input().split())
    wvs[i][0] = wi
    wvs[i][1] = vi
dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    for wi in range(1, w + 1):
        if wi - wvs[i - 1][0] >= 0:
            dp[i][wi] = max(dp[i - 1][wi],
                            dp[i - 1][wi - wvs[i - 1][0]] + wvs[i - 1][1])
        else:
            dp[i][wi] = dp[i - 1][wi]
print(dp[i][wi])

Submission status: Accepted

Solution code:
# region header
import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
from string import ascii_lowercase, ascii_uppercase, digits
sys.setrecursionlimit(10**6)
INF = float('inf')
MOD = 10 ** 9 + 7
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rf(): return float(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]
def rf_(): return [float(_) for _ in rs().split()]
def divisors(n, sortedresult=True):
    div = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.append(i)
            if i != n // i:
                div.append(n//i)
    if sortedresult:
        div.sort()
    return div
# endregion
N, W = ri_()
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = ri_()
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][j - w[i]] + v[i], dp[i][j])
        else:
            dp[i + 1][j] = dp[i][j]
print(max(dp[N]))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N, W = map(int, input().split())
    item = []
    for _ in range(N):
        w, v = map(int, input().split())
        item.append((w, v))

    dp = [0] * (W + 1)
    for w, v in item:
        for i in range(w, W + 1)[::-1]:
            tmp = dp[i - w] + v
            if tmp > dp[i]:
                dp[i] = tmp

    print(max(dp))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def chmax(dp, i, j, b):
    if dp[i][j] < b:
        dp[i][j] = b
        return True
    return False
def main():
    N, W = map(int, input().split())
    goods = []
    for _ in range(N):
        goods.append(list(map(int, input().split())))
    dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
    for i in range(N):
        w, v = goods[i][0], goods[i][1]
        for j in range(W+1):
            chmax(dp, i+1, j, dp[i][j])
            if j-w >= 0:chmax(dp, i+1, j, dp[i][j-w]+v)
    print(dp[-1][-1])
if __name__ == "__main__":
    main()

Submission status: Accepted

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

for w in range(W+1):
    dp[0][w] = 0 if w < A[0][0] else A[0][1]

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

Submission status: Accepted

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

DP = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
# DP[2][3] ... i番目までをナップサックに入れることが可能なとき（成約３）
for n in range(N):
    w_i, v_i = map(int, input().split())
    for w in range(W+1):
        tmp = 0
        if w - w_i >= 0:  # i番目のやつが入れる余地があるときここがkey
            DP[n + 1][w] = max(DP[n][w - w_i] + v_i, DP[n][w])
        else:
            DP[n + 1][w] = DP[n][w]

print(max(DP[N]))

Submission status: Accepted

Solution code:
import sys
# import numpy as np

def IL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

N, W = IL()
v_list = [0] * N
w_list = [0] * N
v = 0
w_total = 0
for i in range(N):
	w_list[i], v_list[i] = IL()
# dp = np.zeros((N+1, W+1))
dp = [[0] * (W+1) for _ in range(N+1)]
for i in range(N):
	for j in range(W+1):
		if j >= w_list[i]:
			dp[i+1][j] = max(dp[i][j-w_list[i]] + v_list[i], dp[i][j])
		else:
			dp[i+1][j] = dp[i][j]

print(dp[N][W])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
dp = [[0] * (m+1) for i in range(n+1)]

for i in range(n):
    w, v = map(int, input().split())
    for j in range(m+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][m])

Submission status: Accepted

Solution code:
import numpy as np

n, ww = map( int, input().split() )

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

dp = np.zeros( ww+1 )
dp = dp.astype( "int64" )
for ni in range( n ):
    dp[ w[ ni ]: ] = np.maximum( dp[ w[ ni ]: ], dp[ :-w[ ni ] ]+v[ ni ] )
#    print( dp )

print( dp[ -1 ] )

Submission status: Accepted

Solution code:
import sys

input = lambda :sys.stdin.readline().rstrip()

def main():
    N, W = map(int, input().split())
    w, v = [0 for _ in range(N)], [0 for _ in range(N)]
    for i in range(N):
        w[i], v[i] = map(int, input().split())
    ans = solve(N, W, w, v)
    print(ans)


def solve(N, W, w, v):
    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(W + 1):
            if 0 <=  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)
    return dp[N][W]


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, w = map(int ,input().split())
items = []
for i in range(n):
    array = list(map(int, input().split()))
    items.append(array)
# dp = np.zeros((n+1, w+1))
dp = [[0 for _ in range(w+1)] for _ in range(n+1)]

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


print(int(dp[i][j]))

Submission status: Accepted

Solution code:
from sys import stdin, stdout
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()
	weight = [0 for _ in range(n)]
	val = [0 for _ in range(n)]
	for i in range(n):
		w, v = rli()
		weight[i], val[i] = w, v
	#dp(i, j) = max val using items 1,...,i at 
	#			weight j

	dp = [[NINF for c in range(W+1)] for r in range(n+1)]
	for r in range(n+1):
		dp[r][0] = 0
	for c in range(W+1):
		dp[0][c] = 0
	for r in range(1, n+1):
		w, v = weight[r-1], val[r-1]
		for c in range(1, W+1):
			dp[r][c] = dp[r-1][c]
			if c - w >= 0:
				dp[r][c] = max(dp[r][c], dp[r-1][c], v + dp[r-1][c-w])
	print(dp[-1][-1])
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from sys import stdin, stdout
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()
	weight = [0 for _ in range(n)]
	val = [0 for _ in range(n)]
	for i in range(n):
		w, v = rli()
		weight[i], val[i] = w, v
	#dp(i, j) = max val using items 1,...,i at 
	#			weight j

	dp = [[NINF for c in range(W+1)] for r in range(n+1)]
	for r in range(n+1):
		dp[r][0] = 0
	for c in range(W+1):
		dp[0][c] = 0
	for r in range(1, n+1):
		w, v = weight[r-1], val[r-1]
		for c in range(1, W+1):
			if c - w < 0:
				dp[r][c] = max(dp[r][c], dp[r-1][c])
			else:
				dp[r][c] = max(dp[r][c], dp[r-1][c], v + dp[r-1][c-w])
	print(dp[-1][-1])
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

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

dp = [0]*(W+1)
L = []
for i in range(N):
    ta,tb = map(int,input().split())
    L.append([tb,ta])

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

Submission status: Accepted

Solution code:
import numpy as np
N, W = map(int, input().split())
dp = np.zeros(W+1, np.int64)
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,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:
def main():
    import sys
    input = sys.stdin.readline

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

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

    # i種類目までの荷物を見る
    for i in range(N):
        # その荷物を重さjになるように持つ
        for j in range(W+1):
            w, v = WV[i]
            num_w = min(1, j//w)        # 荷物は1種につき1個まで
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w*num_w] + v*num_w)
    print(max(dp[-1]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
dp = np.zeros(W+1,dtype=int) #1_indexed
for i in range(N):
    w,v = wv[i]
    dp[w:] = np.fmax(dp[:-w]+v,dp[w:])
print(dp[-1])

Submission status: Accepted

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

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

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

# 重かったので却下
# for i in range(N):
#     weight,value = map(int, input().split())
#     for sum_w in range(W+1):
#         if sum_w - weight >=  0:
#             dp[i+1][sum_w] = max(dp[i][sum_w], dp[i][sum_w - weight] + value)
#         dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

for i in range(N):
    weight, value = map(int, input().split())
    dp[i+1] = dp[i]
    dp[i+1, weight:] = np.maximum(dp[i+1, weight:], dp[i, :W-weight+1] + value)

print(dp[N][W])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np

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

items = [tuple(map(int, input().split())) for _ in range(N)]
dp = np.zeros(W+1, dtype=np.int64)

for i, (w, v) in enumerate(items):
  tmp = np.zeros(W+1, dtype=np.int64)
  tmp[w:] = dp[:-w] + v
  dp = np.maximum(dp, tmp)
print(dp[W])

Submission status: Accepted

Solution code:
import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():

    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())
    # https://qiita.com/drken/items/dc53c683d6de8aeacf5a#dp-%E5%AE%9F%E8%A3%85%E3%81%AE%E9%A0%86%E5%BA%8F

    INF = 10**10  # INF+INFを計算してもオーバーフローしない範囲で大きく
    # dpテーブル dp[i][j]:= i番目までの荷物の中から重さj以下で選ぶ通り数
    dp = [[0]*(W+1) for _ in range(N+1)]
    """
    初期化の値は，
        最小化問題：INF, 
        最大化問題：-INF（0以上の値しか取らないなら-1, あるいは0でもいいかも)
        数え上げ問題：0
        確率問題：0
        Yes/No判定問題:False
    """

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

    # ループ
    for typ in range(1, N+1):
        for weight in range(W+1):

            """
            dp[from] の値の更新が完了していればノード from からノード to への緩和を行っていい．貰うdpであれ配るdpであれ．
            両者の違いを意識すべきケースはcf. 
            https://qiita.com/drken/items/ace3142967c4f01d42e9#%E8%B2%B0%E3%81%86-dp-%E3%81%A8%E9%85%8D%E3%82%8B-dp-%E3%81%AE%E6%AF%94%E8%BC%83

            # 遷移式がたくさんある場合この中でさらにforループを回したりする cf. https://atcoder.jp/contests/dp/tasks/dp_b
            """
            # i番目選ぶ
            if weight-w[typ-1] >= 0:
                dp[typ][weight] = max(max(dp[typ][weight], dp[typ-1][weight-w[typ-1]]+v[typ-1]),dp[typ-1][weight])
            # 選ばない
            else:
                dp[typ][weight] = max(dp[typ][weight], dp[typ-1][weight])

    # 出力
    print(dp[N][W])


resolve()

Submission status: Accepted

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

dp = [[0] * (W + 5) 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 0 <= j - wt[i]:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - wt[i]] + vt[i])
# print(dp)
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 = []
for _ in range(N+1):
    dp.append([0] * (W+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[N][W])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import copy
n,W=map(int,input().split())
l=[0]*(W+1)
for _ in range(n):
	w,v=map(int,input().split())
	d=copy.deepcopy(l)
	for i in range(len(d)):
		if i-w>=0:
			d[i]=max(d[i],l[i-w]+v)
	l=d
	#print(l)

print(l[-1])

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
g = []
for i in range(n):
    g.append(list(map(int, input().split())))
m = [[0 for j in range(w+1)]for i in range(n+1)]
for i in range(n):
    for j in range(w+1):
        if j-g[i][0] < 0:
            m[i+1][j] = m[i][j]
        else:
            m[i+1][j] = max(m[i][j], m[i][j-g[i][0]]+g[i][1])
print(m[n][w])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
 
 
def input():
    return sys.stdin.readline().strip()
 
 
sys.setrecursionlimit(20000000)
 
 
def main():
    N, W = map(int, input().split())
    B = [list(map(int, input().split())) for _ in range(N)]
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(N):
        w = B[i][0]
        v = B[i][1]
        for j in range(W + 1):
            if j >= w:
                dp[i + 1][j] = max(dp[i][j - w] + v, dp[i][j])
            else:
                dp[i + 1][j] = dp[i][j]
    print(dp[-1][-1])
 
 
if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
n,W = [int(e) for e in input().split()]
v = np.zeros(n,dtype='int64')
w = np.zeros(n,dtype='int64')

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

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

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

print(dp[-1])

Submission status: Accepted

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

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

for h in range(W):
    if h+1>=w[0]:
        dp[0][h]=v[0]

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

Submission status: Accepted

Solution code:
inf = 2**60
'''
def table(size, init): #配列生成
  x = len(size)
  l = [init for i in range(size[x-1])]
  for i in range(x-1):
    l = [l for k in range(size[x-2-i])]
  return l
'''

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

print(max(dp[n]))

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 _ in range(n)]


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



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

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007

#+++++

def main():
	#a = int(input())
	n, w = IN()
	#s = input()
	dp = [-1]*(w+1)
	dp[0]=0
	for _ in range(n):
		wi, vi = IN()
		for ri, v in enumerate(dp[::-1]):
			i=len(dp)-ri-1
			#print(i)
			if i + wi > w:
				continue
			if dp[i] >= 0:
				dp[i + wi] = max(dp[i+wi], dp[i]+vi)
		#print(dp)
	ret = max(dp)
	return ret
				
			
		
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N, W = [int(x) for x in input().split()]
    wv = [[int(x) for x in input().split()] for _ in range(N)]

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

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

    print(dp[N][W])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    a, b = map(int, input().split())
    w += [a]
    v += [b]
 
DP = np.zeros(W+1, dtype=int)
# i 円以下で買える商品の最大価値
for i in range(N):
    DP[w[i]:] = np.maximum(DP[:-w[i]]+ v[i], DP[w[i]:])
print(DP[-1])

Submission status: Accepted

Solution code:
# DP
def main():
    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))
 
 
main()

Submission status: Accepted

Solution code:
# dp[w] i番目までの品物で、重さがw以下になるよう選んだときの価値の最大値。
# 参考 https://qiita.com/drken/items/68b8503ad4ffb469624c

import numpy as np

# 入力
# 重さと価値はループのなかで都度取得する
N, W = map(int, input().strip().split())

# 初期化
dp = np.zeros(W + 1, dtype='int64')

# dpテーブル
for i in range(N):
    w, v = map(int, input().strip().split())
    dp[w:] = np.maximum(dp[w:], dp[:-w] + v)

print(dp[-1])

Submission status: Accepted

Solution code:
def dynamicprogramming():
  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):
        dpi = dp[i]
        if dpi != -1:
          if dp[i + w] < dpi + v:
            dp[i + w] = dpi + v
  print(max(dp))

dynamicprogramming()

Submission status: Accepted

Solution code:
import numpy as np
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

DP = np.zeros((N+1,W+1), dtype=np.int64)

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

#print(DP)
print(DP[-1][-1])

Submission status: Accepted

Solution code:
import numpy as np

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


dp = np.zeros((n + 1, w + 1), dtype=np.int64)

for i in range(n):
    tmp = np.zeros(w + 1, dtype=int)
    tmp[l[i][0]:] = dp[i][:-l[i][0]] + l[i][1]
    dp[i + 1] = np.maximum(dp[i], tmp)
    
print(dp[n][w])

Submission status: Accepted

Solution code:
import sys


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


sys.setrecursionlimit(20000000)


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


if __name__ == "__main__":
    main()