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

print(max(dp[N]))

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
val=[]
we=[]
for i in range(n):
  a,b=map(int,input().split())
  we.append(a)
  val.append(b)
dp=[[0 for _ in range(w+1)]for _ in range(n+1)]
for i in range(n+1):
  for j in range(w+1):
    if i==0 or j==0:
      continue
    if we[i-1]>j:
      dp[i][j]=dp[i-1][j]
    else:
      dp[i][j]=max(dp[i-1][j],val[i-1]+dp[i-1][j-we[i-1]])
print(dp[n][w])

Submission status: Accepted

Solution code:
import sys
import numpy as np

n, k = map(int, sys.stdin.readline().split())

dp = np.zeros((n+1, k+1))

for i in range(1,n+1):
    w, v = map(int, sys.stdin.readline().split())
    dp[i] = dp[i-1]
    dp[i][w:] = np.maximum(dp[i-1][:-w]+v, dp[i-1][w:])

print(int(np.max(dp[n])))

Submission status: Accepted

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

#dp = [[None for i in range(W+1)] for j in range(n+1)]
dp = [[0 for i in range(W+1)] for j in range(n+1)]

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

def knap(i, j):
    if dp[i][j] is not None:
        return dp[i][j]

    res = 0

    if i == n:
       	res = 0
    elif j < w[i]:
        res = knap(i+1, j)
    else:
        res = max(knap(i+1, j), knap(i+1, j-w[i]) + v[i])

    dp[i][j] = res
    return dp[i][j]

for i in reversed(range(n)):
    for j in range(W+1):
#        res = 0
        # if i == n-1:
        #     res = 0
        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(knap(0, W))
print(dp[0][W])

Submission status: Accepted

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

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

Submission status: Accepted

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

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

def maxv(i, v):
    if i >= 0:
        if v > DP[i]:
            DP[i] = v

for w, v in (map(int, input().split()) for _ in range(N)):
    for i in range(1, W+1):
        if DP[i] >= 0:
            maxv(i-w, DP[i]+v)
            maxv(0, DP[i-w])

print(DP[0])

Submission status: Accepted

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

wei = []
val = []

for i in range(n):
    x, y = map(int, input().split())
    wei.append(x)
    val.append(y)

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

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
def knapsack(n,W,v,w):
    dp=[[0 for i in range(W+1)]for j 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(v[i-1]<=j):
                dp[i][j] = max(w[i-1] + dp[i-1][j-v[i-1]],dp[i-1][j]) #2 cases in max bracket if (i-1)th element will count or will not count.
            else:
                dp[i][j]=dp[i-1][j]
    # print(dp)
    return dp[n][W] 



n,W=map(int,input().split())
v=[]
w=[]
for i in range(n):
    a,b=map(int,input().split())
    v.append(a)
    w.append(b)
print(knapsack(n,W,v,w))

    # l.append(list(map(int,input().split())))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def main():
	N, W = map(int, input().split())
	wv = []
	for i in range(N):
		w, v = map(int, input().split())
		if w <= W:
			wv.append((w,v))
		
	DP = [[0 for _ in range(100001)] for _ in range(N)]
	
	for i, val in enumerate(wv):
		w, v = val
		if i == 0:
			DP[i][w] = v
			continue
			
		for j in range(W):
			DP[i][j] = max(DP[i-1][j], DP[i][j])
			
			if j+w <= W:
				DP[i][j+w] = max(DP[i-1][j] + v, DP[i][j+w])
			
	print(max(DP[N-1]))
	
if __name__ == "__main__":
	main()

Submission status: Accepted

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

print(max(dp[n]))

Submission status: Accepted

Solution code:
n,wmax = 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]*(wmax+1)
for weight,value in zip(w,v):
    for i in reversed(range(weight,wmax+1)):
        dp[i] = max(dp[i],dp[i-weight]+value)

print(max(dp))

Submission status: Accepted

Solution code:
# Educational DP Contest D-knapsack

def knapsack(N, W, wv):
    # initialize
    dp = [list(0 for _ in range(W+1)) for j in range(N+1)]
    
    # DP
    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]
    return dp[N][W]

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

Submission status: Accepted

Solution code:
def dp():
    n,w = map(int,input().split())
    lis = (map(int,input().split()) for i in range(n))
    
    dpp = [0] * (w + 1)
    for weight, value in lis:
        for j in range(w,weight-1,-1):
            dp = dpp[j-weight] + value
            if dpp[j] < dp:
                dpp[j] = dp
    return max(dpp)
print(dp())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#dp4 #Knapsack 1

