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:
######################################################
############Created by Devesh Kumar###################
#############devesh1102@gmail.com####################
##########For CodeForces(Devesh1102)#################
#####################2020#############################
######################################################
import sys
input = sys.stdin.readline

# import sys
import heapq 
import copy
import math
import decimal
# import sys.stdout.flush as flush
# from decimal import *
#heapq.heapify(li) 
#
#heapq.heappush(li,4) 
#
#heapq.heappop(li)
#
# &	Bitwise AND Operator	10 & 7 = 2
# |	Bitwise OR Operator	10 | 7 = 15
# ^	Bitwise XOR Operator	10 ^ 7 = 13
 
# <<	Bitwise Left Shift operator	10<<2 = 40
# >>	Bitwise Right Shift Operator
# '''############ ---- Input Functions ---- #######Start#####'''
 

def inp():
	return(int(input()))
def inlt(): 
	return(list(map(int,input().split())))
def insr():
	s = input()
	return(list(s[:len(s) - 1]))
def insr2():
	s = input()
	return((s[:len(s) - 1]))
def invr():
	return(map(int,input().split()))
 ############ ---- Input Functions ---- #######End
 # #####   

def pr_list(a):
	print(*a, sep=" ")
def main():
	# tests =  inp()
	tests = 1
	mod = 998244353
	limit = 10**18
	ans = 0
	for test in range(tests):
		[n,w] = inlt()
		val = []
		for i in range(n):
			a = inlt()
			val.append(a)
		dp = [[-1 for i in range(w+3)]for j in range(2)]
		dp[0][0] = 0
		ans = 0
		for i in range(n):
			
			for j in range(w+3):
				dp[(i+1)%2][j] = max(dp[(i+1)%2][j],dp[(i)%2][j])
				if dp[i%2][j] != -1 and j + val[i][0]<=w:
					dp[(i+1)%2][j+val[i][0]] = max(	dp[(i)%2][j+val[i][0]] , 	dp[(i)%2][j] + val[i][1])
					ans = max(ans,dp[(i+1)%2][j+val[i][0]] )
		print(ans)

if __name__== "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
import math
def I():return int(sys.stdin.readline().replace("\n",""))
def I2():return map(int,sys.stdin.readline().replace("\n","").split())
def S():return str(sys.stdin.readline().replace("\n",""))
def L():return list(sys.stdin.readline().replace("\n",""))
def Intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def Lx(k):return list(map(lambda x:int(x)*-k,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":
    N ,W = I2()
    w = [0]*N
    v = [0]*W
    dp = [[0]*(W+1)for _ in range(N+1)]
    for i in range(N):
        a,b = I2()
        w[i] = a
        v[i] = b
    for i in range(N):
        for j in range(0,W+1):
            if(j >= w[i]):
                dp[i+1][j] = max(dp[i+1][j],dp[i][j-w[i]] + v[i])
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
            #print(dp)
    print(dp[N][W])

Submission status: Accepted

Solution code:
n,w=[int(x) for x in input().split()]
dp=[0]*(w+1)
lw=w
for test in range(n):
    cw, v = [int(x) for x in input().split()]
    temp=[0]*(w+1)
    for i in range(1,w+1):
        if cw <= i :
            temp[i]=max(dp[i],v+dp[i-cw])
        else:
            temp[i]=max(dp[i],temp[i-1])
    dp=temp[:]
    #print(dp)
print(dp[w])

Submission status: Accepted

Solution code:
def knapsackBottomUp(wt,price,c,n):
    dp=[[0 for x in range(c+1)] for y in range(n+1)]
    for i in range(n+1):
        for w in range(c+1):
            if i==0 or w==0:
                dp[i][w]=0
            else:
                inc=exc=0
                if wt[i-1]<=w:
                    inc=price[i-1]+dp[i-1][w-wt[i-1]]
                exc=dp[i-1][w]
                dp[i][w]=max(inc,exc)
    
    return dp[n][c]
  
n,c=map(int,input().split())
wt=[]
price=[]
for _ in range(n):
    w,v=map(int,input().split())
    wt.append(w)
    price.append(v)
print(knapsackBottomUp(wt,price,c,n))

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]>=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]
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)

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

