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 pdb
input = sys.stdin.readline

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

# Value[i番目までの品番][重さj以下]
Value = [[0 for _ in range(W+1)] for __ in range(N)]

for load in range(W+1):
  if load < ws[0]:
    # 1番目の品物を入れようがなければスキップ
    Value[0][load] = 0
  else:
    Value[0][load] = vs[0]

for num in range(1, N):
  for load in range(W+1):
    if load >= ws[num]:   # 新しい品物を入れられるとき
      Value[num][load] = max(Value[num][load], Value[num-1][load], Value[num-1][load-ws[num]] + vs[num])
    else:   # 新しい品物を入れられないとき
      # 価値を変えることはできない
      Value[num][load] = Value[num-1][load]
      # Value[num][load] = max(Value[num][load], Value[num-1][load])

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

Submission status: Accepted

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

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

inf = 1e10

# Value[i番目までの品番][重さj以下]
Value = [[-inf for _ in range(W+1)] for __ in range(N)]

for load in range(W+1):
  if load < ws[0]:
    # 1番目の品物を入れようがなければスキップ
    Value[0][load] = 0
  else:
    Value[0][load] = vs[0]

for num in range(1, N):
  for load in range(W+1):
    if load >= ws[num]:   # 新しい品物を入れられるとき
      Value[num][load] = max(Value[num][load], Value[num-1][load], Value[num-1][load-ws[num]] + vs[num])
    else:   # 新しい品物を入れられないとき
      # 価値を変えることはできない
      Value[num][load] = Value[num-1][load]
      # Value[num][load] = max(Value[num][load], Value[num-1][load])

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

Submission status: Accepted

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

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

inf = 1e10

# Value[i番目までの品番][重さj以下]
Value = [[-inf for _ in range(W+1)] for __ in range(N)]

for load in range(W+1):
  if load < ws[0]:
    # 1番目の品物を入れようがなければスキップ
    Value[0][load] = 0
  else:
    Value[0][load] = vs[0]

for num in range(1, N):
  for load in range(W+1):
    if load >= ws[num]:   # 新しい品物を入れられるとき
      # 本来はこれ。負の価値の品物があるならばこれが正しい
      Value[num][load] = max(Value[num][load], Value[num-1][load], Value[num-1][load-ws[num]] + vs[num])
      # すべての品物の価値が正なので、入れられるなら入れた方が良い
      # Value[num][load] = max(Value[num][load], Value[num-1][load-ws[num]] + vs[num])
    else:   # 新しい品物を入れられないとき
      # 価値を変えることはできない
      Value[num][load] = Value[num-1][load]
      # Value[num][load] = max(Value[num][load], Value[num-1][load])

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

Submission status: Accepted

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

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

inf = 1e10

# Value[i番目までの品番][重さj以下]
Value = [[-inf for _ in range(W+1)] for __ in range(N)]

for load in range(W+1):
  if load < ws[0]:
    # 1番目の品物を入れようがなければスキップ
    Value[0][load] = 0
  else:
    Value[0][load] = vs[0]

for num in range(1, N):
  for load in range(W+1):
    if load >= ws[num]:
      # pdb.set_trace()
      # print(num, load, ws[num], vs[num])
      Value[num][load] = max(Value[num][load], Value[num-1][load], Value[num-1][load-ws[num]] + vs[num])
    else:
      Value[num][load] = max(Value[num][load], Value[num-1][load])

print(Value[N-1][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 = [[0]*(W+1) for _ in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if j < w[i]:
            dp[i+1][j] = 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:
import sys
input = sys.stdin.readline
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:
n,w=map(int,input().split())
items=[]
dp=[0 for i in range(w+1)]
for i in range(n):
    wi,vi=map(int,input().split())
    for j in range(w-wi,-1,-1):
        dp[j+wi]=max(dp[j+wi],dp[j]+vi)
print(max(dp))

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)

c = [[0 for j in range(W)] for i in range(n)]
for i in range(W):
    if i+1 < w[0]:
        c[0][i] = 0
    else:
        c[0][i] = v[0]

for i in range(1,n):
    for j in range(W):
        if j+1 < w[i]:
            c[i][j] = c[i-1][j]
        else:
            diff = (j+1)-w[i]
            if diff > 0:
                c[i][j] = max(c[i-1][j], v[i]+c[i-1][diff-1])
            else:
                c[i][j] = max(c[i-1][j], v[i])
print(max(c[-1]))

Submission status: Accepted

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

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

for i in range(N):
    for sum_w in range(W+1):
        # i 番目の品物を選ぶ場合
        if sum_w >= weight[i]:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - weight[i]] + value[i])
        # i 番目の品物を選ばない場合
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

