Problem:


Score : 100 points

Problem Statement

There are N items, numbered 1, 2, \ldots, N.
For each i (1 \leq i \leq N), Item i has a weight of w_i and a value of v_i.

Taro has decided to choose some of the N items and carry them home in a knapsack.
The capacity of the knapsack is W, which means that the sum of the weights of items taken must be at most W.

Find the maximum possible sum of the values of items that Taro takes home.

Constraints

All values in input are integers.

1 \leq N \leq 100

1 \leq W \leq 10^5

1 \leq w_i \leq W

1 \leq v_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

Print the maximum possible sum of the values of items that Taro takes home.

Sample Input 1

3 8
3 30
4 50
5 60

Sample Output 1

90

Items 1 and 3 should be taken.
Then, the sum of the weights is 3 + 5 = 8, and the sum of the values is 30 + 60 = 90.

Sample Input 2

5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

Sample Output 2

5000000000

The answer may not fit into a 32-bit integer type.

Sample Input 3

6 15
6 5
5 6
6 4
6 6
3 5
7 2

Sample Output 3

17

Items 2, 4 and 5 should be taken.
Then, the sum of the weights is 5 + 6 + 3 = 14, and the sum of the values is 6 + 6 + 5 = 17.



Sample input:
3 8
3 30
4 50
5 60


Sample output:
90

Submission status: Accepted

Solution code:
import sys
import numpy as np
import itertools
import heapq
import bisect
import math
import queue
from operator import itemgetter #sortedの対象を決めたい
from fractions import gcd #最大公約数
from copy import deepcopy #参照で影響されないコピー
from collections import Counter, deque, defaultdict #要素ごとの出現回数、双方向アクセス可能データ型
from functools import reduce
mod = 1000000007
inf = 10**10
sys.setrecursionlimit(1000000)

input = sys.stdin.readline

def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res
 
def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)
# template


def main():
    n, w = map(int, input().split())

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
import itertools
import heapq
import bisect
import math
import queue
from operator import itemgetter #sortedの対象を決めたい
from fractions import gcd #最大公約数
from copy import deepcopy #参照で影響されないコピー
from collections import Counter, deque, defaultdict #要素ごとの出現回数、双方向アクセス可能データ型
from functools import reduce
mod = 1000000007
inf = 10**10
sys.setrecursionlimit(1000000)

input = sys.stdin.readline

def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res
 
