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:
def MAX(a, b):
    return b + (((((a + ms - b) & ms) >> (K - 1)) * tt) & (ms + a - b))
def MIN(a, b):
    return a - (((((a + ms - b) & ms) >> (K - 1)) * tt) & (ms + a - b))

def tolist(n):
    sx = bin(n)[2:] + "_"
    return [int(sx[-(i+1) * K - 1:-i * K - 1], 2) for i in range((len(sx)+K-2) // K)]

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

ms = int(("1" + "0" * (K - 1)) * (W + 1), 2)
tt = (1 << K - 1) - 1
one = int(("0" * (K - 1) + "1") * (W + 1), 2)

a = 8
b = 39

s = 1 << K - 2 + (W * K)
for _ in range(N):
    w, v = map(int, input().split())
    s = MAX(s, (s >> w * K) + one * v)

print(max(tolist(s)) - (1 << K - 2))

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

print(max(dp[N]))

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:], dp[:-w] + v , dp[w:])
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)]

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

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

Submission status: Accepted

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

w = []
v = []
for _ in range(N):
    wv = list(map(int, input().split()))
    w.append(wv[0])
    v.append(wv[1])

dp = [[0, 0]]
for i in range(1, W+1):
    max_t = dp[i-1][0]
    flag = dp[i-1][1]
    for j in range(N):
        if w[j] > i or dp[i-w[j]][1] & (1 << j):
            continue
        if max_t < dp[i-w[j]][0] + v[j]:
            max_t = dp[i-w[j]][0] + v[j]
            flag = dp[i-w[j]][1] | (1 << j)
    dp += [[max_t, flag]]
print(dp[W][0])

Submission status: Accepted

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

a = [[0] * 2 for i in [0] * n]

for i in range(n):
  a[i] = list(map(int,input().strip().split()))

weight_max = 0
for i in range(n):
  weight_max += a[i][0]

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

for i in range(n):
  for sum_w in range(w+1):
    if sum_w >= a[i][0]:
      dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w-a[i][0]]+a[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 = list(map(int,input().strip().split()))

a = [[0] * 2 for i in [0] * n]

for i in range(n):
  a[i] = list(map(int,input().strip().split()))

weight_max = 0
for i in range(n):
  weight_max += a[i][0]

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

for i in range(n):
  for sum_w in range(w+1):
    if sum_w >= a[i][0]:
      dp[i+1][sum_w] = max(dp[i][sum_w], dp[i][sum_w-a[i][0]]+a[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())
wv = [list(map(int, input().split())) for _ in range(N)]

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

for w in range(1, W+1):
    for n in range(N):
        Wi = wv[n][0]
        Vi = wv[n][1]
        if Wi <= w:
            dp[n+1][w] = max(dp[n][w], dp[n][w-Wi] + Vi)
        dp[n+1][w] = max(dp[n][w], dp[n+1][w])

print(dp[N][W])

Submission status: Accepted

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

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

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

for i in range(1,N+1):
  for w_now in range(1,W+1):
    if w_now - ws[i-1] >= 0:
      dp_table[i][w_now] = max( dp_table[i-1][w_now], dp_table[ i-1][w_now-ws[i-1] ] + vs[i-1] )
    else:
      dp_table[i][w_now] = dp_table[i-1][w_now]
print(int(dp_table[-1][-1]))

Submission status: Accepted

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

import sys

def main2():
    n,k = map(int,(input().split()))
    items=[list(map(int,input().split())) for _ in range(n)]
    dp = [[0 for _ in range(k+1)] for _ in range(n)]
    for i in range(n):
        for j in range(k+1):
            if i==0 and j>=items[0][0]:
                dp[0][j]=items[0][1]
            elif i>0 and j>=items[i][0]:
                dp[i][j]=max(dp[i-1][j],items[i][1]+dp[i-1][j-items[i][0]])
            elif j < items[i][0] and i > 0:
                dp[i][j]=dp[i-1][j]
    print (dp[-1][-1])

if __name__ == "__main__":
    main2()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    N, W = map(int, readline().split())
    INF = int(1e5)+100
    weight = [0 for _ in range(110)]
    value = [0 for _ in range(110)] 
    for i in range(N):
        w, v = map(int, readline().split())
        weight[i] = w
        value[i] = v
    dp = [[0 for _ in range(INF)] for _ in range(110)]
    for i in range(N):
        for sum_w in range(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+1][sum_w], dp[i][sum_w])
    print(dp[N][W])
if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

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

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

    return dp[-1][-1]


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
def chmax(dp, i, x):
  if dp[i] < x:
    dp[i] = x
    return True
  return False

n, W = map(int, input().split())
dp = [-10**9]*(W+1)
dp[0] = 0
for i in range(n):
  w, v = map(int, input().split())
  for i in range(W-w,-1,-1):
    chmax(dp, i+w, dp[i] + v) 
print(max(dp))

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

print(dp[W])

Submission status: Accepted

Solution code:
import sys,io
from functools import lru_cache
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())
N,W=reads()
weight,value=[0]*N,[0]*N
for i in range(N):
    weight[i],value[i]=reads()
