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


input = sys.stdin.readline
N,W  = map(int,input().split())
dp = np.zeros((N+1,W+1),dtype=int)
w,v = [],[]
for _ in range(N):
    w_,v_ = map(int,input().split())
    w.append(w_)
    v.append(v_)

for row in range(N):
    dp[row+1,:w[row]] = dp[row,:w[row]]
    dp[row+1,w[row]:] = np.maximum(dp[row,w[row]:],v[row]+dp[row,:-w[row]])
print(dp[N,-1])

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 = [[0]*(W+1) for _ in range(N+1)]
# dp[i][sum_w]
# i-1番目までの品物から重さがsum_wを超えないように選んだ時の価値の総和
# sum_w = 0, 1, 2, ... ,W

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

        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
print(dp[N][W])

Submission status: Accepted

Solution code:
N, W = 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+1) for _ in range(N+1)]
# dp[i][sum_w]
# i-1番目までの品物から重さがsum_wを超えないように選んだ時の価値の総和
# sum_w = 0, 1, 2, ... ,W

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

        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
print(dp[N][W])

Submission status: Accepted

Solution code:
def solve():
    n,w = map(int,input().split())
    w_list,v_list = [0]*n,[0]*n
    for i in range(n):
        w_list[i],v_list[i] = map(int,input().split())
    dp = [[0]*(w+5) for i in range(n+5)]
    for i in range(n):
        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-1][w])
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:

def solve():
    n,w = map(int,input().split())
    w_list,v_list = [0]*n,[0]*n
    for i in range(n):
        w_list[i],v_list[i] = map(int,input().split())
    dp = [[0]*(w+5) for i in range(n+5)]
    for i in range(n):
        for j in range(w+1):
            if j-w_list[i]>=0:
                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-1][w])
    return 0
 
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

for j in range(W+1):
    if WV[0][0]>j:
        dp[0][j]=0
    else:
        dp[0][j]=WV[0][1]

for i in range(1,N):
    newW = WV[i][0]
    newV = WV[i][1]
    for j in range(1,W+1):
        if j-newW>=0:
            dp[i][j] = dp[i-1][j-newW]+newV
        dp[i][j] = max(dp[i-1][j],dp[i][j-1],dp[i][j])
#print(*dp,sep='\n')
print(dp[-1][-1])

Submission status: Accepted

Solution code:
#ABC164C
def main():
    import sys
    import copy
    N, limit = map(int, sys.stdin.readline().split())
    L = tuple([tuple(map(int, sys.stdin.readline().split())) for _ in range(N)])
    dp = [[0 for _ in range(limit+1)] for _ in range(N)]
    dp[0][L[0][0]] = L[0][1] #初期値
    for i in range(1, N):
        dp[i] = copy.copy(dp[i-1]) #前回をコピー(初)
        w, v = L[i][0], L[i][1]
        dp[i][w] = max(v, dp[i][w])
        for j in range(limit+1-w):
            if dp[i-1][j] >0:
                dp[i][w+j] = max(v+ dp[i-1][j], dp[i][w+j])
            
    
    
    print(max(dp[-1]))



if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, w = tuple([int(e) for e in input().split()])
    items = []
    for i in range(n):
        items.append(tuple([int(e) for e in input().split()]))
    
    t = [[0] * (n + 1) for _ in range(w + 1)]
    for i in range(1, w + 1):
        for j in range(1, n + 1):
            if i - items[j - 1][0] >= 0:
                t[i][j] = t[i - items[j - 1][0]][j - 1] + items[j - 1][1]
            t[i][j] = max(t[i][j], t[i][j - 1], t[i - 1][j], t[i - 1][j - 1])
    print(t[w][n])
    return 0

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n, w = tuple([int(e) for e in input().split()])
    items = []
    for i in range(n):
        items.append(tuple([int(e) for e in input().split()]))
    items.sort(key=lambda x: x[0])
    
    t = [[0] * (n + 1) for _ in range(w + 1)]
    for i in range(1, w + 1):
        for j in range(1, n + 1):
            if i - items[j - 1][0] >= 0:
                t[i][j] = t[i - items[j - 1][0]][j - 1] + items[j - 1][1]
            t[i][j] = max(t[i][j], t[i][j - 1], t[i - 1][j], t[i - 1][j - 1])
    print(t[w][n])
    return 0

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)

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

Submission status: Accepted

Solution code:
import numpy as np
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
dp=np.zeros(w+1,np.int64)
# dp[j]:重さがwを超えないようにカバンに入れた時の価値の最大
# dp[0]=0
for i in range(n):
      w_=wv[i][0]
      v_=wv[i][1]
      dp[w_:]=np.maximum(dp[w_:],dp[:-w_]+v_)