def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)
# template


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

    dp = np.zeros([n+1, w+1])
    
    for i, itm in enumerate(wv):
        dp[i+1, :itm[0]] = dp[i, :itm[0]]
        dp[i+1, itm[0]:] = np.max([dp[i, itm[0]:], dp[i, :w-itm[0]+1] + itm[1]], axis=0)

    print(int(dp[n, w]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np

input = sys.stdin.readline

# N 品物の数、 W 合計の重さ
n, w = map(int, input().split())

# (W V) W : 品物の重さ V：品物の価値
lst = [list(map(int, input().split())) for ii in range(n)]

# 価値 v を最大にするので、0に初期化
# １次元は品物（インデックス0には ALL0）、２次元は重さの合計
dp = np.zeros([n+1, w+1])

for i, ln in enumerate(lst):
    # 自分の重さが入るまでは１つ前の
    dp[i+1, :ln[0]] = dp[i, :ln[0]]
    # 自分を加えられる。選ばない時と価値の高いほうをセット
    dp[i+1, ln[0]:] = np.max([dp[i, ln[0]:], dp[i, :w-ln[0]+1]+ln[1]], axis=0)

print(int(dp[n, w]))

Submission status: Accepted

Solution code:
import numpy as np

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

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

for i, (wi, vi) in enumerate(wv):
    dp[i+1] = dp[i]
    np.maximum(dp[i][wi:], dp[i][:-wi] + vi, out=dp[i+1][wi:])
"""
for i in range(n):
    for sum_w in range(w+1):
        wi = wv[i][0]
        vi = wv[i][1]
        if sum_w - wi >= 0:
            dp[i+1][sum_w] = dp[i][sum_w - wi] + vi
        dp[i+1][sum_w] = max(dp[i][sum_w], dp[i+1][sum_w])
"""
#print(dp)
print(dp[n][w])

Submission status: Accepted

Solution code:
import numpy as np

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

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

for _w, _v in zip(w, v):
	np.maximum(dp[_w:], dp[:-_w] + _v, out=dp[_w:])
print(dp[-1])

Submission status: Accepted

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

dp=[[0]*(w+1) for i in range(n+1)]
for i in range(n):
    for j in range(w+1):
        if j >= item[i][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:
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(N):
    for sum_w in range(W+1):
        #i+1番目の品物を選んだ場合
        if (sum_w-w[i])>=0:
            m=0

            m=dp[i][sum_w - w[i]]+v[i]

            dp[i+1][sum_w]=max(dp[i+1][sum_w],m)
        #i+1番目の品物を選ばなかった場合
        dp[i+1][sum_w]=max(dp[i][sum_w],dp[i+1][sum_w])

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

Submission status: Accepted

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

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

    # print(N, W, WV)

    return N, W, WV


def solve(N, W, WV):
    x, y = N + 1, W + 1
    DP = [[0 for _ in range(y)] for _ in range(x)]

    for i in range(N):
        weight = WV[i][0]
        for w in range(W + 1):
            # 選ぶ
            if w + weight <= W:
                tw = w + weight
                DP[i + 1][tw] = max(DP[i + 1][tw], DP[i][w] + WV[i][1])

            # 選ばない
            DP[i + 1][w] = max(DP[i + 1][w], DP[i][w] + 0)

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


if __name__ == '__main__':
    res = solve(*args())
    print(res)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
f = [[0 for m in range(M + 1)] for n in range(N + 1)]
for n in range(N):
    for m in range(M + 1):
        if m < W[n]:
            f[n + 1][m] = f[n][m]
        else:
            f[n + 1][m] = max(f[n][m], f[n][m - W[n]] + V[n])
print(f[N][M])

Submission status: Accepted

Solution code:
n, w = list(map(int,input().split()))
w_v = [list(map(int,input().split())) for i in range(n)]
dp = [[0] * 100001 for i in range(101)]

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

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

print(dp[n][w])

Submission status: Accepted

Solution code:
# 参考：https://atcoder.jp/contests/dp/submissions/5316523

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)

# print(ndp)

for w, v in zip(w, v):
    #    print(w,v,ndp[:-w] + v)
    #    print(w,v,ndp[w:])
    np.maximum(ndp[:-w] + v, ndp[w:], out=ndp[w:])
#    print(w,v,ndp)

print(ndp[-1])

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
w = {}
v = {}

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

dp = {}
dp[0] = {}

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
#knapsack1
n,w=map(int,input().split())
data=[]
for i in range(n):
    u,v=map(int,input().split())
    data.append((u,v))
can_pack=[[0 for i in range(w+1)] for j in range(n+1)]
#can_pack[i][k]=i番目までの荷物を使って重さをkにしようとしたときに、もしそれが可能ならばその時の価値の最大値、不可能なら0

for   i in range(n):
    a,b=data[i][0],data[i][1]
    #aが重さ、bが価値　。
    for j in range(1,w+1):
        if    j>=a:
            can_pack[i+1][j]=max(can_pack[i][j-a]+b,can_pack[i][j])
        else:
            can_pack[i+1][j]=can_pack[i][j]
ans=0
for i in range(w+1):
    ans=max(ans,can_pack[n][i])
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
N, W = [int(x) for x in stdin.readline().rstrip().split()]
wv = []
for i in range(N):
    wv.append([int(x) for x in stdin.readline().rstrip().split()])
wv.append([0,0])

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

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

Submission status: Accepted

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

    dp = [[0] * (W + 5) for _ in range(N + 5)]
    
    for i in range(N):
        for j in range(W):
            print
            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]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

N,W = imn()
wv = [iln() for _ in range(N)]

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

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

Submission status: Accepted

Solution code:
n ,c = map(int,input().split())
wt =[]; val=[]

for _ in range(n):
  wi , vi = map(int,input().split())
  wt.append(wi)
  val.append(vi)
  
# dp [n][c+1] = 0 
dp = [[0 for i in range(c+1)]for j in range(n)]

for w in range(c+1):
  wi = wt[0]
  if wi<=w:
    dp[0][w]=val[0]
  else:
    dp[0][0]=0

for i in range(1,n):
  wi = wt[i];vi = val[i]
  for w in range(1,c+1):
    if wi<=w:
      dp[i][w] = max(vi+dp[i-1][w-wi] , dp[i-1][w])
    else:
      dp[i][w] = dp[i-1][w]

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(N)]
w = [0]*(N+1) # 商品番号とのズレが嫌だったのでこっちも1足しといた
v = [0]*(N+1)
for i in range(N):
    w[i+1], v[i+1] = wv[i]

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

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