dp=[[ 0 for _ in  range(W+1) ] for _ in range(N+1)]
for i in range(N):
  for k in range(W+1):
    if (k >= weight[i]) :dp[i+1][k] = max(dp[i][k-weight[i]] + value[i], dp[i][k])
    else :dp[i+1][k] = dp[i][k]
print("{}".format(dp[N][W]))

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
a = list()
a.append([0, 0])
inf = float('inf')
for _ in range(N):
  x = list(map(int, input().split()))
  a.append(x)
dp = [[-inf for _ in range(W+1)]for _ in range(N+1)]
# dp[i][w] : i番目までで、wを超えないように選んだ時の価値の最大値
for w in range(W+1):
  dp[0][w] = 0
for i in range(N):
  for w in range(W+1):
    # i+1番目を選ぶかもしれないとき
    if w - a[i+1][0] >= 0:
      dp[i+1][w] = max(dp[i][w], dp[i][w-a[i+1][0]] + a[i+1][1])
    # i+1番目を選ばないとき
    else:
      dp[i+1][w] = dp[i][w]
print(dp[N][W])

Submission status: Accepted

Solution code:
l=input().split()
n=int(l[0])
W=int(l[1])
lweight=[]
lvalue=[]
for i in range(n):
	l=input().split()
	u=int(l[0])
	v=int(l[1])
	lweight.append(u)
	lvalue.append(v)
dp=[[0 for i in range(W+1)] for i in range(n+1)]
for i in range(n+1):
	dp[i][0]=0
for j in range(W+1):
	dp[0][j]=0
for i in range(1,n+1):
	for j in range(1,W+1):
		if(j>=lweight[i-1]):
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-lweight[i-1]]+lvalue[i-1])
		else:
			dp[i][j]=dp[i-1][j]
print(dp[n][W])

Submission status: Accepted

Solution code:
import numpy as np
N,W = map(int,input().split())
l = [list(map(int,input().split()))for i in range(N)]
dp = np.zeros(shape=(N,W + 1),dtype = int)
for i in range(l[0][0],W + 1):
    dp[0][i] = l[0][1]
for i in range(1,N):
    weight = l[i][0]
    value = l[i][1]
    dp[i][:weight] = dp[i - 1][:weight]
    dp[i][weight:] = np.maximum(dp[i - 1][weight:], value + dp[i - 1][:-weight])
print(dp[N - 1][W])

Submission status: Accepted

Solution code:
def read_int():
    return int(input().strip())
 
 
def read_ints():
    return list(map(int, input().strip().split(' ')))
 
 
def solve():
    """
    OPT[N][W] = maximum value obtained with first N items and weights up to W
    OPT[N][W] = max(OPT[N-1][W-w[N]]+v[N], OPT[N-1][W])
    OPT[0][0] = 0
    """
    N, W = read_ints()
    w, v = [], []
    for _ in range(N):
        w0, v0 = read_ints()
        w.append(w0)
        v.append(v0)
    OPT = [[0]*(W+1) for _ in range(N+1)]
    for i in range(1,N+1):
        for j in range(1,W+1):
            OPT[i][j]=OPT[i-1][j]
            if j-w[i-1]>=0:
                OPT[i][j]=max(OPT[i][j],OPT[i-1][j-w[i-1]]+v[i-1])
    return OPT[-1][-1]
if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
import numpy as np

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