def d():
    n,W = map(int,input().split())
    #縦:品物　横:重さ
    dp = [[0]*(W+1) for _ in range(n+1)]
    #dp[i][j]:i個の品物があり、容量jのときの価値の最大値
    wv = [list(map(int,input().split())) for _ in range(n)]

    for i in range(1,n+1):
        for j in range(1,W+1):
            #i番目の品物を用いるとき
            #i番目の品物の重さより容量が小さいとき(i番目の品物を使えないとき)
            if j < wv[i-1][0]:
                #i-1番目の品物までを用いたときと価値は同じ
                dp[i][j] = dp[i-1][j]
            else:#i番目の品物を使えるとき
                #i番目の品物を用いるか用いないか
                #i-1番目までの品物を用いたときの価値とi-1番目までの品物にi番目の品物を加えたときを比較
                dp[i][j] = max(dp[i-1][j],dp[i-1][j - wv[i-1][0]] + wv[i-1][1])
    print(dp[n][W])

if __name__ == '__main__':
    d()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
def factorial(n):
    if (n==0) or (n==1):
        return 1
    ret = 1
    for i in range(2, n+1):
        ret *= i
    return ret
def combination(n, k):
    return factorial(n)//factorial(k)//factorial(n-k)
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N, W = LI()
wv = LIR(N)

dp = [[0]*(W+1) for i 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[N][W])

Submission status: Accepted

Solution code:
N,W=list(map(int,input().strip().split(" ")))
items=[]
for _ in range(N):
    w,v=list(map(int,input().strip().split(" ")))
    items+=[(w,v)]

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

Submission status: Accepted

Solution code:
# @author 

import sys

class DKnapsack1:
    def solve(self):
        n, W = [int(_) for _ in input().split()]
        w = [0] * (n + 1)
        v = [0] * (n + 1)
        for i in range(1, n + 1):
            w[i], v[i] = [int(_) for _ in input().split()]

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

        for we in range(W + 1):
            dp[we][0] = 0
            for k in range(1, n + 1):
                dp[we][k] = dp[we][k - 1]
                if w[k] <= we:
                    dp[we][k] = max(dp[we][k], dp[we - w[k]][k - 1] + v[k])

        print(dp[W][n])

solver = DKnapsack1()
input = sys.stdin.readline

solver.solve()

Submission status: Accepted

Solution code:
inf = float('inf')

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

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

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]

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

Submission status: Accepted

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

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

dp = [[0]*(W+1) for _ in range(N)]
# dp[i][ws] : i番目までの品物から総重量がwsを超えないように選んだ時の総価値の最大値

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

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

print(dp[N-1][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:
"D Knapsack 1"
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:])  # dp[:-w]はまだ重さwのものが入るナップサックの状態
    # outは戻り値を格納する配列を指定できる


print(dp[-1])


"""
dp[:-w]は後ろからw個より前の要素、つまり（N-w）個
dp[w:]は前からw個より後ろの要素、つまり（N-w）個
よって形状が一致する
"""

"""
dp[:-w]は今見ている重さw、価値vの荷物を入れることのできる状態のナップサック
dp[:-w]+vをすることで、今見ている荷物を入れた時の価値の総和になる。
今、重さw、価値vの荷物を入れたナップサックと、dp[w:]を比較する。
それぞれの要素について大きい方が新しい要素となり、out=dp[w:]によって上書きされる。
maximumが返すのはnp配列。形状は比較対象となっている配列の形状と一致する
"""

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
weight = []
value = []
for _ in range(N):
    w_tmp, v_tmp = map(int, input().split())
    weight.append(w_tmp)
    value.append(v_tmp)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def resolve():
    (N, W) = list(map(int, input().split(" ")))
    wvs = [[None, None]]
    wvs.extend([list(map(int, input().split(" "))) for _ in range(N)])
    dps = [[0] * (W+1) for _ in range(N+1)]

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

    print(dps[N][W])

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

for i in range(1, N+1):
    for w in range(maxW+1):
        WV[i][w] = max(WV[i-1][w], WV[i][w])
        nw = w + W[i]
        if nw <= maxW:
            WV[i][nw] = WV[i-1][w] + V[i]

print(max(WV[-1]))

Submission status: Accepted

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

dp = [[None] * (10**5 + 1) for _ in range(100 + 1)]
# def dfs(weight=0, depth=N - 1):
#     if dp[depth][weight] is not None:
#         return dp[depth][weight]
#
#     if depth == -1:
#         dp[depth][weight] = 0
#         return 0
#
#     if weight + ws[depth] <= W:
#         result = max(dfs(weight, depth - 1), dfs(weight + ws[depth], depth - 1) + vs[depth])
#     else:
#         result = dfs(weight, depth - 1)
#     dp[depth][weight] = result
#     return result
#
# print(dfs())