print(dp[N][W])

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 円以下で買える商品の最大価値
# TLE案件のやつ
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:
n,W = map(int,input().split())
wt =[];val=[]

dp = [[0 for i in range(W+1)] for j in range(n)]
for _ in range(n):
  wi , vi= map(int,input().split())
  wt.append(wi)
  val.append(vi)

for i in range(W+1):
  if i>=wt[0]:
    dp[0][i]=val[0]   
  else:
    dp[0][i]=0
    
    
    
#print(dp)  
for i in range(1,n):
  wi = wt[i]
  vi = val[i]
  for w in range(1,W+1):
    if wi <= w:
      dp[i][w] = max(vi + dp[i-1][w-wi] , dp[i-1][w] )
    else:
      dp[i][w] = dp[i-1][w]

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

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,w = get_nums_l()
ppp = list(map(lambda s: tuple(map(int,s.strip().split())), sys.stdin.readlines()))

# dp[i] = 重さiで得られる最大の価値
dp = [0] * (w+1)

for p in ppp:
    we = p[0]
    va = p[1]
    for i in reversed(range(len(dp))):
        if i+we > w:
            continue
        ne = i+we
        dp[ne] = max(dp[ne], dp[i]+va)

# log(dp)

print(max(dp))

Submission status: Accepted

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

for i in range(N):
    w[i], v[i] = map(int, input().split())
    
#dp[3][5] 3個目までの荷物で5容量のときの最大value
dp = [[0]*(W+1) for i in range(N+1)]

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

Submission status: Accepted

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

def main():
    n, w = map(int, input().split())

    dp = [0] * (w + 1)

    for _ in range(n):
        wi, vi = map(int, input().split())

        for wj in range(w, wi - 1, -1):
            nv = dp[wj - wi] + vi
            if dp[wj] < nv:
                dp[wj] = nv

    print(max(dp))

main()

Submission status: Accepted

Solution code:
n,w = map(int,input().split())

lstw, lstv = [], []
for i in range(n):
    w_,v_ = map(int,input().split())
    lstw.append(w_)
    lstv.append(v_)

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

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

Submission status: Accepted

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

w, v = [], []
for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

# dp[in_n_items][below_w_weight] = max_value
dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]

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

Submission status: Accepted

Solution code:
import numpy as np
N, W = map(int, input().split())
dp = np.zeros(W+1)
for i in range(N):
  w, v = map(int, input().split())
  dp[w:] = np.maximum(dp[:-w]+v, dp[w:])