items = [tuple(map(int, input().split(' '))) for _ in range(N)]

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

for i in range(N):
    weight = items[i][0]
    value = items[i][1]
    dp[i + 1][:weight] = dp[i][:weight]
    dp[i + 1][weight:] = np.maximum(dp[i][weight:], value + dp[i][:-weight])

print(dp[N][W])

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    OPT[N][W] = maximum value obtained with first N items and weights up to W
    OPT[N][W] = max(OPT[N-1][W-w[N]]+v[N], OPT[N-1][W])
    OPT[0][0] = 0
    """
    N, W = read_ints()
    w, v = [], []
    for _ in range(N):
        w0, v0 = read_ints()
        w.append(w0)
        v.append(v0)
    OPT = [[0]*(W+1) for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, W+1):
            OPT[i][j] = OPT[i-1][j]
            if j-w[i-1] >= 0:
                OPT[i][j] = max(OPT[i][j], OPT[i-1][j-w[i-1]]+v[i-1])
    return OPT[-1][-1]


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import bisect
from queue import Queue
from collections import deque

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

nap = [[int(i) for i in input().split()] for j in range(n)]

dp = [[0 for _ in range(100001)] for _ in range(101)]

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

print(dp[n][w])

Submission status: Accepted

Solution code:
import sys
rl = sys.stdin.readline
def a():
    N, W = map(int, rl().split())
    dp = [-1]*(W+1)
    dp[0] = 0
    for _ in range(N):
        w, v = map(int, rl().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))
a()

Submission status: Accepted

Solution code:
import sys
# import numpy as np
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))
# import profile

def solve():
	n, w = read(); 
	dp = [[0 for i in range(w+1)] for j in range(3)]
	w_v_list = [read() for i in range(n)]
	# for i in dp:print(*i)
	# print("\n")
	# print(w_v_list)
	for i in range(n):
		for j in range(w+1):
			elem_w, elem_v = w_v_list[i]
			if elem_w <= j:
				dp[i%3][j] = max(elem_v + dp[(i-1)%3][j - elem_w], dp[i%3][j-1], dp[(i-1)%3][j])
				# w_v_list[i][1] = 0
			else:
				dp[i%3][j] = max(dp[i%3][j-1], dp[(i-1)%3][j])
		for k in range(w+1):
			dp[(i+1)%3][k] = 0
		# for i in dp:print(*i)
		# print("\n")
	print(dp[(n-1)%3][w])




if __name__ == "__main__":
	solve()

Submission status: Accepted

Solution code:
import sys
# import numpy as np
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))
# import profile

def solve():
	n, w = read(); 
	dp = [[0 for i in range(w+1)] for j in range(3)]
	w_v_list = [read() for i in range(n)]
	# for i in dp:print(*i)
	# print("\n")
	# print(w_v_list)
	for i in range(n):
		for j in range(w+1):
			elem_w, elem_v = w_v_list[i]
			if elem_w <= j:
				dp[i%3][j] = max(elem_v + dp[(i-1)%3][j - elem_w], dp[i%3][j-1], dp[(i-1)%3][j])
				# w_v_list[i][1] = 0
			else:
				dp[i%3][j] = max(dp[i%3][j-1], dp[(i-1)%3][j])
		dp[(i+1)%3] = [0]*(w+1)
		# for i in dp:print(*i)
		# print("\n")
	print(dp[(n-1)%3][w])




if __name__ == "__main__":
	solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
ans = 0
n, w = map(int, input().split())
lst = [[0,0]]
for _ in range(n):
    a, b = map(int, input().split())
    lst.append([a,b])
dp = [[0] * (w+1) for _ in range(n+1)]

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

Submission status: Accepted

Solution code:
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())
    dp = np.concatenate([dp[:w], np.fmax(dp[w:], dp[:W+1-w]+v)])
    #print(dp)
    
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, W = map(int, input().split())
    dp = [-INF] * (W + 1)
    dp[0] = 0
    for _ in range(n):
        w, v = map(int, input().split())
        for w0 in range(W, -1, -1):
            if dp[w0] == INF:
                continue
            if w + w0 <= W:
                dp[w + w0] = max(dp[w + w0], dp[w0] + v)
    print(max(dp))
resolve()

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

def resolve():
    return 

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

print(dp[N][W])

Submission status: Accepted

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline
    # 整数 1 つ
    # n = int(input())
    # 整数複数個
    n, w = map(int, input().split())
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    # N = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    A = [list(map(int, input().split())) for i in range(n)]

    Knap = [[0] * (w+1) for _ in range(n+1)]
#    Knap = [[0] * (110) for _ in range(10**5+10)]

    for i in range(n):
        for k in range(w+1):
            if k + A[i][0] <= w:
#                point = k + A[i][0]
                Knap[i+1][k+A[i][0]] = max(Knap[i+1][k+A[i][0]], (Knap[i][k] + A[i][1]))

            Knap[i+1][k] = max(Knap[i][k], Knap[i+1][k])

#    knapmax = 0
    # for i in range(n):
    #     knapmax = max(knapmax, max(Knap[i+1]))
    print(Knap[n][w])
#    print(*Knap, sep="\n")
resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
N,W=list(map(int,input().split()))
DP=np.zeros(W+1,dtype=int)
for i in range(N):
    w,v=list(map(int,input().split()))
    a=DP[:-w]+v
    b=DP[w:]
    DP[w:]=np.fmax(a,b)
print(DP[-1])

Submission status: Accepted

Solution code:
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)] #1_indexed
for i in range(1,N+1):
    w,v = wv[i-1]
    for j in range(W+1):
        if j-w>=0:
            dp[i][j] = max(dp[i][j],dp[i-1][j-w]+v)
        dp[i][j] = max(dp[i][j],dp[i-1][j])
print(dp[-1][-1])

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
X = [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, W+1):
    DP[0][i] = float("-inf")
for i in range(1, N+1):
    for j in range(W+1):
        if j-X[i-1][0] >= 0:
            DP[i][j] = max(DP[i-1][j], DP[i-1][j-X[i-1][0]]+X[i-1][1])
        else:
            DP[i][j] = DP[i-1][j]
print(max(DP[N]))
                    
#最後から2行目。
#ありえないのは-INFで選ばれないように

Submission status: Accepted

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

for i 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] >= 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[N][W])

Submission status: Accepted

Solution code:
import numpy as np
N,W=list(map(int,input().split()))
DP=np.zeros(W+1)

for i in range(N):
    w,v=list(map(int,input().split()))
    a=DP[:-w]+v
    b=DP[w:]
    c=np.maximum(a,b)
    DP[w:]=c



print(int(DP[-1]))
# for i in DP:
#     print(i)

Submission status: Accepted

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

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

        if j-w<0:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])
        else:
            dp[i][j] = max(dp[i-1][j-w]+v,dp[i-1][j])

print(max(max(dp)))

Submission status: Accepted

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

def solve_knapsack(capacity):
    # basic checks
 
    
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit
    dp = [0]*(W + 1)
    

    for i in range(0, N):
        weights,profits = map(int,input().split())
        for c in range(capacity, weights-1, -1):
            tmp = profits + dp[c - weights]
            if tmp > dp[c]: dp[c] = tmp
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
    
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

Submission status: Accepted

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

def solve_knapsack(capacity):
    # basic checks
 
    
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit
    dp = [0]*(W + 1)
    weights, profits = [0]*(N+1), [0]*(N+1)
    for i in range(0, N):
        weights[i],profits[i] = map(int,input().split())
    

    for i in range(0, N):
        for c in range(capacity, weights[i]-1, -1):
            tmp = profits[i] + dp[c - weights[i]]
            if tmp > dp[c]: dp[c] = tmp
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
    
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

Submission status: Accepted

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

def solve_knapsack(capacity):
    # basic checks
 
    
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit
    dp = [0]*(W + 1)
    weights, profits = [0]*(N+1), [0]*(N+1)
    

    for i in range(0, N):
        weights[i],profits[i] = map(int,input().split())
        for c in range(capacity, weights[i]-1, -1):
            tmp = profits[i] + dp[c - weights[i]]
            if tmp > dp[c]: dp[c] = tmp
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
    
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

Submission status: Accepted

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

def solve_knapsack(capacity):
    # basic checks
 
    
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit
    dp = [0]*(W + 1)
    weights, profits = [0]*(N+1), [0]*(N+1)
    

    for i in range(0, N):
        weights,profits = map(int,input().split())
        for c in range(capacity, weights-1, -1):
            tmp = profits + dp[c - weights]
            if tmp > dp[c]: dp[c] = tmp
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
    
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

Submission status: Accepted

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

def solve_knapsack(capacity):
    # basic checks
 
    
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit

    for i in range(0, N):
        weights,profits = map(int,input().split())
        for c in range(capacity, weights-1, -1):
            tmp = profits + dp[c - weights]
            if tmp > dp[c]: dp[c] = tmp
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

Submission status: Accepted

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

def solve_knapsack(capacity):
    # basic checks
 
    dp = [0]*(capacity + 1)
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit

    for i in range(0, N):
        weights,profits = map(int,input().split())
        for c in range(capacity, weights-1, -1):
            tmp = profits + dp[c - weights]
            if tmp > dp[c]: dp[c] = tmp
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
 
n,w=map(int,input().split())
dp=[0]*(w+1)
 
def ans(n,w):
  for _ in range(n):
    c,p=map(int,input().split())
    for j in range(w,c-1,-1):
      tmp=dp[j-c]+p
      if dp[j]<tmp:
        dp[j]=tmp
  return dp[-1]
print(ans(n,w))

Submission status: Accepted

Solution code:
import sys
read = lambda: sys.stdin.readline().rstrip()
 
N,W=map(int,read().split())
 
def solve_knapsack(capacity):
    # basic checks
 
    dp = [0]*(capacity + 1)
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit
 
    for i in range(0, N):
        weights,profits = map(int,read().split())
        for c in range(capacity, weights-1, -1):
            tmp = profits + dp[c - weights]
            if tmp > dp[c]: dp[c] = tmp
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

Submission status: Accepted

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

def solve_knapsack(capacity):
    # basic checks
 
    dp = [0]*(capacity + 1)
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit

    for i in range(0, N):
        weights,profits = map(int,input().split())
        for c in range(capacity, weights-1, -1):
            tmp = profits + dp[c - weights]
            if tmp > dp[c]: dp[c] = tmp
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
res = solve_knapsack(W)
print(res)

Submission status: Accepted

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


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

def solve_knapsack(capacity):
    # basic checks
 
    dp = [0]*(capacity + 1)
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit

    for i in range(0, N):
        weights,profits = map(int,input().split())
        for c in range(capacity, weights-1, -1):
            tmp = profits + dp[c - weights]
            if tmp > dp[c]: dp[c] = tmp
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
def main():
  n, w = [int(e) for e in input().split()]
  t = [-1 for i in range(w + 1)]
  t[w] = 0
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(nw, w + 1):
      if t[i] == -1:
        continue
      if t[i - nw] < t[i] + nv:
        t[i - nw] = t[i] + nv
  print(max(t))
main()

Submission status: Accepted

Solution code:
def knapsack(N, C, weights, values):
    dp = [[0 for _ in range(N + 1)] for _ in range(C + 1)]
    for i in range(1, C + 1):
        for j in range(1, N + 1):
            if weights[j - 1] <= i:
                dp[i][j] = max(dp[i][j - 1], values[j - 1] + dp[i - weights[j - 1]][j - 1])
            else:
                dp[i][j] = dp[i][j - 1]
    return dp[C][N]
 
 
if __name__ == '__main__':
    n, c = list(map(int, input().split()))
    weights = [0] * n
    values = [0] * n
    for i in range(n):
        weights[i], values[i] = map(int, input().split())
    print(knapsack(n, c, weights, values))

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 以下となるように選んだときの、
#価値の総和の最大値
for i in range(N):
    for j in range(W+1):
        if j - w[i] >= 0:
            #dp[i+1][j] = max(dp[i+1][j], dp[i][j-w[i]] + v[i])
            dp[i+1][j] = dp[i][j - w[i]] + v[i]

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

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 以下となるように選んだときの、
#価値の総和の最大値
for i in range(N):
    for j in range(W+1):
        if j - w[i] >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-w[i]] + v[i])
        
        dp[i+1][j] = max(dp[i][j], dp[i+1][j])

print(dp[N][W])

Submission status: Accepted

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
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())
    a = dp[:-w] + v
    b = dp[w:]
    m = np.maximum(a,b)
    dp[w:] = m

print(dp[-1])