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

import collections
def main():
    N,W = map(int, input().split())
    I = collections.deque()
    for _ in range(N):
        I.append(tuple(map(int, input().split())))

    dp = [0]*(W+1)
    while I:
        w,v = I.popleft()
        for j in range(W, w-1, -1):
            x = dp[j-w] + v
            if x > dp[j]:
                dp[j] = x

    print(dp[W])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, w = [int(i) for i in input().split()]
import numpy as np
dp = np.zeros(w+1, np.int64)
for i in range(n):
    wi, vi = [int(i) for i in input().split()]
    np.maximum(dp[:-wi]+vi, dp[wi:], out=dp[wi:])
print(max(dp))

Submission status: Accepted

Solution code:
import sys
imput = sys.stdin.readline
def main():
    N, W = map(int, input().split())
    dp = [[0]*(W+1) for _ in range(N+2)]
    for i in range(1, N+1):
        w, v = map(int, input().split())
        for j in range(1, W+1):
            if j<w:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)
    print(int(dp[i][j]))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

w = [0 for _ in range(N)]
v = [0 for _ in range(N)]

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

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

Submission status: Accepted

Solution code:
import numpy as np

n,W = (int(i) for i in input().split())
items=[[int(i) for i in input().split()]for j in range(n)]

dp  = np.zeros(W+1)

for w,v in items:
    dp[w:] = np.maximum(dp[w:],v+dp[:-w])

print(int(dp[-1]))

Submission status: Accepted

Solution code:
import numpy as np

n,W = (int(i) for i in input().split())
weights = []
values = []
for j in range(n):
    wt, val = [int(i) for i in input().split()]
    weights.append(wt)
    values.append(val)

dp  = np.zeros(W+1)

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

print(int(dp[-1]))

Submission status: Accepted

Solution code:
from sys import stdin,stdout
N,W=map(int,stdin.readline().split())
matrix=[[-1 for i in range(0,W+1)]for j in range(0,N+1)]
for i in range(0,len(matrix)):
    matrix[i][0]=0
for i in range(0,len(matrix[0])):
    matrix[0][i]=0
weights=[]
values=[]
for i in range(0,N):
    w,v=map(int,stdin.readline().split())
    weights.append(w)
    values.append(v)
for item in range(1,N+1):
    for weight in range(1,W+1):
        if(weights[item-1]<=weight):
            matrix[item][weight]=max(values[item-1]+matrix[item-1][weight-weights[item-1]],matrix[item-1][weight])
        else:
            matrix[item][weight]=matrix[item-1][weight]
print(matrix[N][W])

Submission status: Accepted

Solution code:
import numpy as np

num, weight_limit = map(int, input().split())
wv_list = [list(map(int, input().split())) for _ in range(num)]

dp = np.zeros(weight_limit + 1)

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

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

print(dp[n][w])

Submission status: Accepted

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

baggage = [0]*N

for l in range(N):
    w, v = [int(x) for x in stdin.readline().rstrip().split()]
    baggage[l] = (w, v)

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

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

        else:
            dp[i+1][w] = dp[i][w]
print(dp[N][W])

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())
    np.maximum(dp[:-w]+v, dp[w:], out=dp[w:])

print(dp[-1])

Submission status: Accepted

Solution code:
N, W = (int(n) for n in input().split())
w, v = [], []
for _ in range(N):
    w_, v_ = (int(n) for n in input().split())
    w.append(w_)
    v.append(v_)

def knapsack_dp(W, w, v):
    """Solve knapsack problem by dynamic programming"""
    N = len(w)
    dp = [[0] * (W + 1) for _ in range(N + 1)]

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

    return dp[N][W]

print(knapsack_dp(W, w, v))

Submission status: Accepted

Solution code:
N, weight_capacity = (int(n) for n in input().split())
weights, values = [], []
for _ in range(N):
    w, v = (int(n) for n in input().split())
    weights.append(w)
    values.append(v)

def knapsack_dp(weight_capacity, weights, values):
    """Solve knapsack problem by dynamic programming"""
    N = len(weights)
    dp = [[0] * (weight_capacity + 1) for _ in range(len(weights) + 1)]

    for i in range(N):
        for w in range(weight_capacity + 1):
            if w >= weights[i]:
                dp[i + 1][w] = max(dp[i][w], dp[i][w - weights[i]] + values[i])
            else:
                dp[i + 1][w] = dp[i][w]

    return dp[N][weight_capacity]

print(knapsack_dp(weight_capacity, weights, values))

Submission status: Accepted

Solution code:
n,w=list(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+1)]
dp[0][0] = 0

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

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

Submission status: Accepted

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

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

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

print(max(dp[-1]))

Submission status: Accepted

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

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

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

    print(max(dp))

main()

Submission status: Accepted

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

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

    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            if dp[i] != -1 and dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v

    print(max(dp))

main()

Submission status: Accepted

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

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())
dp=[[0]*(w+1) for _ in range(n)]
l=[0]*n
for i in range(n):
    l[i]=list(map(int,input().split()))