# その重みを超えないように選んだ時の最大価値
for w, v in wv:
    np.maximum(dp[w:], dp[:-w] + v, out=dp[w:])

print(dp[W])

Submission status: Accepted

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
import numpy as np

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

Submission status: Accepted

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

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

for i in range(n):
    for omosa in range(w+1):
        if weight[i] <= omosa: #もし追加しても制限を超えないなら
            #i番目の商品を選ぶ場合
            dp[i+1][omosa] = max(dp[i+1][omosa], value[i] + dp[i][omosa-weight[i]])
        #i番目の商品を選ばない場合(これはいつでも起きる)
        dp[i+1][omosa] = max(dp[i+1][omosa], dp[i][omosa])

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())

dp = [[0] * (W + 1) for _ in range(N + 1)]
# dp[i][j](j=0,1,...,W)の値が求まっている状態で、dp[i+1][j]を更新することを考える

for i in range(N):
    for j in range(W+1):#重さ0からWまでチェック
        if j-w[i]>=0:#入れてもOKな場合,容量と価値を足す
            dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i])
        else:#何も入れずに先に進む
            dp[i+1][j]=dp[i][j]
print(max(dp[N]))

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())

dp = [[0] * (W + 1) for _ in range(N + 1)]
# dp[i][j](j=0,1,...,W)の値が求まっている状態で、dp[i+1][j]を更新することを考える

for i in range(N):
    for j in range(W+1):#重さ0からWまでチェック
        if j-w[i]>=0:#入れてもOKな場合,容量と価値を足す
            dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i])
        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
v = [0] * 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 j in range(W + 1):
        if w[i] <= j:
            dp[i + 1][j] = max(dp[i][j - w[i]] + v[i], dp[i][j])
        else:
            dp[i + 1][j] = dp[i][j]

print(dp[n][W])

Submission status: Accepted

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

for i in range(1,N+1):    #i番目の荷物
    for j in range(1,W+1):   #上限の重さ
        if j>=w[i-1]:
            dp[j][i]=max(dp[j-w[i-1]][i-1]+v[i-1],dp[j][i-1])
        else:
            dp[j][i]=dp[j][i-1]
            
print(dp[-1][-1])

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())
    tmp = dp[:]
    for j in range(1, W+1):
        if j  >= w and tmp[j] < tmp[j-w] + v:
            dp[j] = tmp[j-w] + v
        else:
            dp[j] = tmp[j]
    
print(dp[-1])

Submission status: Accepted

Solution code:

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


#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合S

weight=[0]*110
value=[0]*110

S = [[0 for j in range(3)] for i in range(100010)]
DP= [[0 for j in range(100100)] for i in range(110)]

for i in range(N):
    A,B=map(int,input().split())
    weight[i]=A
    value[i]=B
    
