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 fileinput


def knapsack(capacity, item_weights, item_values):
    no_current_item_values = [0] * (capacity + 1)
    for i, val in enumerate(item_values):
        with_current_item_values = [0] * (capacity + 1)
        for current_capacity in range(1, capacity + 1):
            if current_capacity < item_weights[i]:
                with_current_item_values[current_capacity] = no_current_item_values[current_capacity]
            else:
                with_current_item_values[current_capacity] = max(
                    no_current_item_values[current_capacity],
                    no_current_item_values[current_capacity - item_weights[i]] + val
                )
        no_current_item_values = with_current_item_values

    return no_current_item_values[-1]


inp = fileinput.input()

first_line_split = inp.readline().split(" ")

item_count = int(first_line_split[0])
capacity = int(first_line_split[1])

item_weights = []
item_values = []
for _ in range(item_count):
    split = inp.readline().split(" ")
    item_weights.append(int(split[0]))
    item_values.append(int(split[1]))

print(knapsack(capacity, item_weights, item_values))

Submission status: Accepted

Solution code:
n,W = map(int, input().split())
l = [dict() for i in range(n+1)]
l[0][0] = 0
for i in range(1,n+1):
  w,v = map(int, input().split())
  l[i] = l[i-1].copy()
  l[i][w] = max(l[i].get(w,0),v)
  for x in l[i-1]:
    if x+w <= W:
      l[i][x+w] = max(l[i].get(x+w,0),l[i-1][x] + v)
print(max(l[n].values()))

Submission status: Accepted

Solution code:
def dpcalc():
    global n, w
    dp = [0] * (w + 1)      # 初期値は０　範囲は0〜wまで

    for i in range(n):      # 品物0からn-1までを評価
        wt, vl = map(int, input().split())
        for j in range(w, wt - 1, -1):
            tmp = dp[j - wt] + vl
            if tmp > dp[j]:
                dp[j] = tmp
    return dp[w]


if __name__ == "__main__":
    
    n, w = map(int, input().split())
    print(dpcalc())

Submission status: Accepted

Solution code:
def calc(num,capacity):
    dp = [0]*(capacity+1)
    for _ in range(num):
        weight, value = map(int, input().split())
        for w in range(capacity,weight - 1,-1):
            tmp = dp[w - weight] + value
            if dp[w] < tmp:
              dp[w] = tmp
    return dp[capacity]
 
num, capacity = map(int, input().split())
print(calc(num,capacity))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n,W = [int(i) for i in input().split()]
wv = [[int(i) for i in input().split()] for j in range(n)] # 縦「n」行

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

print(max(dp))    
    
#print(dp)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n,W = [int(i) for i in input().split()]
wv = [[int(i) for i in input().split()] for j in range(n)] # 縦「n」行

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

print(max(dp))    
    
#print(dp)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
wlis=[]
vlis=[]
for i in range(n):
    a,b=map(int,input().split())
    wlis.append(a)
    vlis.append(b)

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

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

print(dp[n][w])

Submission status: Accepted

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

#dp[i][j]=i番目の品物までだけを選び重量制限をjとしたときの価値の最大値
dp = []
dp.append([0]*min(W[0],Wmax+1)+ [V[0]]*max(0, Wmax+1-W[0]))


for i in range(1,N):
	#今回の重量制限をwとする
	#今回は荷物を積む場合: dp[i][w] = dp[i-1][w-w[i]]+v[i] 
	#今回は荷物を積まない場合: dp[i][w] = dp[i-1][w]
	#よってこの2つのうち大きいほうをdp[i][w]に採用する
	dpi = []
	for j in range(Wmax+1):
		if j<W[i]:
			dpi.append(dp[i-1][j])
		else:
			dpi.append(max(dp[i-1][j], dp[i-1][j-W[i]]+V[i]))
	dp.append(dpi)
print(dp[N-1][Wmax])

Submission status: Accepted

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

	dp = [0] * (W + 1)
	for w, v in WV:
		for sumw in range(W, w - 1, -1):
			t = dp[sumw - w] + v
			if dp[sumw] < t:
				dp[sumw] = t
		#for x in dp:
		#	print("{:4d}".format(x), end="")
		#print()
	return max(dp)

print(main())