print(dp[N][W])

Submission status: Accepted

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

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

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

print(max(dp[n]))

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

for i in range(wv[0][0], w+1):
    dp[0][i] = wv[0][1]

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


Item = collections.namedtuple("Item", ("weight", "value"))


def main():
    N, W = [int(i) for i in input().split()]
    items = [Item(int(i), int(j))for (i, j) in [input().split() for _ in range(N)]]
    # 選択肢をn番目の品物まで、重さを最大wとしたときの価値の最大値
    dp = [[0] * (W + 1) for _ in range(N + 1)]

    # n番目の品物まで含む
    for n in range(1, N + 1):
        # 重さの最大値がw
        for w in range(W + 1):
            # n番目の品物
            item = items[n - 1]
            # 買う（＝買える）
            if w - item.weight >= 0:
                dp[n][w] = max(dp[n][w], dp[n - 1][w - item.weight] + item.value)
            # 買わない（＝買えない）場合も行う
            dp[n][w] = max(dp[n][w], dp[n - 1][w])

    ans = dp[N][W]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
def fun(n,w):
 cos=[0]*(w+1)
 for i in range(n):
  w1,v1=map(int,input().split())
  for j in range(w,w1-1,-1):
   f=cos[j-w1]+v1
   if(cos[j]<f):
    cos[j]=f
 print(cos[-1])
n,w=map(int,input().split())
fun(n,w)

Submission status: Accepted

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

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

print(max(dp[-1]))

Submission status: Accepted

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

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

for w, v in L:
    #重さを足し合わせていき合計を求める
    cnt = cnt + w
    #W=重さの制約とこれまでの重さの合計のうち、
    #小さい方から品物iの重さまで、逆順にfor文を回す
    ##3,8-5,...15-7
    for i in range(min(cnt, W), w - 1, -1):
        #同じ重さでより価値が高い組み合わせがあれば価値を更新する
        ## w < Wの制約があり、i - wとその値を参照してから更新しているため、
        ## Wの制約を満たさない値を持つことはない
        ### 方法上、持ち得ない重さに持ち得ない値がつくことがあるが、
        ### それらが解 = 最大値になることはない
        ### (解を求める過程でついでに足されたり足されなかったりするだけなので)
        if dp[i] < dp[i - w] + v:
            dp[i] = dp[i - w] + v

print(max(dp))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
import datetime
import itertools
import sys
import copy

# 入力
#N = int(input())
#S = str(input())
#N, A, B = map(int, input().split())

N, W = map(int, input().split())
H = []
for _ in range(N) :
  H.append(list(map(int, input().split())))
#print(H)

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) :
    dp[i][j] = max(dp[i-1][j], dp[i][j])
    if dp[i-1][j] > 0 and j+H[i-1][0] <= W:
      dp[i][j+H[i-1][0]] = max(dp[i-1][j+H[i-1][0]], dp[i-1][j] + H[i-1][1])
    
  dp[i][H[i-1][0]] = max(dp[i-1][H[i-1][0]], H[i-1][1])
  #print (dp[i])      
#print (dp)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
import datetime
import itertools
import sys
import copy

# 入力
#N = int(input())
#S = str(input())
#N, A, B = map(int, input().split())

N, W = map(int, input().split())
H = []
for _ in range(N) :
  H.append(list(map(int, input().split())))
#print(H)

#N(i+1)個目の品物を追加したときにWjとなる場合のWj地点の最大価値
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) :
    dp[i][j] = max(dp[i-1][j], dp[i][j])
    if dp[i-1][j] > 0 and j+H[i-1][0] <= W:
      dp[i][j+H[i-1][0]] = max(dp[i-1][j+H[i-1][0]], dp[i-1][j] + H[i-1][1])
    
  dp[i][H[i-1][0]] = max(dp[i-1][H[i-1][0]], H[i-1][1])
  #print (dp[i])      
#print (dp)