#print(l)
for i in range(w+1):
    if i>=l[0][0]:
        dp[0][i]=l[0][1]
for i in range(w+1):
    for j in range(n-1):
        if i<l[j+1][0]:
            dp[j+1][i]=dp[j][i]
        else:
            dp[j+1][i]=max(dp[j][i-l[j+1][0]]+l[j+1][1],dp[j][i])


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

Submission status: Accepted

Solution code:
# dp[i][w_sum]: i番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値
N, W = map(int, input().split())
items = [tuple(map(int, input().split())) for i in range(N)]

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

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

        # i-1番目の品物を選ぶ場合
        # 重量的に入れられるなら入れてみる
        if w_sum+items[i][0] <= W:
            dp[i+1][w_sum+items[i][0]] = max(dp[i+1][w_sum+items[i][0]],
                                             dp[i][w_sum]+items[i][1])

        # i-1番目の品物を選ばない場合
        dp[i+1][w_sum] = max(dp[i+1][w_sum], dp[i][w_sum])

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

Submission status: Accepted

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

for i in range(1, n+1):
    wi, vi = map(int, input().split())
    for j in range(w+1):
        if wi > j:
            lst[i][j] = lst[i-1][j]
        else:
            lst[i][j] = max(lst[i-1][j], lst[i-1][j-wi] + vi)
print(max(lst[n]))

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

Submission status: Accepted

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

for i in range(n):
    weight, value = map(int,input().split())
    for w in range(max_weight+1):
        if w >= weight:
            dp[i+1][w] = max(dp[i][w-weight] + value, dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
print(dp[n][max_weight])

Submission status: Accepted

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

Submission status: Accepted

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

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,w=map(int,input().split())
    W=[0]*n; V=[0]*n
    for i in range(n):
        a,b=map(int,input().split())
        W[i]=a; V[i]=b
    # dp[i][k] iまでの品物で、重さがk以下
    dp=[[0]*(w+1) for _ in range(n+1)]
    for i in range(1,n+1):
        for k in range(w+1):
            if k-W[i-1]>=0:
                dp[i][k]=max(dp[i-1][k-W[i-1]]+V[i-1],dp[i-1][k])
            else:
                dp[i][k]=dp[i-1][k]
    print(dp[n][w])
resolve()

Submission status: Accepted

Solution code:
"""
ナップサック問題
"""
N,W = map(int, input().split())
dp = [[-1 for i in range(100100)] for j in range(N+1)]
dp[0][0] = 0
for i in range(N):
    w, v = map(int, input().split())
    for j in range(W):
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if dp[i][j] == -1:
            continue
        elif j+w <= W:
            # print("i:{},j:{},value1:{}".format(i,i+j,max(dp[i][j]+v, dp[i][j+w])))
            dp[i+1][j+w] = max(dp[i][j]+v, dp[i][j+w])
            # print(dp[i+1][j+w],i+1,j+w)

print(max(dp[N][:W+1]))

Submission status: Accepted

Solution code:
# D - Knapsack 1 Educational DP Contest / DP
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())
    np.maximum(dp[w:], dp[:-w] + v, out = dp[w:])

ans = dp.max()
print(ans)

Submission status: Accepted

Solution code:
#DP 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):
    w,v=wv[i]
    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],dp[i][j-w]+v)
print(dp[-1][-1])

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,W = LI()
wv = [LI() for _ in range(n)]
dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(n):
    w,v = wv[i]
    for j in range(w):
        dp[i+1][j] = dp[i][j]
    for j in range(W+1):
        if w + j > W:
            break
        dp[i+1][w+j] = max(dp[i][w+j],dp[i][j] + v)
    #print(dp)
print(max(dp[-1]))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
from operator import itemgetter


def branchAndBound(N: int, M: int, V: list, W: list, R: list) -> int:
    def upperbound(w, v, i):
        rest = M - w
        _v = v
        for j in range(i + 1, N):
            if W[j] >= rest:
                rest -= W[j]
                v += V[j]
                _v = v
            else:
                _v += R[j] * rest
                break
        return v, _v

    prov, tmp = upperbound(0, 0, -1)
    h = [(tmp, W[0], V[0] * (W[0] >= M), 0), (upperbound(0, 0, 0)[1], 0, 0, 0)]
    while h:
        _v, w, v, cur = heappop(h)
        if _v > prov or cur == N - 1:
            continue
        nxtw, nxtv = w + W[cur + 1], v + V[cur + 1]
        if nxtw >= M:
            heappush(h, (_v, nxtw, nxtv, cur + 1))
        _prov, ub = upperbound(w, v, cur)
        if _prov < prov:
            prov = _prov
        if ub < prov:
            heappush(h, (ub, w, v, cur + 1))
    return -prov


def main():
    N, M, *L = map(int, open(0).read().split())
    t = [(v, w, v / w) for w, v in zip(*[iter(L)] * 2)]
    t.sort(key=itemgetter(2), reverse=True)
    V, W, R = [], [], []
    for v, w, r in t:
        V += [-v]
        W += [-w]
        R += [r]
    ans = branchAndBound(N, -M, V, W, R)
    print(ans)
    