Submission status: Accepted

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

	dp = [0] * (W + 1)
	#for n in range(N):
	#	w, v = WV[n]
	for w, v in WV:
		for sumw in range(W, w - 1, -1):
			#dp[sumw] = max([dp[sumw], dp[sumw - w] + v])
			t = dp[sumw - w] + v
			if dp[sumw] < t:
				dp[sumw] = t
		#for x in dp:
		#	print("{:4d}".format(x), end="")
		#print()
	return max(dp)

print(main())

Submission status: Accepted

Solution code:
def dp():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))

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

Submission status: Accepted

Solution code:
def d():
    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])
    return dp[-1][-1]


if __name__ == '__main__':
    ans = d()
    print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:


def main():

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

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


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

#    print(tab)

    wvn.sort(key = lambda x : x[1], reverse = True )
    wvn.sort(key = lambda x : x[0] )


    #i番目の荷物を追加で使ってみる
    for i in range(1, N + 1 ):

        #重さがwiのときのcase
        for wi in range(1, W+1 ):

            wv = wvn[i-1]


            a = tab[i-1][wi]
            b = tab[i][wi-1]
            
            c = 0
            if wi>=wv[0] :
                t = tab[i-1][wi-wv[0]] + wv[1]
                c = max(c,t)
            
#            print(( (i,wi), a,b,c))

            tab[i][wi] = sorted([a,b,c])[-1]


    print(tab[-1][-1])

#    for row in tab:
#        print(row)



main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def mi(): return map(int, input().split())


def li(): return list(mi())


def li_(): return [int(x) - 1 for x in input().split()]


def lin(n: int): return [input() for _ in range(n)]


def llin(n: int): return [li() for _ in range(n)]


def llin_(n: int): return [li_() for _ in range(n)]


def lli(): return [list(map(int, l.split())) for l in input()]


def i(): return int(input())


def f(): return float(input())


def s(): return input().replace('\n', '')


def main():
    N, W = mi()
    WV = llin(N)
    dp = [[0] * (W + 1) for _ in range(N)]
    dp[0] = [WV[0][1] if WV[0][0] <= i else 0 for i in range(W+1)]
    for i in range(1, N):
        for j in range(W + 1):
            if j >= WV[i][0]:
                dp[i][j] = dp[i - 1][j - WV[i][0]] + WV[i][1]
            dp[i][j] = max(0, dp[i][j], dp[i - 1][j])
    print(dp[N-1][W])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
n,w=list(map(int, sys.stdin.readline().split()))
arr=[list(map(int, sys.stdin.readline().split())) for i in range(n)]

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

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


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

Submission status: Accepted

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

print(max(dp[N]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, os
range = xrange

def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]
 
    wi, vi = inp[2], inp[3]
 
 
    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi
 
    for i in range(n - 1):
        wi = inp[2*i + 4]
        vi = inp[2*i + 5]
        for j in range(m, wi-1, -1):
            x = vi + dp[j - wi]
            if dp[j] < x:
                dp[j] = x
 
    print(dp[-1])
main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, os
range = xrange

def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]
 
    wi, vi = inp[2], inp[3]
 
 
    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi
 
    for i in range(n - 1):
        wi = inp[2*i + 4]
        vi = inp[2*i + 5]
        for j in range(m, wi-1, -1):
            x = vi + dp[j - wi]
            if dp[j] < x:
                dp[j] = x
 
    print(dp[-1])
main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, os
 
def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]
 
    wi, vi = inp[2], inp[3]
 
 
    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi
 
    for i in range(n - 1):
        wi = inp[2*i + 4]
        vi = inp[2*i + 5]
        for j in range(m, wi-1, -1):
            x = vi + dp[j - wi]
            if dp[j] < x:
                dp[j] = x
 
    print(dp[-1])
main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, os

def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]

    wi, vi = inp[2], inp[3]


    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi

    for i in range(n - 1):
        wi = inp[2*i + 4]
        vi = inp[2*i + 5]
        for j in range(m, wi-1, -1):
            if dp[j] < vi + dp[j - wi]:
                dp[j] = vi + dp[j - wi]

    print(dp[-1])
main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, os
range = xrange

def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]
 
    wi, vi = inp[2], inp[3]
 
 
    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi
 
    for i in range(n - 1):
        wi = inp[2*i + 4]
        vi = inp[2*i + 5]
        for j in range(m, wi-1, -1):
            if dp[j] < vi + dp[j - wi]:
                dp[j] = vi + dp[j - wi]
 
    print(dp[-1])
main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, os
range = xrange