for i in range(N):
    for w in range(W+1):
        if w>=weight[i]:
            DP[i+1][w]=max(DP[i][w-weight[i]]+value[i],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.array([ [0]*(W+1) ] * (N+1))
for n in range(1,N+1):
    w, v = map(int, input().split() )
    dp[n][:] = dp[n-1][:]
    dp[n][w:W+1] = np.maximum(dp[n-1][w:W+1], dp[n-1][:W+1-w]+v )

print(dp[N][W])

Submission status: Accepted

Solution code:
import numpy as np
def resolve():
	# N: 品物の個数、W: 容量の上限
	N, W = map(int, input().split())
	# DP配列の宣言: あるナップサック内の体積における価値の最大値
	dp = np.zeros(W+1, dtype=np.int64)
	# 商品数繰り返す
	for _ in range(N):
		# 各商品の重さwと価値vを読み込み
		w, v = map(int, input().split())
		# 商品の重さ以上のテーブルを更新
		# 入れない時（そのまま）と、
		# 入れた時（入れる前の価値＋この商品の価値）の
		# 価値の最大値にテーブルを更新
		dp[w:] = np.maximum(dp[w:], dp[:W+1-w] + v)
	print(dp[W])
resolve()

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

Submission status: Accepted

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

from collections import defaultdict

dp = defaultdict(int)

dp[0] = 0

for _ in range(N):
    w, v = map(int, input().split())
    for k, val in list(dp.items()):
        if k+w <= W:
            dp[k+w] = max(dp[k+w], val+v)



print(max(dp.values()))

Submission status: Accepted

Solution code:
import numpy as np
def resolve():
	# N: 品物の個数、W: 容量の上限
	N, W = map(int, input().split())
	# DP配列の宣言: DP[N][W]
	dp = np.empty((N+1, W+1), dtype=np.int64)
	# DP配列の初期化
	dp[0,:] = 0
	for i in range(N):
		w_n, v_n = map(int, input().split())
		dp[i+1, :w_n] = dp[i, :w_n]
		dp[i+1, w_n:] = np.maximum(
			dp[i, w_n:],
			dp[i, :(W+1-w_n)] + v_n
		)
	print(dp[N, W])
resolve()

Submission status: Accepted

Solution code:
import numpy as np

N, W = map(int, input().split())
dp = np.array([ [0]*(W+1) ] * (N+1))
for n in range(1,N+1):
    w, v = map(int, input().split() )
    dp[n][:] = dp[n-1][:]
    dp[n][w:W+1] = np.maximum(dp[n-1][w:W+1], dp[n-1][:W+1-w]+v )
    # for w_lim in range(1,W+1):
    #     if w_lim - wv[n][0] >= 0 :
    #         dp[n][w_lim] = max( dp[n-1][w_lim], dp[n-1][w_lim-wv[n][0]]+wv[n][1] )
    #     else :
    #         dp[n][w_lim] = dp[n-1][w_lim]
print(dp[N][W])

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

import numpy as np

def main():
    N, W = map(int, input().split())
    dp = [0] * (W+1)
    dp = np.array(dp)
    #dp[i][j]  iまでをみてjの重さでの最大価値
    for i in range(1,N+1):
        w, v = map(int, input().split())
        dp[w:W+1] = np.maximum(dp[w:W+1], dp[:W+1-w] + v)

#    print(dp)
    print(dp[W])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

import numpy as np

def main():
    N, W = map(int, input().split())
    dp = [[0] * (W+1) for i in range(N+1)]
    dp = np.array(dp)
    #dp[i][j]  iまでをみてjの重さでの最大価値
    for i in range(1,N+1):
        w, v = map(int, input().split())
        dp[i][:] = dp[i-1][:]
        dp[i][w:W+1] = np.maximum(dp[i-1][w:W+1], dp[i-1][:W+1-w] + v)

#    print(dp)
    print(dp[N][W])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import collections as cc
input = sys.stdin.readline
I=lambda:list(map(int,input().split()))
n,w=I()
val=[]
wt=[]
for i in range(n):
	x,y=I()
	wt.append(x)
	val.append(y)
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 wt[i-1]<=j:
			dp[i][j]=max(val[i-1]+dp[i-1][j-wt[i-1]],dp[i-1][j])
		else:
			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 i in range(N+1) ]
#print(dp)
Wl=[]
Vl=[]
for i in range(N):
  w,v=map(int,input().split())
  Wl.append(w)
  Vl.append(v)