print(dp[-1])

Submission status: Accepted

Solution code:
def main():
    n, w= map(int, input().split())
    w_item = []
    v_item = []
    dp = [[0 for _ in range(w+1)] for _ in range(n+1)]
    for _ in range(n):
        tmp_w, tmp_v = map(int, input().split())
        w_item.append(tmp_w)
        v_item.append(tmp_v)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  n,w=map(int,input().split())
  wv=[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):
      dp[i+1][j]=max(dp[i][j-wv[i][0]]+wv[i][1],dp[i][j]) if j-wv[i][0]>=0 else dp[i][j]
  print(dp[n][w])
if __name__=='__main__':
  main()

Submission status: Accepted

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

score = [0] * (W+1)

for n in range(N) :
  w, v = map(int,raw_input().split())
  for i in range(w, W+1) :
    score[i-w] = max(score[i-w], score[i] + v)

print score[0]

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, W = map(int, input().split())
    wv = [tuple(map(int, input().split())) for i in range(N)]

    dp = [-1]*(W+1)
    dp[0] = 0
    for w, v in wv:
        for j in range(W-w, -1, -1):
            if dp[j] >= 0 and dp[j+w] < dp[j]+v:
                dp[j+w] = dp[j] + v

    print(max(dp))


main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest


def resolve():
    N, W = map(int, input().split())

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

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

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

    # 選ぶ選ばないだと2^n
    for i in range(0, N - 1):
        w = wv[i + 1][0]
        v = wv[i + 1][1]
        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(max([l[-1] for l in dp]))



class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 8
3 30
4 50
5 60"""
        output = """90"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000"""
        output = """5000000000"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """6 15
6 5
5 6
6 4
6 6
3 5
7 2"""
        output = """17"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

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=[[0]*(W+1) for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,W+1):
        if j<w[i-1]:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])
print(dp[N][W])

Submission status: Accepted

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

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

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

Submission status: Accepted

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



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


print(dp[N][W])

Submission status: Accepted

Solution code:
# PyPy3

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

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

npsk_1(N, W)

Submission status: Accepted

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

for i in range(n):
  w,v=map(int,input().split())
  for j in range(m,w-1,-1):
    dp[j]=max(dp[j-w]+v,dp[j])
    
print(dp[m])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int, input().split())))
# print(wv)
dp = [[0] * 100100 for _ in range(110)]


for i in range(N):
    for sum_w in range(W + 1):

        if wv[i][0] <= sum_w:
            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][W])

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
from copy import copy
a=[0]*(w+1)
for i in range(n):
    b=copy(a)
    x,y=map(int,input().split())
    for j in range(min(x,w),w+1):
        b[j]=max(a[j-x]+y,a[j])
    a=copy(b)
print(max(a))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
WV = [tuple(map(int, input().split())) for i in range(n)]
W = [w for w, v in WV]
V = [v for w, v in WV]
DP = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1, n+1):
    for j in range(W[i-1]):
        DP[i][j] = DP[i-1][j]
    for j in range(W[i-1], m+1):
        DP[i][j] = max(DP[i-1][j], DP[i-1][j-W[i-1]]+V[i-1])
print(DP[n][m])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
inf = float("inf")

n_item, w_volume = map(int, input().split())
weight, value = [], []
for _ in range(n_item):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)
# print(n_item, w_volume, weight, value)

# dp[i + 1][w]: i番目までの商品から重さがwを超えないよういくつか選んだときの価値の最大値
# 商品iを選ぶことができるとき (w - weight[i] >= 0 のとき)
# dp[i + 1][w] = max(dp[i + 1][w], dp[i][w - weight[i]] + value[i])
# 商品iを選ぶことができないとき
# dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])

dp = [[0 for w in range(w_volume + 1)] for i in range(n_item + 1)]

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

print(dp[n_item][w_volume])

Submission status: Accepted

Solution code:
def resolve():
    n, w = map(int, input().split())
    ws, vs = [0]*n, [0]*n
    for i in range(n):
        ws[i], vs[i] = map(int, input().split())
    dp = [[0]*(w+1) for _ in range(n+1)]
    for i in range(n):
        for j in range(w+1):
            if j >= ws[i]:
                dp[i][j] = max(dp[i][j], dp[i-1][j - ws[i]] + vs[i])
            dp[i][j] = max(dp[i][j], dp[i-1][j] if i - 1 >= 0 else 0)
    print(dp[n-1][w])
resolve()

Submission status: Accepted

Solution code:
def knapsack_dp(n,w,wts,val):
    dp=[[0]*(w+1) for i in range(n+1)]

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

    return dp[n][w]