def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]

    wi, vi = inp[2], inp[3]


    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi

    for i in range(n - 1):
        wi = inp[2*i + 4]
        vi = inp[2*i + 5]
        for j in reversed(range(wi, m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

    print(dp[-1])
main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, os
range = xrange

def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]

    w, v = inp[2::2], inp[3::2]

    dp = [0] * (m + 1)
    for j in range(w[0], m + 1):
        dp[j] = v[0]

    for i in range(n - 1):
        vi = v[i + 1]
        wi = w[i + 1]
        for j in reversed(range(wi, m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

    print(dp[-1])
main()

Submission status: Accepted

Solution code:
import sys
n,w=list(map(int, sys.stdin.readline().split()))
arr=[list(map(int, sys.stdin.readline().split())) for i in range(n)]

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

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


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

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
"""
問題
https://atcoder.jp/contests/dp/tasks/dp_d

解説
https://qiita.com/drken/items/dc53c683d6de8aeacf5a#d-%E5%95%8F%E9%A1%8C---knapsack-1
"""

def solve():
    """
    Python: TLE (´･_･`)
    """
    N, LIMIT = list(map(int, input().split()))
    W, V = [None], [None]
    for i in range(N):
        w, v = list(map(int, input().split()))
        W.append(w)
        V.append(v)
    
    # dp[i][w] := i個目までの品物を選んだ時の、重さがwのときの価値の最大値
    dp = [[w for w in range(LIMIT+1)] for i in range(N+1)]
    for w in range(LIMIT+1):
        dp[0][w] = 0
    
    #O(N*LIMIT) = O(10**7)
    for i in range(1, N+1):
        for w in range(LIMIT+1):
            if w-W[i] >= 0:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-W[i]] + V[i])
            else:
                dp[i][w] = dp[i-1][w]

    ans = 0
    for w in range(LIMIT+1):
        ans = max(ans, dp[N][w])

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import numpy as np
N,W = map(int, input().split())
# np.maximum https://www.sejuku.net/blog/69175
# 第一引数と第二引数の大小関係を要素ごとに比較して、大きい方を格納した配列を返す
dp = np.zeros(W+1, dtype=np.int64)
# その重さでの最大valueが保存されている
for i in range(N):
    w,v = map(int,input().split())
    # updating dp[w:]
    # total value of dp[k] when i-1 VS total value of dp[k-w]+v when i 

    np.maximum(dp[:W-w+1]+v,dp[w:],out=dp[w:])
print(dp[-1])

Submission status: Accepted

Solution code:
import numpy as np
N,W = map(int, input().split())
# np.maximum https://www.sejuku.net/blog/69175
# 第一引数と第二引数の大小関係を要素ごとに比較して、大きい方を格納した配列を返す
dp = np.zeros(W+1, dtype=np.int64)
# その重さでの最大valueが保存されている
for _ in range(N):
    w,v = map(int,input().split())
    # w以下ならvを足したもの、w以上ならそのままの値で、最大値を求める
    # 出力はw以上の配列として返す(それ以下は重さwなので関与しない)
    # 足す場合が前者、足さない場合が後者
    np.maximum(dp[:W-w+1]+v,dp[w:],out=dp[w:]) 

print(dp[-1])

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:],dp[:-w]+v)
print(int(max(dp)))

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

print(dp[N,:].max())

Submission status: Accepted

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

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

Submission status: Accepted

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

def f(n,W):
    wv = [list(map(int, input().split())) for _ in range(n)]
    dp = [-1] * (W + 1)
    dp[0] = 0
    for w, v in wv:
        for i in range(W - w, -1, -1):
            if dp[i] == -1: continue
            nv = dp[i] + v
            if nv > dp[i + w]:
                dp[i + w] = nv
    print(max(dp))

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

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

import numpy as np
ndp = np.zeros(W+1,dtype= np.int64)
for w,v in zip(w,v):
    np.maximum(ndp[:-w] + v, ndp[w:], out = ndp[w:])
print(ndp[-1])

Submission status: Accepted

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

for i in range(n):
    w, v = map(int, input().split())
    dp[i + 1] = dp[i]
    if w <= W:
        dp[i + 1][w:] = np.maximum(dp[i][:W - w + 1] + v, dp[i][w:])
print(int(dp[n][W]))

Submission status: Accepted

Solution code:
import numpy as np