for i in range(1,N+1):
  for w in range(W+1):
    #print(i,w)
    if w>=Wl[i-1]:
      dp[i][w]=max(dp[i-1][w-Wl[i-1]]+Vl[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=map(int,input().split())
value=[]
wt=[]
for i in range(n):
    a,b=map(int,input().split())
    wt.append(a)
    value.append(b)
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 wt[i-1]<=j:
            dp[i][j]=max(value[i-1]+dp[i-1][j-wt[i-1]],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[n][w])

Submission status: Accepted

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

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

print(max(dp))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
import math
from  collections import defaultdict


# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

def solve(test):
	n, w = map(int, input().split())
	val = [None] * n
	wgt = [None] * n
	for i in range(n):
		wgt[i], val[i] = 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):
		for j in range(1, w + 1):
			dp[i][j] = dp[i - 1][j]
			if wgt[i - 1] <= j:
				dp[i][j] = max(dp[i][j], val[i - 1] + dp[i - 1][j - wgt[i - 1]])
	ans = dp[-1][-1]
	print(ans)



if __name__ == "__main__":
	test_cases = 1
	for t in range(1, test_cases + 1):
		solve(t)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# key not available ""
n, w = [int(i) for i in input().split()]
weights = []
value = []
for _ in range(n):
    x, y = [int(i) for i in input().split()]
    weights.append(x)
    value.append(y)
dp = [[0 for i in range(w+1)] for j in range(n)]
for i in range(n):
    for j in range(1, w+1):
        if weights[i] <= j:
            dp[i][j] = max(value[i] + dp[i-1][j-weights[i]],dp[i-1][j])
        else:
            dp[i][j] = max(dp[i][j-1],dp[i-1][j])
print(dp[-1][-1])

## 0 1 2 3  4  5  6  7  8
#  0 0 0 30 30 30 30 30 30
#  0 0 0 30 50 50 50 80 80
#  0 0 0 30 50 60 60 80 90

Submission status: Accepted

Solution code:
n,w = map(int,input().split())
inf = float("inf")
dp = [[-inf]*(w+1) for _ in range(n+1)]
for j in range(w+1):
    dp[0][j] = 0
for i in range(n):
    s,t = map(int,input().split())
    for l in range(w+1):
        if l-s >=0:
            dp[i+1][l] = max(dp[i][l],dp[i][l-s]+t)
        else:
            dp[i+1][l] = dp[i][l]
print(dp[-1][w])

Submission status: Accepted

Solution code:
NW = list(map(int, input().split()))
wv = []
for i in range(NW[0]):
    wv.append(list(map(int, input().split())))

dp = [[0] * (NW[1]+1) for i in range(NW[0]+1)]
for i in range(NW[0]+1):
    for sum_w in range(NW[1]+1):
            try:
                if (sum_w - wv[i][0])>=0:
                    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])
            except:
                continue

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

Submission status: Accepted

Solution code:
from numpy import zeros, maximum            
                                            
n, W, *wv = map(int, open(0).read().split())
t = zeros(W+1, int)                         
for i in range(n):                          
    w = wv[i * 2]                           
    v = wv[i * 2 + 1]                       
    t[w:] = maximum(t[w:], t[:-w]+v)        
print(t[-1])

Submission status: Accepted

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

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

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

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

    if w<=W:
        dp[i][w:]=np.maximum(dp[i-1][w:],dp[i-1][:W-w+1]+v)
        dp[i][:w]=dp[i-1][:w]
    else:
        dp[i]=dp[i-1]

print(dp[N][W])

Submission status: Accepted

Solution code:
# TODO:実装
N, W = map(int, input().split())

DP = {0: 0}
for i in range(N):
    wi, vi = map(int, input().split())
    DP_dst = DP.copy()
    for j in DP:
        if j+wi <= W:
            DP_dst[j+wi] = max(DP.get(j+wi, 0), DP[j]+vi)
    DP = DP_dst
print(max((DP[x] for x in DP)))

Submission status: Accepted

Solution code:
import numpy as np

n, w = map(int, input().split())
dp = np.zeros(w+1, dtype=int)

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

print(dp.max())

Submission status: Accepted

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

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

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

print(dp[n][w])
#for i in range(n+1):
#  print(dp[i])

Submission status: Accepted

Solution code:
def e():
    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])


##########
if __name__ == "__main__":
    e()

Submission status: Accepted

Solution code:
def main():
    def solve(N, W, wv):
        dp = [-1] * (W+1)
        dp[0] = 0

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

            for j in range(W-wi, -1, -1):
                if dp[j] == -1:
                    continue
                if dp[j+wi] < dp[j] + vi:
                    dp[j+wi] = dp[j] + vi

        return max(dp)

    N, W = map(int, input().split())
    wv = tuple(tuple(map(int, input().split())) for i in range(N))
    print(solve(N, W, wv))

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

Submission status: Accepted