print(int(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 = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]

from collections import Counter

dp = Counter()
dp[0] = 0
for w, v in WV:
  ndp = Counter()
  for k in dp:
   	ndp[k] = max(dp[k], ndp[k])
   	if k+w <= W:
   	 	ndp[k+w] = max(dp[k] + v, ndp[k+w])
  dp = ndp
print(dp.most_common()[0][1])

Submission status: Accepted

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


def main():
    n, w = map(int, input().split())
    wv = [tuple(map(int, input().split())) for _ in range(n)]

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
INF = float('inf')
MAX_N = 110
MAX_W = 10**5 + 100

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

dp = [[0]*MAX_W for _ in range(MAX_N)]

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:


import sys
input = sys.stdin.readline

def main():
    #1:初期化
    N,W = map(int,input().split())
    wv = []
    for _ in range(N):
        wv.append(list(map(int,input().split())))
    dp = [[0]*(W+1) for i in range(N+1)]

    #print(dp)
    #print(dp2)
    #2:初期値(元からゼロなので記述無し)

    #3:dp実行部(貰うDP)
    for i in range(1,N+1):
        for j in range(1,W+1):
            if wv[i-1][0] <= j: #dpの横が重さだが，jが重さ以下ならそもそも入れられない．
                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(i,j)
            #print(*dp,sep="\n")

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""memo
    numpyでやるときは配列を一気に更新するが(numpy使いたくないのでやらない)，
    このやり方は後ろの方から更新することで後の更新に影響を与えない(考え方すごい)．
    (参考#9889377)
"""

import sys
input = sys.stdin.readline

def main():
    #1:初期化
    N,W = map(int,input().split())
    dp = [0]*(W+1)

    #2:初期値(元からゼロなので記述無し)

    #3:dp実行部(貰うDP)
    for i in range(N):
        w, v = map(int,input().split())
        for i in range(W, w-1, -1):
            tmp = dp[i-w] + v
            if dp[i] < tmp:
                dp[i] = tmp
        #print(dp,sep="\n")

    #4:出力
    print(max(dp))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import numpy as np

N, W = map(int, input().split())
wv = []
#i番目までを詰めたときの最大の価値を記録
dp = np.zeros(W+1)
for i in range(N):
    w, v = map(int, input().split())
    dp[w:] = np.maximum(dp[:-w]+v, dp[w:])

print(int(dp[-1]))

Submission status: Accepted

Solution code:
n, w = [int(i) for i in input().split(" ")]
vw = []
for i in range(n):
  vw.append([int(i) for i in input().split(" ")])

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

Submission status: Accepted

Solution code:
def main():
  from collections import deque
  n,w=map(int,input().split())
  item=deque([list(map(int,input().split())) for _ in range(n)])
  DP=[[0]*(w+1) for _ in range(n+1)]
  for i in range(1,n+1):
    itemNow=item.popleft()
    weight=itemNow[0]
    value=itemNow[1]
    for j in range(w+1):
      if j<weight:
        DP[i][j]=DP[i-1][j]
      else:
        DP[i][j]=max(DP[i-1][j],DP[i-1][j-weight]+value)
        
  print(DP[n][w])
      
if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,w=mii()
wei,val=[0],[0]

for i in range(n):
    x,y=mii()
    wei.append(x)
    val.append(y)

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 >= wei[i]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-wei[i]]+val[i])
        else:
            dp[i][j] = dp[i-1][j]

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,w=mii()
wei,val=[0],[0]

for i in range(n):
    x,y=mii()
    wei.append(x)
    val.append(y)

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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,w=map(int,input().split())
WV=[tuple(map(int,input().split())) for i in range(n)]
dp=[0]*(w+1)
for i in range(n):
  wi,vi=WV[i]
  for di in range(w,-1,-1):
    if not (0<=di-wi<10**7+10): continue
    dp[di]=max(dp[di],dp[di-wi]+vi)
print(dp[w])
# print(dp)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

for item in range(n):
    now_w=wv[item][0]
    now_v=wv[item][1]

    for weight in range(w+1):
        ans1=dp[item][weight]
        ans2=-1
        if weight - now_w >= 0:
            ans2=dp[item][weight-now_w]+now_v
        dp[item+1][weight] = max(ans1,ans2)

print(dp[n][w])

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
#0 weight , [1] value
table = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * (w+1) for i in range(n+1)]

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

for i in range(n):
    for j in range(w+1):
        if(j >= table[i][0]):
            dp[i+1][j] = choice_max(
                            dp[i][j],
                            dp[i][j - table[i][0]] + table[i][1]
                            )
        else:
            dp[i+1][j] = dp[i][j]
#[print(item)for item in dp]
print(dp[n][w])

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
WEIGHTS = list(list(map(int, input().split())) for _ in range(N))
M = len(WEIGHTS)

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

for i, (weight, value) in enumerate(WEIGHTS):
    for w in range(W + 1):
        if w - weight >= 0:
            DP[i+1][w] = max(DP[i][w - weight] + value, DP[i][w])
        else:
            DP[i+1][w] = DP[i][w]

print(DP[M][W])

# dp_ij := 1~jまでのアイテムからいくつかを選んで総重量iを超えないようにしたときの最大価値

# 0 1 2 3  4  5  6  7  8
# 0 0 0 0  0  0  0  0  0
# 0 0 0 30 30 30 30 30 30
# 0 0 0 30 50 50 50 80 80
# 0 0 0 30 50 60 60 80 90

Submission status: Accepted

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

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

def do_dp():
  for i,thing in enumerate(things):
    dp_1 = dp[i-1]
    for j in range(1, w + 1):      
      dp[i][j] = dp_1[j-thing[0]] + thing[1]  if (j - thing[0]) >= 0 else dp_1[j]
      dp[i][j] = max(dp[i][j], dp_1[j])

do_dp()
print(dp[n][w])

Submission status: Accepted

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

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



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

    print(dp[0][W])
if __name__ == "__main__":
    main() #endline===============================================