def main():
    num, weigh = map(int, input().split())
    dp = np.zeros((num + 1, weigh + 1), dtype=int)

    for i in range(1, num + 1):
        now_weigh, now_value = map(int, input().split())
        dp[i, :now_weigh] = dp[i - 1, :now_weigh]
        dp[i, now_weigh:] = np.maximum(dp[i - 1, :weigh - now_weigh + 1] + now_value, dp[i - 1, now_weigh:])

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    num, weigh = map(int, input().split())
    dp = [defaultdict(int) for i in range(num + 1)]
    dp[0][0] = 0

    for i in range(1, num + 1):
        data = list(map(int, input().split()))
        for pre_value in dp[i - 1].keys():
            dp[i][pre_value] = max(dp[i - 1][pre_value], dp[i][pre_value])
            if pre_value + data[0] <= weigh:
                dp[i][pre_value + data[0]] = max(dp[i - 1][pre_value] + data[1], dp[i][pre_value + data[0]])

    print(max(list(dp[-1].values())))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import numpy as np

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

dp = np.zeros(W+1)
for i in range(N):
    w, v = map(int, input().rstrip().split(' '))
    dp[w:] = np.max(np.vstack([dp[w:], dp[:-w] + v]), axis=0)
    
    
print(int(max(dp)))

Submission status: Accepted

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

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

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

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

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:], dp[:-w]+v)
print(int(max(dp)))

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque

INF = 10 ** 10

N, W = [int(x) for x in stdin.readline().rstrip().split()]
wv = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N)]

# 重さiでの価値の最大
# 品物の重複選択を許さない
dp = [[0] * (W+10) for _ in range(N+10)]

for i in range(N):
    weight, value = wv[i]
    dp[i+1] = dp[i][:]
    for j in range(weight, W+1):
        dp[i+1][j] = max(dp[i][j], dp[i][j-weight]+value)

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)]
#品物は0～N-1と考えるので注意！

DP = [0]*(W+1) #0~W
#各iにつき、残り重さがWの時の最大価値をDPに入れる


#i=N-1までいった時のmax(DP)が答え
for i in range(0, N, 1): #0~N-1
  w, v = wv[i]
  #残りwei(W-DPの2個目の添字)がw未満の場合入れられない
  #入れない場合は変えなければいい
  for nw in range(W, w-1, -1):
    iretaV = DP[nw-w] + v
    if iretaV > DP[nw]:
      DP[nw] = iretaV

print(max(DP))

Submission status: Accepted

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

n,w=map(int,input().split())
dp=[0]*(w+1)
c,p=map(int,input().split())
dp[c]=p

def ans(n,w):
  for _ in range(1,n):
    c,p=map(int,input().split())
    for j in range(w,c,-1):
      if dp[j-c] != 0 and dp[j]<dp[j-c]+p:
        dp[j]=dp[j-c]+p
    if dp[c] < p:
      dp[c]=p
  return max(dp)
print(ans(n,w))

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(int(dp[-1]))

Submission status: Accepted

Solution code:
#問題 D
import numpy as np
N, W = map(int,input().split())
#普通に書くとTLEだったのでNumpy化
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(int(dp[-1]))


#dpをN*(W+1)配列とかにしてもnumpyなら間に合う。コピーに時間がかかるのかな？

# numpy化してもやっぱりTLEなので、どうもコピーが悪かったらしい
# N, W = map(int,input().split())
# VAL = np.zeros(W+1)
# val = np.zeros(W+1)
# for n in range(N):
#     w,v = map(int,input().split())
#     for weight in range(w,W+1):
#         val[weight] = max(VAL[weight],VAL[weight-w]+v)
#     VAL = np.copy(val)
# print(int(VAL[W]))

# VAL = [0]*(W+1)
# val = [0]*(W+1)
# for n in range(N):
#     w,v = map(int,input().split())
#     for weight in range(w,W+1):
#         val[weight] = max(VAL[weight],VAL[weight-w]+v)
#     VAL = val[:]
#print(VAL[W])
    # listをコピーするときは注意　https://qiita.com/utgwkk/items/5ad2527f19150ae33322
    # listへのアクセスは重いらしい。 https://qiita.com/pegasusBS15/items/620985fdc21c75ad8026

Submission status: Accepted

Solution code:
import numpy as np
N, W = map(int,input().split())
#普通に書くとTLEだったのでNumpy化
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(int(dp[-1]))

Submission status: Accepted

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


from collections import defaultdict
dp = defaultdict(int)
dp[0]=0

for wv in wvList:
    w,v = wv
    tp = defaultdict(int,{ i[0]+w : i[1]+v  for i in dp.items() if i[0]+w<=W})
    for i in set(list(dp.keys())+list(tp.keys())):
        dp[i] = max(dp[i],tp[i])