print (max(dp[N]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,w = map(int, input().split())
a = [[int(x) for x in input().split()] for i in range(n)]
dp = [-1 for i in range(w + 1)]
dp[0] = 0
for i in range(n):
    for j in range(w, -1, -1):
        if dp[j] != -1 and j + a[i][0] <= w:
            dp[j + a[i][0]] = max(dp[j + a[i][0]], dp[j] + a[i][1])
print(max(dp))

Submission status: Accepted

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

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

    for n in range(N):
        weight, value = map(int, input().split())

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

    print(dp[N][W])


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)

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
# dp[m][w] mまで使ってwを超えない価値の最大値
dp = [[0] * (W + 100) for _ in range(N + 10)]

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

# dp[m][w] mまで使ってwを超えない価値の最大値
dp = [[0] * (W + 1) for _ in range(N + 1)]


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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
n,w = map(int,input().split())
weight = [0 for i in range(n)]
value = [0 for i in range(n)]
for i in range(n):
    weight[i],value[i] = map(int,input().split())
    
 
#dp[i][j]: i番目の品物までの中から選び、重さがj以下になる時の、価値の総和の最大値
dp = [[0 for i in range(w+1)] for j in range(n+1)]
 
for i in range(n):
    for j in range(w+1):
        if j - weight[i] >= 0:
            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:
n,w = map(int,input().split())
weight = [0 for i in range(n)]
value = [0 for i in range(n)]
for i in range(n):
    weight[i],value[i] = map(int,input().split())
    

#dp[i][j]: i番目の品物までの中から選び、重さがj以下になる時の、価値の総和の最大値
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):
        dp[i][j] = max(dp[i][j],dp[i-1][j])
        if(j - weight[i-1] >= 0):
            dp[i][j] = max(dp[i-1][j-weight[i-1]]+value[i-1],dp[i][j])
            
print(dp[n][w])

Submission status: Accepted

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

#dp[i][j]: i番目の品物までの中から選び、重さがj以下になる時の、価値の総和の最大値
dp = [[None for i in range(w+1)] for j in range(n+1)]
dp[1][weight[0]] = value[0]

for i in range(1,n):
    for j in range(w+1):
        if j - weight[i] >= 0:
            if dp[i][j-weight[i]] != None and dp[i][j] != None:
                dp[i+1][j] = max(dp[i][j-weight[i]]+value[i],dp[i][j])
            elif dp[i][j-weight[i]] == None and dp[i][j] != None:
                dp[i+1][j] = dp[i][j]
            elif dp[i][j-weight[i]] != None and dp[i][j] == None:
                dp[i+1][j] = dp[i][j-weight[i]]+value[i]
            else:
                dp[i+1][weight[i]] = value[i]
        else:
            dp[i+1][j] = dp[i][j]
            
print(max(i for i in dp[n] if i is not None))

Submission status: Accepted

Solution code:
n,w = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(n)]
#dp[i][j]はi番目まででj(j<=w)になるもの
dp = [[0]*(w+1) for i in range(n)]
for k in range(w+1):
  if k >= wv[0][0]:
    dp[0][k] = wv[0][1]
  else:
    continue
for i in range(n-1):
  for j in range(w+1):
    if j >= wv[i+1][0]:
      dp[i+1][j] = max(dp[i][j-wv[i+1][0]]+wv[i+1][1],dp[i][j])
    else:
      dp[i+1][j] = dp[i][j]
print(dp[n-1][w])

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[0]*(W+1) for _ in range(2)]

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

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

Submission status: Accepted

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


dp = [[0 for i in range(100100)] for _ in range(110)]

for i in range(N):
    for sw in range(W + 1):
        if sw - Wt[i] >= 0:
            dp[i+1][sw] = max(dp[i+1][sw], dp[i][sw-Wt[i]] + Vt[i])
        dp[i+1][sw] = max(dp[i+1][sw], dp[i][sw]) 

print(dp[N][W])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
b = [tuple(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 + b[i][0] <= W:
      dp[i + 1][j + b[i][0]] = max(dp[i][j] + b[i][1], dp[i + 1][j + b[i][0]])
    dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(max(dp[-1]))

Submission status: Accepted

Solution code:
from pprint import pprint
import sys

N, W = map(int, sys.stdin.readline().strip().split(" "))

w = []
for _ in range(N):
    w_i, v_i = map(int, sys.stdin.readline().strip().split(" "))
    w.append((w_i, v_i))

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


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

Submission status: Accepted

Solution code:
from pprint import pprint
import sys

N, W = map(int, sys.stdin.readline().strip().split(" "))

w = []
for _ in range(N):
    w_i, v_i = map(int, sys.stdin.readline().strip().split(" "))
    w.append((w_i, v_i))

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


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

Submission status: Accepted

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

for i in range(n):
    wi, vi = map(int, input().split())
    np.maximum(ndp[:-wi]+vi, ndp[wi:], out=ndp[wi:])

print(int(ndp[-1]))

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)]
weight = []
value = []
for i in range(N):
    w,v = map( int, input().split() )
    weight.append(w)
    value.append(v)

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