n,w=map(int,input().split())
wts,vals=[],[]
for i in range(n):
    a,b=map(int,input().split())
    wts.append(a)
    vals.append(b)

print(knapsack_dp(n,w,wts,vals))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(10e9)


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]

n,w=mdata()
val=[0]*(n)
wt=[0]*(n)
for i in range(n):
    wt[i],val[i]=mdata()
print(knapSack(w,wt,val,n))

Submission status: Accepted

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

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

INFTY = -1*10**7
dp = [[0]*(W+1) for _ in range(N)]
dp[0][S[0][0]] = S[0][1]

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
#DP D
def main():
    import sys
    N, W = map(int, sys.stdin.readline().split())
    L = tuple([tuple(map(int, sys.stdin.readline().split())) for _ in range(N)])
    #print(L)
    dp = [[0 for i in range(10**5+1)] for _ in range(N)]
    for i in range(N):
        w, v = L[i][0], L[i][1]
        if i>=1:
            dp[i][w] = max(v, dp[i-1][w])
        elif i==0:
            dp[i][w] = v
        for j in range(10**5+1):
            if i>=1 and dp[i-1][j]!=0:
                dp[i][j] = max(dp[i-1][j], dp[i][j])
                if w+j <=10**5:
                    dp[i][w+j] = max(dp[i-1][w+j], v + dp[i-1][j])
                
    print(max(dp[-1][:W+1]))



if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin


# 最大化問題
def chmax(a,b):
    if a < b: return b
    else: return a


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, W = list(map(int,_in[0].split(' ')))  # type:list(int)
    w_v_arr = []
    for i in range(N):
        _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
        w_v_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    dp = [[0] * (W+1) for _ in range(N+1)] # 最大化問題 (初期条件 dp=0)
    
    # 配るDP
    for i in range(N):
        for w in range(1,W+1):
            if w >= w_v_arr[i][0]:
                dp[i+1][w] = chmax(dp[i+1][w],dp[i][w-w_v_arr[i][0]]+w_v_arr[i][1])
            dp[i+1][w] = chmax(dp[i+1][w],dp[i][w])
    cnt = dp[N][W]
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

Submission status: Accepted

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

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N, W = MAP()
w, v = [], []
for _ in range(N):
    wi, vi = MAP()
    w.append(wi)
    v.append(vi)

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

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

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

Submission status: Accepted

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

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 < 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())
 
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(np.max(dp))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import numpy as np
n,w=map(int,input().split())
wv=[]
for _ in range(n):
    wv.append(list(map(int,input().split())))
dp=np.zeros(w+1,np.int64)
for i in range(n):# i番目までの商品について全ての重さについて調べる
    w_=wv[i][0]
    v_=wv[i][1]
    dp[w_:]=np.maximum(dp[w_:],dp[:-w_]+v_)

print(dp[-1])

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
w = []
v = []
for _ in range(N):
    x, y = map(int, input().split())
    w.append(x)
    v.append(y)
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, W+1):
        dp[i][j] = max(dp[i][j], dp[i-1][j])
        if j - w[i-1] < 0:
            continue
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])
# print(*dp, sep='\n')
print(dp[N][W])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import copy
n,w = map(int,input().split())
b = [0]*(w+1)
a = [0]*(w+1)
for _ in range(n):
  wi,vi = map(int,input().split())
  a = copy.copy(b)
  for i in range(min(wi,w+1),w+1):
    a[i] = max(b[i-wi]+vi,b[i])
  b = a
print(max(b))

Submission status: Accepted

Solution code:
NW = list(map(int,input().split()))
N,W = NW[0],NW[1]
wv = [map(int,input().split()) for _ in range(N)]
w,v = [list(i) for i in zip(*wv)]
dp = [[0]*(W+1) for _ in range(N+1)]#初期値は入力済み
ans = 0
for i in range(1,N+1):
    for j in range(1,W+1):
        if j-w[i-1] < 0:
            dp[i][j] = dp[i-1][j]
            ans = max(ans,dp[i][j])
        else:
            dp[i][j] = max(dp[i-1][j-w[i-1]]+v[i-1],dp[i-1][j])
            ans = max(ans,dp[i][j])
print(ans)

Submission status: Accepted

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

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


if __name__ == '__main__':
    solve()

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):
    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[N][W])

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):
    weight,value = map(int,input().split())
    for j in range(w+1):
        if j >= weight:
            dp[i+1][j] = max(dp[i][j-weight]+value,dp[i][j])
        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())
dp = np.zeros(W + 1)
for n 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:
import copy

N,W=map(int,input().split())
G=[0]   #G[0]はダミー
for index1 in range(N):
    w,v=map(int,input().split())
    G.append((w,v))