print(max(dp.values()))

Submission status: Accepted

Solution code:
"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_d

D - Knapsack 1
"""

def solve(wv_pairs):
    dp = [0] * (W + 1)
    for i in range(N):
        w_i, v_i = wv_pairs[i]
        for ww in range(W, w_i - 1, -1):
            dp[ww] = max(dp[ww], dp[ww - w_i] + v_i)
    return max(dp)


N, W = map(int, input().split())
pairs = [[int(s) for s in input().split()] for _ in range(N)]
res = solve(pairs)
print(res)

Submission status: Accepted

Solution code:
import numpy as np

N, W = map(int, input().split())
INF = -10 ** 12

# 重さW以下の時の価値の最大値
dp = np.zeros((N, W + 1), dtype=np.int64)

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

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

Submission status: Accepted

Solution code:
def calc(num,capacity):
    dp = [0]*(capacity+1)
    for _ in range(num):
        weight, value = map(int, input().split())
        for w in range(capacity,weight - 1,-1):
            tmp = dp[w - weight] + value
            if dp[w] < tmp:
              dp[w] = tmp
    return dp[capacity]

num, capacity = map(int, input().split())
print(calc(num,capacity))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N):
    w,v = map(int,input().split())
    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:
import numpy as np
import sys
input = sys.stdin.readline
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:
from sys import stdin
import numpy as np


def dp_solve(dp, lim, n):
    for i in range(n):
        w, v = map(int, input().split())
        dp[i+1][:w] = dp[i][:w]
        dp[i+1][w:] = np.maximum(dp[i][w:], dp[i][:-w]+v)
    return np.max(dp[n])


if __name__ == "__main__":
    n, lim = map(int, stdin.readline().split())
    items = []

    dp = np.zeros((n+1, lim+1), dtype='uint64')
    print(dp_solve(dp, lim, n))

Submission status: Accepted

Solution code:

import numpy as np
N,W = map(int, input().split())
# np.maximum https://www.sejuku.net/blog/69175
# 第一引数と第二引数の大小関係を要素ごとに比較して、大きい方を格納した配列を返します。
dp = np.zeros(W+1, dtype=np.int64)
for _ in range(N):
    w,v = map(int,input().split())
    # w以下ならvを足したもの、w以上ならそのままの値で、最大値を求める
    # 出力はw以上の配列として返す(それ以下は重さwなので関与しない)
    # 足す場合が前者、足さない場合が後者。その重さでの最大valueが保存されている
    np.maximum(dp[:W-w+1]+v,dp[w:],out=dp[w:]) 

print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

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

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


#dp[w] = max cost
costs = [-1 for _ in range(W + 1)]
costs[0] = 0

for w, v in WV:
    for index in reversed(range(W + 1)):
        if costs[index] == -1:
            continue
        if index + w > W:
            continue
        costs[index + w] = max(costs[index] + v, costs[index + w])


print(max(costs))

Submission status: Accepted

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

weight = []
value = []

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


dp = []

for i in range(N+1):
    dp.append([])
    for j in range(W+1):
        dp[i].append(0)


# max value = dp[何個まで見たか][現在の重さ]
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][j+weight[i]], dp[i][j] + value[i])

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

print(dp[N][W])

Submission status: Accepted

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

weight = []
value = []

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

def dfs(index, v, w):
    x = 0
    if (index >= N):
        return v
    if (w + weight[index] <= W):
        x = dfs(index+1, v+value[index], w+weight[index])
    y = dfs(index+1,v,w)

    return max(x, y)


# ans = dfs(0, 0, 0)

dp = []

for i in range(N+1):
    dp.append([])
    for j in range(W+1):
        dp[i].append(0)
    
# max value = dp[何個まで見たか][現在の重さ]
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][j+weight[i]], dp[i][j]+value[i])
        # else:
        #     dp[i+1][j] = dp[i][j]
        # if 
        if j >= weight[i]:
            dp[i+1][j] = max(dp[i][j-weight[i]]+value[i], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]


print(dp[N][W])

Submission status: Accepted

Solution code:
def nap(n,cap):
    val = [0]*(cap+1)
    for _ in range(n):
        w,v = map(int,input().split())
        for k in range(cap,w-1,-1):
            nv=val[k-w]+v
            if val[k]<nv:
                val[k]=nv
    return max(val)

n,cap=map(int,input().split())
print(nap(n,cap))