Submission status: Accepted

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

Submission status: Accepted

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


def f(n, W):
    dp = [0] * (W + 1)
    for i in range(n):
        wi, vi = map(int, input().split())
        for w in range(W, wi - 1, -1):
            v_ = dp[w - wi] + vi
            if dp[w] < v_:
                dp[w] = v_
    return(dp[-1])


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

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**7)
    N,W=list(map(int,sys.stdin.readline().split()))

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

    WL=[0]*N
    VL=[0]*N

    for i in range(N):
        w,v=list(map(int,sys.stdin.readline().split()))
        WL[i]=w
        VL[i]=v

    for i in range(1,N+1):
        for w in range(1,W+1):
            if w>=WL[i-1]:
                a=dp[i-1][w-WL[i-1]]+VL[i-1]
                b=dp[i-1][w]
                dp[i][w]=max(a,b)
            else:
                dp[i][w]=dp[i-1][w]
    print(dp[-1][-1])
main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

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

print(dp[-1])

Submission status: Accepted

Solution code:
def knapsack(N,W,wv):
  #初期化
  inf=float("inf")
  dp=[[-inf for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0

  #DP
  for i in range(N):
    for w in range(W+1):
      if wv[i][0]<=w: #dp[i][w-wv[i][0]]の状態にi番目の荷物が入る可能性がある
        dp[i+1][w]=max(dp[i][w-wv[i][0]]+wv[i][1], dp[i][w])
      else: #入る可能性はない
        dp[i+1][w]=dp[i][w]
  return dp[N][W]

if __name__ == "__main__":
  N, W = map(int, input().split())
  wv = [list(map(int, input().split())) for i in range(N)]
  ans = knapsack(N, W, wv)
  print(ans)

Submission status: Accepted

Solution code:
def woo(n, w):
	res = [0 for i in range(0, w+1)]

	for i in range(0, n):
		ww, vv = map(int, input().split())
		for j in range(w, ww-1, -1):
			wtotal = j + ww
			vtotal = res[j-ww] + vv
			if vtotal > res[j]:
				res[j] = vtotal

	return res

if __name__ == '__main__':
	n, w = map(int, input().split())
	r = woo(n, w)
	print(max(r))

Submission status: Accepted

Solution code:
import numpy as np

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

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

print(dp.max())

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
weight=[]
value=[]
for i in range(n):
    q,r=map(int,input().split())
    weight.append(q)
    value.append(r)

dp=[[0 for _ in range(100100)] for _ in range(110)]

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

print(dp[n][w])

Submission status: Accepted

Solution code:
n,w = map(int,input().split())
#list1[i][重さw,価値v]
list1 = [list(map(int,input().split())) for i in range(n)]

#1次元配列で、更新していく形で解くこととする。(本来i,j方向に2次元配列で解く)
dp = [0]*(w+1) #wは0,1,2,...,wとなる
"""
#こっちのループは、重さを外側で、商品を内側で回しているので、
#商品の重複を許すことになる。よって、商品を外側で回さなければならない。
for i in range(w+1): #iには現在の重さが入る
    for j in range(n): #jには各商品が入る
        if i - list1[j][0] >= 0:
            dp[i] = max(dp[i-list1[j][0]]+list1[j][1],dp[i])
"""

for i in range(n):
    for j in range(w,-1,-1): #後ろから見ることで重複を避けている。※
        if j - list1[i][0] >= 0:
            dp[j] = max(dp[j-list1[i][0]]+list1[i][1],dp[j])
"""
※例えば、i=0のループで、
jを前から回すと、wの条件を満たすたびにlist1[i][1]が足されていくので、
一つの商品に対して何度も重複を許すことになる。但し、後ろから回せば
dp[j-list1[i][0]]は必ずその要素を足し合わせていない値であることがわかる。
これを前から回したいときは、適宜一周前のループを参照する必要があるため、
二次元配列を作成する必要がある。
"""
print(dp[-1])

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
weight=[]
value=[]
for i in range(n):
    q,r=map(int,input().split())
    weight.append(q)
    value.append(r)

dp=[[0 for i in range(100111)] for j in range(111)]

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

print(dp[n][w])

Submission status: Accepted

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