dp[-1] = [0] * len(dp[-1])
for depth in range(0, N):
    for weight in range(10**5 + 1):
        v = dp[depth - 1][weight]
        if weight + ws[depth] <= W:
            dp[depth][weight] = max(v, dp[depth - 1][weight + ws[depth]] + vs[depth])
        else:
            dp[depth][weight] = v

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
# dp[i][w] : i個目の時の重さwの最大値
dp = [[0] * 100010 for _ in range(N+1)]
for i in range(N):
    w_i, v_i = map(int, input().split())
    for w in range(W+1):
        if w >= w_i:
            dp[i+1][w] = max(dp[i][w-w_i]+v_i, dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]

print(dp[N][W])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
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)]
dp[0][w[0]] = v[0]

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

ans = 0

for j in range(W + 1):
    if dp[-1][j] > ans:
        ans = dp[-1][j]

print(ans)

Submission status: Accepted

Solution code:
# D-Knapsack 1
N,W = map(int,input().split())
Weight = [0 for _ in range(N)]
Value = [0 for _ in range(N)]
for i in range(N):
    Weight[i],Value[i] = map(int,input().split())

# dp[i+1][w]:= i番目までの品物の中から重さがwを超えないように選んだときの、価値の総和の最大値
dp = [[0 for i in range(W+1)] for j in range(N+1)]

for i in range(N):
    # あらゆる合計重量sum_wに対して品物iを入れるべきか計算する
    for sum_w in range(W+1):
        # i番目を選ぶ場合
        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])

# for d in dp:
#     print(d)

print(dp[N][W])

Submission status: Accepted

Solution code:
# D-Knapsack 1
N,W = map(int,input().split())
Weight = [0 for _ in range(N)]
Value = [0 for _ in range(N)]
for i in range(N):
    Weight[i],Value[i] = map(int,input().split())

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

for i in range(N):
    # あらゆる合計重量sum_wに対して品物iを入れるべきか計算する
    for sum_w in range(W+1):
        # i番目を選ぶ場合
        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])

# for d in dp:
#     print(d)

print(dp[N][W])

Submission status: Accepted

Solution code:
# D-Knapsack 1
N,W = map(int,input().split())
Weight = [0 for _ in range(N)]
Value = [0 for _ in range(N)]
for i in range(N):
    Weight[i],Value[i] = map(int,input().split())

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

for i in range(N):
    # あらゆる合計重量sum_wに対して品物iを入れるべきか計算する
    for sum_w in range(W+1):
        # i番目を選ぶ場合
        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(dp[N][W])

Submission status: Accepted

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

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

# print(wv)

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

print(dp[N][W])

Submission status: Accepted

Solution code:
import sys

n, w = [int(x) for x in input().split(" ")]

wv_list = []

for i in range(n):
  wv_list.append([int(x) for x in input().split(" ")])

dp = [[0 for y in range(w+2)] for x in range(n+1)]

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

Submission status: Accepted

Solution code:
def LI(): return [int(x) for x in input().split()]
def II(): return int(input())

N,W=LI()
LIS=[tuple(LI()) for _ in range(N)]

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

for i,(w,v) in enumerate(LIS, 1):
    for wb in range(0, W+1):
        DP[i][wb] = DP[i-1][wb]
        if wb >= w :
            DP[i][wb] = max(DP[i][wb], DP[i-1][wb-w]+v)

print(DP[N][W])

Submission status: Accepted

Solution code:
def LI(): return [int(x) for x in input().split()]
def II(): return int(input())

N,W=LI()
LIS=[tuple(LI()) for _ in range(N)]

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

for i,(w,v) in enumerate(LIS, 1):
    for wb in range(0, W+1):
        DP[i][wb] = DP[i-1][wb]
        if wb >= w :
            DP[i][wb] = max(DP[i][wb], DP[i-1][wb-w]+v)
# for lis in DP:
#     print(lis)

print(DP[N][W])

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
w,v=[],[]
dp=[[0]*(W+1) for i in range(n+1)]
for i in range(n):
    wi,vi=map(int,input().split())
    w.append(wi)
    v.append(vi)
for i in range(n):
    for w_sum in range(1,W+1):
        if w_sum - w[i]>=0:
            dp[i+1][w_sum]=max(dp[i][w_sum],dp[i][w_sum - w[i]]+v[i])
        else:
            dp[i+1][w_sum]=dp[i][w_sum]
print(dp[-1][-1])

Submission status: Accepted