if __name__=="__main__":main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
def main():
    N,W = map(int,input().split())
    dp = [-1 for _ in range(W+1)]
    dp[W] = 0
    for _ in range(N):
        nm,nv = [int(a) for a in input().split()]
        for j in range(nm,W+1):
            a = nm
            if dp[j] == -1:
                continue
            if dp[j-a] < dp[j] + nv:
                dp[j-a] = dp[j] + nv
    print(max(dp))
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

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 for _ in range(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:
n,w=map(int,input().split())
li=[[int(i) for i in input().split()] for j in range(n)]
 
dp = [[0 for i in range(w+1)] for j in range(n+1)]
 
ans = 0
for i in range(n):
    for j in range(1,w+1):
        if li[i][0] <= j:
            dp[i+1][j]=max(dp[i][j], dp[i][j-li[i][0]]+li[i][1])
        else:
            dp[i+1][j]=dp[i][j]
        ans = max(ans,dp[i+1][j])
print(ans)

Submission status: Accepted

Solution code:
N,W = [int(x) for x in input().split()]
dp = [[0]*(W+1) for _ in range(N+2)]
uv = [[0,0]]+[[int(x) for x in input().split()] for _ in range(N)]
for i in range(N+1):
  for j in range(W+1):
    dp[i+1][j] = max(dp[i+1][j],dp[i][j])
    if uv[i][0]+j<=W:
      dp[i+1][j+uv[i][0]] = max(dp[i][j]+uv[i][1],dp[i+1][j+uv[i][0]])
print(max(dp[N+1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
N , W = map(int, input().split())
goods = np.array([list(map(int , input().split())) for _ in range(N)])
dp = np.zeros((N + 1 , W + 1) , dtype = np.int)

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

Submission status: Accepted

Solution code:
from copy import deepcopy
N, K = [int(i) for i in input().split()]
wvs = [(int(w), int(v)) for w,v in [input().split() for _ in range(N)]]
dp = [0]*(K)
for i, wv in enumerate(wvs):
  w,v = wv
  tmp_dp = deepcopy(dp)
  for j in range(i,K):
    if (j+w) <= K:
      tmp_dp[j+w-1] = max(dp[j+w-1], dp[j-1] + v)
  dp = tmp_dp
print(max(dp))

Submission status: Accepted

Solution code:
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+1)]
for i in range(1, N+1):
    for sum_w in range(1, W + 1):
        if sum_w-wv[i-1][0] >= 0:
            dp[i][sum_w] = max(dp[i-1][sum_w], dp[i-1][sum_w-wv[i-1][0]] + wv[i-1][1])
        else:
            dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])

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

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
ws = [0] * n
vs = [0] * n
for i in range(n):
    ww, vv = map(int, input().split())
    ws[i] = ww
    vs[i] = vv

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

print(dp[n][w])

Submission status: Accepted

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

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


main()

Submission status: Accepted

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

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


main()

Submission status: Accepted

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

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


main()

Submission status: Accepted

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

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
class Solver():
    def __init__(self, N, W, items):
        self.N = N
        self.W = W
        self.items = items

    def solve(self):
        dp = [[0 for _ in range(self.W+1)] for _ in range(self.N+1)]
        for i in range(self.N):
            for w in range(self.W+1):
                if w - self.items[i][0] >= 0:
                    dp[i+1][w] = max(dp[i+1][w], dp[i][w - self.items[i][0]] + self.items[i][1])

                dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])
        return dp[self.N][self.W]


def main():
    N, W = [int(i) for i in input().split()]
    items = [[int(i) for i in input().split()] for _ in range(N)]
    solver = Solver(N, W, items)
    print(solver.solve())


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque

input = sys.stdin.readline

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

def main():
    N, W = map(int, input().split())
    f_inf = float('inf')
    # DP テーブルを初期化　(最小化問題なので INF に初期化)
    MAX_N = 110000
    dp = [0] * (W + 1)


    for _ in range(N):
        w, v = map(int, input().split())
        for sum_w in range(W, w-1, -1):
            a = dp[sum_w - w] + v
            if a > dp[sum_w]:
                dp[sum_w] = a
    print(dp[-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque

input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    f_inf = float('inf')
    # DP テーブルを初期化　(最小化問題なので INF に初期化)
    MAX_N = 110000
    dp = [0] * (W + 1)


    for _ in range(N):
        w, v = map(int, input().split())
        for sum_w in range(W, w-1, -1):
            tv = dp[sum_w - w] + v
            if tv > dp[sum_w]:
                dp[sum_w] = tv
    print(dp[-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    n, w = map(int, input().split())
    dp = [-1] * (w + 1)
    dp[w] = 0
    for i in range(n):
        input_w, input_v = map(int, input().split())
        for i in range(input_w, w + 1):
            if dp[i] == -1:
                continue
            if dp[i - input_w] < dp[i] + input_v:
                dp[i - input_w] = dp[i] + input_v
    print(max(dp))

main()