#DP[i][j]=i番目までの品物を使って重さj以下の最大価値
DP=[[0]*(W+1)]
inf=float('inf')
component=[0]+[-inf]*W
for index2 in range(N):
    DP.append(copy.copy(component))

for i in range(1,N+1):
    for j in range(1,W+1):
        if j>=G[i][0]:
            DP[i][j]=max(DP[i-1][j],DP[i-1][j-G[i][0]]+G[i][1])
        else:
            DP[i][j]=DP[i-1][j]


#for index3 in range(N+1):
    #print(DP[index3])

print(DP[N][W])

Submission status: Accepted

Solution code:
def main():
  N,W = map(int,input().split())  #nは入力回数
  num_list = [list(map(int, input().split())) for _ in range(N)]
  dp = [[0] * (W+1) for i in range(N+1)]
  weight=[row[0] for row in num_list]
  value=[row[1] for row in num_list]
  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])
      #iを選ばない場合
      dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w])
  print(int(dp[N][W]))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
w=[0 for _ in range(110)]
v=[0 for _ in range(110)]
for i in range(1,N+1):
    w[i],v[i]=map(int,input().split())
dp=[[0 for i in range(110000)] for j in range(110)]

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

print(dp[N][W])

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 sw in range(W+1):
        if sw < w:
            dp[i+1][sw] = dp[i][sw]
        else:
            dp[i+1][sw] = max((dp[i][sw]),(dp[i][sw-w]+v))
print(dp[-1][-1])

Submission status: Accepted

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

# dp[j]:重さの総和がj以下となるように選択した時の最大
dp=np.zeros(w+1,np.int64)
for i in range(n):
      # i+1個目までの商品の中から選ぶときのdpを計算する
      # i+1個目の計算をするときはdpはi個目までの商品の中から選んだ時のdpとなっている
      # i=0 ->dp=zeros
      w_=wv[i][0]
      v_=wv[i][1]
      # dp[w_:]:i+1個目の商品を加えられるのはこの部分のみ。
      # dp[w_:]:i+1個目の商品を加えないパターン
      # dp[:-w_]+v_:i+1個目の商品を加えたパターン。商品の重さだけwを減らした時の最大価値に商品の価値をプラスしている。
      dp[w_:] = np.maximum(dp[w_:], dp[:-w_] + v_)
print(dp[-1])

Submission status: Accepted

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

w,v = [],[]
for i in range(n):
    ww,vv = map(int,input().split())
    w.append(ww)
    v.append(vv)

for i in range(n):
    for ww in range(wmax+1):
        dp[i+1][ww] = dp[i][ww] if w[i]>ww else max(dp[i][ww], dp[i][ww-w[i]]+v[i])

ans = dp[n][wmax]
print(ans)

Submission status: Accepted

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

w,v = [],[]
for i in range(n):
    ww,vv = map(int,input().split())
    w.append(ww)
    v.append(vv)

#初期条件
for ww in range(w_lim+1): dp[0][ww] = v[0] if ww>=w[0] else 0

#漸化式
for i in range(n-1):
    for ww in range(w_lim+1):
        dp[i+1][ww] = dp[i][ww] if w[i+1]>ww else max(dp[i][ww], dp[i][ww-w[i+1]]+v[i+1])

ans = dp[n-1][w_lim]
print(ans)

Submission status: Accepted

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

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

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

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

for i in range(N):
    wi, vi = wv[i]

    for j in range(wi):
        dp[i+1][j] = dp[i][j]

    for j in range(wi, W+1):
        dp[i+1][j] = max(dp[i][j], dp[i][j-wi] + vi)

print(dp[N][W])

Submission status: Accepted

Solution code:
n,W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(n)]
dp = [[-(10 ** 18)] * (W+1) for i in range(n+1)]
dp[0][0] = 0
for i,(w,v) in enumerate(wv):
  for j in range(W-w+1):
    dp[i+1][j+w] = max(dp[i+1][j+w],dp[i][j]+v)
    dp[i+1][j] = max(dp[i+1][j],dp[i][j])
  for j in range(W-w+1,W):
    dp[i+1][j] = max(dp[i+1][j],dp[i][j])
print(max(dp[n]))

Submission status: Accepted

Solution code:
import sys


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

def main():

    # i have too make index as weight and value as value
    import numpy as np
    N, W = map(int, input().split())

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

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


    print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


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

    # dp = [[0] * (W + 1) for _ in range(N + 1)]
    dp = np.zeros(W + 1, dtype=np.int64)


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

    # print(w, v, dp)
    print(dp.max())


if __name__ == "__main__":
    main()