Solution code:
from subprocess import*
call(('pypy3','-c',"""
I=lambda:list(map(int,input().split()))
n,W=I()
g=[0]+[I()for _ in range(n)]
dp=[[0]*-~W for _ in range(n+1)]
for i in range(1,n+1):
    t=g[i]
    for j in range(W+1):
        if j-t[0]>=0:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[0]]+t[1])
        else:
            dp[i][j]=dp[i-1][j]
print(max(dp[-1]))
"""))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

N,W = map(int,input().split())
wv_l= []
for i in range(N):
    wv_l.append(list(map(int,input().split())))
DP = [[0]*(W+1) for i in range(N+1)]

for i in range(N):
    for sum_w in range(W+1):
#        print(DP)
#        print(i,sum_w)
        if sum_w-wv_l[i][0] >= 0:
            DP[i+1][sum_w] = max(DP[i+1][sum_w],DP[i][sum_w-wv_l[i][0]]+wv_l[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())
#i個目の品物までで重さw以下のときの価値の最大値 
dp = [[0]*(W+1) for _ in range(N+1)]
"""
dp[i, wi:W+1] = max(i番目の重さwiの品物を入れた場合, 入れなかった場合)
         = np.max(dp[i-1, :W-wi+1] + v, dp[i-1, wi:W+1])
"""

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

import numpy as np
ndp = np.zeros(W+1,dtype= np.int64)

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

Submission status: Accepted

Solution code:
n,W=map(int, input().split())
a=[]
for _ in range(n):
    w,v=map(int, input().split())
    a.append((w,v))
dp=[[0 for j in range(W+1)] for i in range(n+1)] # dp[n][w] = max value using up to n-th items and weigh = w

for i in range(1,n+1):
    w,v=a.pop()
    for j in range(W+1):
        if j-w>=0:
            dp[i][j]=max(
                dp[i-1][j-w]+v # use j-th item (w,v)
                ,dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]

print(max(dp[n]))

Submission status: Accepted

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


main()

Submission status: Accepted

Solution code:
def main():
    N, W = map(int, input().split())
    WV = []
    for _ in range(N):
        w, v = map(int, input().split())
        WV.append((w, v))
    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])


main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np

N, W = map(int, input().split())
items = []
for _ in range(N):
    items.append(tuple(map(int, input().split())))
dp = np.array([[0 for j in range(W+1)] for _ in range(N+1)])
for i in range(1, N+1):
    w, v = items[i-1]
    dp[i, :w] = dp[i-1, :w]
    dp[i, w:] = np.maximum(dp[i-1, :-w] + v, dp[i-1, w:])
print(dp[N, W])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[0] * (W + 1) for _ in range(N + 1)]

    for i, (cw, cv) in enumerate(zip(w, v)):
        for j in range(W + 1):
            dp[i+1][j] = dp[i][j]
            if 0 <= j - cw :
                dp[i+1][j] = max(dp[i+1][j], dp[i][j - cw] + cv)
    return max(dp[-1])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    result = solve(N, W, w, v)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
w=[]
v=[]
for i in range(N):
    w_,v_=map(int,input().split())
    w.append(w_)
    v.append(v_)
INF=10**9
dp=[[0]*(W+1) for i in range(N+1)]#dp[i+1][j] i個目までで容量jのときの最大の価値
#dp[i+1][w]:=max(dp[i][w-wi],dp[i][w])加えるか加えないか
for i in range(N):
    for j in range(1,W+1):
        if j-w[i]>=0:
            dp[i+1][j]=max(dp[i][j-w[i]]+v[i],dp[i+1][j])
        dp[i+1][j]=max(dp[i+1][j],dp[i][j])
ans=0
for j in range(W+1):
    ans=max(ans,dp[N][j])
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

N,W = [int(i) for i in input().split()]
H = [[int(i) for i in input().split()] for _ in range(N)]

dp = [[0]*(W+1) for _ in range(N)]
for i in range(N):
    dp[i][H[i][0]] = H[i][1]
    dp[i] = list(accumulate(dp[i]))

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

print(dp[-1][-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 i in range(N)]

wv.sort()
wv.reverse()

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

for i, x in enumerate(wv,1):
    w = x[0]
    v = x[1]
    for j in range(w,W+1):
        dp[i][j] = max(dp[i-1][j],dp[i-1][j-w]+v)
        
print(dp[N][W])

Submission status: Accepted

Solution code:
import sys
from collections import Counter
N, W = map(int, input().split())

dp = Counter()
dp[0] = 0

for _ in range(N):
    w, v = map(int, sys.stdin.readline().split())
    for k, x in dp.copy().items():
        if k + w <= W:
            dp[k + w] = max(dp[k + w], x + v)

print(max(dp.values()))