Solution code:
def solve(N,W,wv):
    dp=[-1]*(W+1)
    dp[0]=0
    for i in range(N):
        cur_w=wv[i][0]
        cur_v=wv[i][1]
        for j in range(W-cur_w,-1,-1):
            if dp[j]==-1:
                continue
            if dp[j+cur_w]<dp[j]+cur_v:
                dp[j+cur_w]=dp[j]+cur_v
    return max(dp)


N,W=map(int,input().split())
wv=tuple(tuple(map(int,input().split())) for _ in range(N))
print(solve(N,W,wv))

Submission status: Accepted

Solution code:

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

weights = []
profits = []

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

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

print(dp[n][w])

Submission status: Accepted

Solution code:
def solve(N,W,wv):
    dp=[-1]*(W+1)
    dp[0]=0
    for i in range(N):
        cur_w=wv[i][0]
        cur_v=wv[i][1]
        for j in range(W-cur_w,-1,-1):
            if dp[j]==-1:
                continue
            if dp[j+cur_w]<dp[j]+cur_v:
                dp[j+cur_w]=dp[j]+cur_v
    return max(dp)


N,W=map(int,input().split())
wv=tuple(tuple(map(int,input().split())) for _ in range(N))
print(solve(N,W,wv))

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
dp=[-1]*(w+1)
dp[0]=0
for _ in range(n):
  a,d=map(int,input().split())
  for b in range(w,a-1,-1):
    if dp[b-a]!=-1:
    	dp[b]=max(dp[b],d+dp[b-a])
print(max(dp))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,w = map(int, input().split())
high = [0] * (w + 1)
for i in range(n):
    weight, value = map(int, input().split())
    if weight <= w:
        renewal = high[:weight]
        renewal += [max([j+value, k]) for j,k in zip(high[:w-weight+1], high[weight:])]
        high = renewal
print(high[w])

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, W = na()
w = []
v = []
for i in range(n):
    x,y = map(int,input().split())
    w.append(x)
    v.append(y)

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

for i in range(n):
    wts.append(list(map(int, input().split())))
    
dp = [[0]*(w+1) for i in range(n)]
dp[0][wts[0][0]] = wts[0][1]

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np
def main():
    #入力
    readline=stdin.readline
    inf=10**12
    n,max_w=map(int,readline().split())
    w=[0]*n
    v=[0]*n
    for i in range(n):
        w[i],v[i]=map(int,readline().split())

    dp=np.full((n+1,max_w+1),-inf,dtype=np.int64)
    dp[0][0]=0
    for i in range(n):
        dp[i+1,:w[i]]=dp[i,:w[i]]
        dp[i+1,w[i]:]=np.maximum(dp[i,w[i]:],dp[i,:max_w-w[i]+1]+v[i])

    print(dp[n].max())

if __name__=="__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from heapq import heapify, heappop, heappush
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

# ここから書き始める
n, w = map(int, input().split())
dp = [[0 for i in range(w + 1)] for i in range(n)]
for i in range(n):
    weight, value = map(int, input().split())
    if i == 0:
        dp[i][weight] = value
        continue
    for j in range(w + 1):
        dp[i][j] = dp[i - 1][j]
        if 0 <= j - weight:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - weight] + value)
print(max(dp[-1]))

Submission status: Accepted

Solution code:
import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N,W = map(int,readline().split())
WV = [list(map(int,readline().split())) for _ in range(N)]

dp = np.zeros(W+1,np.int64)
for w,v in WV:
  np.maximum(dp[w:],dp[:-w].copy() +v,out=dp[w:])
print(dp.max())

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/dp/submissions/13960132

def MAX(a, b):
    d = a + ms - b
    return b + ((ms - ((d & ms) >> (K - 1))) & mask & d)

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)
mask = int(("0" + "1" * (K - 1)) * (W + 1), 2)
tt = (1 << K - 1) - 1
one = int(("0" * (K - 1) + "1") * (W + 1), 2)

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:
# https://atcoder.jp/contests/dp/submissions/13960132

def MAX(a, b):
    d = a + ms - b
    return b + ((((d & ms) >> (K - 1)) * tt) & d)

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)

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:
def MAX(a, b):
    return b + (((((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)

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))