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())
stones=[None]*n
for i in range(n):
  w,v=map(int,input().split())
  stones[i]=[w,v]

import numpy as np
dp=np.zeros(W+1,dtype=int)

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

print(dp.max())

Submission status: Accepted

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

#DP[n][w]: n番目までの品物で wグラムまでの重さを入れた場合の価値の最大
for n in range(1,N+1):
    for w in range(1,W+1):
        wi,vi = Data[n]
        if w >= wi:
            DP[n][w] = max(DP[n][w],DP[n-1][w-wi]+vi)
        DP[n][w] = max(DP[n][w],DP[n-1][w])

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

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

print(dp[n][w])

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


def main():
    N, W = map(int, readline().split())
    WV = np.array([[int(x) for x in readline().split()] for _ in range(N)])

    dp = np.zeros([W+1], np.int64)

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

    print(np.max(dp))


main()

Submission status: Accepted

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

dp = np.zeros(w+1,int)#w+1のint型配列
for i in range(n):
	W,V = WV[i]
	#print(str(dp)+":"+str(dp[W:])+":"+str(dp[:-W]))
	dp[W:] = np.maximum(dp[W:],dp[:-W]+V)
	#print(str(dp))

print(dp[-1])

Submission status: Accepted

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, w = list(map(int, input().rstrip('\n').split()))
    dp = [0] * (w + 1)
    for _ in range(n):
        wv, vv = list(map(int, input().rstrip('\n').split()))
        for i in range(w - wv, -1, -1):
            dp[i+wv] = max(dp[i+wv], dp[i] + vv)
    print(dp[-1])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def main():

    N, W = map(int, raw_input().split())
    dp = [0]*(W+1)
 
    for i in xrange(N):
        w, v = map(int, raw_input().split())
        for j in xrange(W, w-1, -1):
            x = dp[j-w] + v
            if x > dp[j]:
                dp[j] = x
 
    print dp[-1]

main()

Submission status: Accepted

Solution code:
#EDP-D, E
import sys
from collections import defaultdict
n, W = map(int, sys.stdin.readline().split())
dp = [defaultdict(int) for _ in range(n)]
#初期設定
w, v = map(int, sys.stdin.readline().split())
dp[0][w] = v
#print(dp)

for i in range(1, n):
    w, v = map(int, sys.stdin.readline().split())
    dp[i][w] = max(dp[i-1].get(w, 0), v)
    for w1, v1 in dp[i-1].items():
        dp[i][w1] = max(dp[i][w1], v1)
        if w+w1<=W:
            dp[i][w1+w] = max(dp[i][w1+w], v1+v)

print(max(dp[-1].values()))

Submission status: Accepted

Solution code:
from itertools import count

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 w in range(W+1):
        if w - WV[i][0] >= 0:  # 品物を追加できるとき
            dp[i+1][w] = max(dp[i+1][w], dp[i][w-WV[i][0]] + WV[i][1])
        # できないとき
        dp[i+1][w] = max(dp[i+1][w], dp[i][w])
print(dp[N][W])

Submission status: Accepted

Solution code:
"""
【01ナップザック問題】
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i,v_i<=100, 1<=W<=10000
"""
#------------------------------------------------------------------------------

#入力,準備
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)

#メイン
#dp[j] : 重さの総和がjを超えないように選んだ時の価値の総和の最大値
for i in range(n):
    j=W
    while j>=w[i]:
        dp[j]=max(dp[j],dp[j-w[i]]+v[i])
        j-=1

print(dp[W])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,w=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
res=[0 for _ in range(w+1)]
for i in range(n):
    for j in range(w,a[i][0]-1,-1):
        res[j]=max(res[j],res[j-a[i][0]]+a[i][1])
print(res[w])

Submission status: Accepted

Solution code:
n,W=map(int, input().split())
w=[0]*n
v=[0]*n
for i in range(n):
    x,y=map(int, input().split())
    w[i]=x
    v[i]=y
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 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:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, w = list(map(int, readline().split()))
    wv = [list(map(int, readline().split())) for _ in range(n)]
    dp = [0] * (w + 1)
    for ww, vv in wv:
        for i in range(w-ww+1, -1, -1):
            if i + ww <= w:
                dp[i+ww] = max(dp[i+ww], dp[i] + vv)
    print(dp[-1])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
n, W = map(int, sys.stdin.readline().split())
dp = [[0 for _ in range(W+1)] for _ in range(n)]
for i in range(n):
    w, v =map(int, sys.stdin.readline().split())
    for j in range(W+1):
        dp[i][j] = max(dp[i-1][j], dp[i][j])
        if dp[i-1][j] !=0 and j+w<=W:
            dp[i][j+w] = max(dp[i-1][j+w], v+ dp[i-1][j])
            #print(dp, i)
        
    dp[i][w] = max(dp[i-1][w], v)
    
#print(dp)  
print(max(dp[-1]))

Submission status: Accepted

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

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

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


print(max(dp[n]))

Submission status: Accepted

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

dp=np.zeros(w+1,int)
for i in range(n):
  w,v=WV[i]
  dp[w:]=np.maximum(dp[w:],dp[:-w]+v)
print(dp[-1])

Submission status: Accepted

Solution code:
def Knapsack1(W,w,v): # n個のナップザック(重さw[i],価値v[i]) 総重量W以内での価値の最大化
    n=len(w)
    # dp[i][j] : i番目の品物で重さj以下の価値の最大値
    dp=[[0 for _ in range(W+1)] for _ in range(n+1)]
    for i in range(1,n+1):
        for j in range(W+1):
            dp[i][j]=max( dp[i][j],dp[i-1][j] )
            if j >= w[i-1]:
                dp[i][j]=max(dp[i][j],dp[i-1][j-w[i-1]]+v[i-1])
    print(max(dp[n]))

def main():
    n,W = map(int,input().split())
    w=[0 for _ in range(n)]
    v=[0 for _ in range(n)]
    for i in range(n):
        w[i],v[i] = map(int,input().split())
    Knapsack1(W,w,v)
if __name__ == "__main__":
    main()

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

print(dp[W])

Submission status: Accepted

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

weights = [0]*(N+5)
values = [0]*(N+5)

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

for i in range(N):
    weights[i], values[i] = map(int, input().split())
    for sum_w in range(W+1):
        if sum_w >= weights[i]:
            if dp[i+1][sum_w] < dp[i][sum_w-weights[i]]+values[i]:
                dp[i+1][sum_w] = dp[i][sum_w-weights[i]]+values[i]
        if dp[i+1][sum_w] < dp[i][sum_w]:
            dp[i+1][sum_w] = dp[i][sum_w]


print(max([max(row) for row in dp]))

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):
    j=W
    while j>=w[i]:
        dp[j]=max(dp[j],dp[j-w[i]]+v[i])
        j-=1
print(dp[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 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:
import numpy as np
N, W = map(int, input().split())
l = sorted([tuple(map(int, input().split())) for i in range(N)], key=lambda x: x[0])
dp = np.zeros(W+1, dtype=int)
for i in range(N):
    w = l[i][0]
    dp[w:] = np.maximum(dp[w:], dp[:-w] + l[i][1])
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,W = map(int,readline().split())
m = map(int,read().split())
WV = list(zip(m,m))

# 重さ -> 最大価値

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

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

answer = dp.max()
print(answer)

Submission status: Accepted

Solution code:
N, W = [int(x) for x in input().split()]
WV = [[int(x) for x in input().split()] for _ in range(N)]
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(N):
    for w in range(W+1):
        if (w - WV[i][0] >= 0):
            dp[i+1][w] = max(dp[i+1][w], dp[i][w-WV[i][0]]+WV[i][1])
        dp[i+1][w] = max(dp[i+1][w], dp[i][w])
print(dp[N][W])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
w=[0]*n
v=[0]*n
for i in range(n):
    w[i],v[i]=map(int,input().split())
dpv=[0]*(k+1)
dpw=[0]*(k+1)
for j in range(n):
    for i in range(k,-1,-1):
        if i-w[j]>=0:
            if dpv[i-w[j]]+v[j]>dpv[i]:
                dpw[i]=dpw[i-w[j]]+w[j]
                dpv[i]=dpv[i-w[j]]+v[j]
        else:
            break
print(dpv[k])

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    w = [0] * n
    v = [0] * n
    for i in range(n):
        w[i], v[i] = list(map(int, input().split()))
    l = [0] * (m + 1)
    for i in range(n):
        for j in range(m, w[i] - 1, -1):
            x = v[i] + l[j-w[i]]
            if x > l[j]:
                l[j] = x
    print(l[-1])
main()

Submission status: Accepted

Solution code:
def main():
    N, W = map(int, input().split())
    wi, vi = map(int, input().split())
    dp = [0] * wi + [vi] * (W + 1 - wi)
    for _ in range(1, N):
        wi, vi = map(int, input().split())
        for i in range(W, wi - 1, -1):
            t = dp[i - wi] + vi
            if t > dp[i]:
                dp[i] = t
    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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


def main():
    N, W = map(int, readline().split())
    wv = map(int, read().split())
    dp = np.zeros(W + 1, np.int64)

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

    print(dp.max())


if __name__ == '__main__':
    main()

Submission status: Accepted

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

N, W = map(int, readline().split())
wv = map(int, read().split())
dp = np.zeros(W + 1, np.int64)

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

print(dp.max())

Submission status: Accepted

Solution code:
def resolve():
    N,W = map(int,input().split())
    weights = [0]
    values  = [0]
    for i in range(N):
        w,v = map(int,input().split())
        weights.append(w)
        values.append(v)

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

    for ni in range(1,len(min_costs)):
        for wi in range(1,len(min_costs[ni])):
            if wi < weights[ni]:
                min_costs[ni][wi] = min_costs[ni -1][wi]
            else:
                min_costs[ni][wi] = max(min_costs[ni -1][wi],min_costs[ni -1][wi-weights[ni]] + values[ni])

    print(min_costs[-1][-1])
    
resolve()

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
#dp=[[0,0] for i in range(w+1)]
dp=[]
for i in range(w+1):
    dp.append([0,0])
dp[0][0]=1
it=[]
val=[]
for i in range(n):
    a,b=input().split()
    it.append(int(a))
    val.append(int(b))
for i in range(n):
    x=it[i]
   # dp2=dp[:]
    ac=[]
    for j in range(w-x,-1,-1):
        if dp[j][0]==1:
           # print(i,j)
            ac.append(j+x)
            dp[j+x][1]=max(dp[j+x][1],val[i]+dp[j][1])
   # print(dp)
    for i in ac:
        dp[i][0]=1
  #  print(dp,dp2)
print(max([i[1] for i in dp]))

Submission status: Accepted

Solution code:
# dp[i][j] i個目までの荷物を使って重さjまでとなるのときの最大の価値

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

Submission status: Accepted

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

def Main(N, W, V):
    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 < V[i][0]):
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = max(dp[i][j], dp[i][j-V[i][0]]+V[i][1])
    return dp[N][W]            

def main():
    N, W = map(int, input().split())
    V = []
    for _ in range(N):
        V.append(list(map(int, input().split())))
    print(Main(N, W, V))

if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

    # for i in range(N+1):
    #     print(dp[i])
    print(dp[N][W])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#メモ化したもの(修正版)
n,w=map(int,input().split())
a=[]
dp=[]
for i in range(n):
   a.append(list(map(int,input().split())))
for k in range(n+1):
   dp.append([-1]*(w+1))
def rec(i,j):
   if dp[i][j]>=0:
       return dp[i][j]
   if i==n:
       res=0
   elif j<a[i][0]:
       res=rec(i+1,j)
   else:
       res=max(rec(i+1,j),rec(i+1,j-a[i][0])+a[i][1])
   dp[i][j]=res
   return res
print(rec(0,w))

Submission status: Accepted

Solution code:
#dpテーブルのみでの解法(とびとび)
n,w=map(int,input().split())
a=[]
dp=[]
for i in range(n):
   a.append(list(map(int,input().split())))
for k in range(n+1):
  dp.append([])
  for l in range(w+1):
      dp[k].append(0)
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+a[i][0]<=w:
           dp[i+1][j+a[i][0]]=max(dp[i+1][j+a[i][0]],dp[i][j]+a[i][1])
print(dp[n][w])

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
a=[]
dp=[]
for i in range(n):
   a.append(list(map(int,input().split())))
for k in range(n+1):
  dp.append([])
  for l in range(w+1):
      dp[k].append(0)
for i in range(n-1,-1,-1):
   for j in range(w+1):
       if j<a[i][0]:
           dp[i][j]=dp[i+1][j]
       else:
           dp[i][j]=max(dp[i+1][j],dp[i+1][j-a[i][0]]+a[i][1])
print(dp[0][w])

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
a=[]
dp=[]
for i in range(n):
   a.append(list(map(int,input().split())))
for k in range(n+1):
  dp.append([])
  for l in range(w+1):
      dp[k].append(0)
for i in range(n):
   for j in range(w+1):
       if j<a[i][0]:
           dp[i+1][j]=dp[i][j]
       else:
           dp[i+1][j]=max(dp[i][j],dp[i][j-a[i][0]]+a[i][1])
print(dp[n][w])

Submission status: Accepted

Solution code:
#dpテーブルのみでの解法(順方向)
n,w=map(int,input().split())
a=[]
dp=[]
for i in range(n):
   a.append(list(map(int,input().split())))
for k in range(n+1):
  dp.append([])
  for l in range(w+1):
      dp[k].append(0)
for i in range(n):
   for j in range(w+1):
       if j<a[i][0]:
           dp[i+1][j]=dp[i][j]
       else:
           dp[i+1][j]=max(dp[i][j],dp[i][j-a[i][0]]+a[i][1])
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+1)] for _ in range(N+1)]
for i in range(N):
  w = wv[i][0]
  for j in range(W+1):
    dp[i+1][j]=dp[i][j]
    if j >= w:
      dp[i+1][j] = max(dp[i+1][j], dp[i][j-w] + wv[i][1])
print(max(dp[N]))

Submission status: Accepted

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

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

dp[0][0] = 0

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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(N):
    for j in range(W+1):
        if w[i] > j:
            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:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,W=map(int,input().split())
    w=[0]*(n+1)
    v=[0]*(n+1)
    for i in range(1,n+1):
        w[i],v[i]=map(int,input().split())
    dp=[0]*(W+1)
    for i in range(1,n+1): # i番目を見る
        newdp=dp[:] # 使わない場合を先に計算したことにしておく
        for j in range(W+1):
            if(j-w[i]>=0): # i番目を使う場合(貰うDP)
                newdp[j]=max(dp[j-w[i]]+v[i],dp[j])
        dp=newdp
    print(dp[-1])
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,W=map(int,input().split())
    w=[0]*(n+1)
    v=[0]*(n+1)
    for i in range(1,n+1):
        w[i],v[i]=map(int,input().split())
    dp=[0]*(W+1)
    for i in range(1,n+1): # i番目を見る
        newdp=dp[:]
        for j in range(W+1):
            if(j+w[i]<=W):
                newdp[j+w[i]]=max(newdp[j+w[i]],dp[j]+v[i])
        dp=newdp
    print(dp[-1])
resolve()

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
dp = [{ 0: 0 }]
for i in range(N):
  w, v = map(int, input().split())
  d = dp[i]
  d2 = {}
  for w0 in d:
    v0 = d[w0]
    d2[w0] = v0
  for w0 in d:
    v0 = d[w0]
    if w0+w > W:
      continue
    if w0+w not in d:
      d2[w0+w] = v0+v
    else:
      d2[w0+w] = max(d2[w0+w], v0+v)
  dp.append(d2)
r = max(dp[N].values())
print(r)

Submission status: Accepted

Solution code:
import numpy as np

MAX_WEIGHT = 100100


def main(n, w, items):
    dp = np.zeros((n + 1, MAX_WEIGHT), dtype=int)
    for i in range(n):
        weight, value = items[i]
        dp[i + 1][:weight] = dp[i][:weight]
        dp[i + 1][weight:] = np.maximum(dp[i][weight:], dp[i][:MAX_WEIGHT - weight] + value)
    return dp[n][w]


if __name__ == '__main__':
    N, W = map(int, input().split())
    ITEMS = []
    for _ in range(N):
        ITEMS.append(tuple(map(int, input().split())))
    print(main(N, W, ITEMS))

Submission status: Accepted

Solution code:
import numpy as np


def main(n, w, items):
    dp = np.zeros((n + 1, w + 1), dtype=int)
    for i in range(1, n + 1):
        weight, value = items[i - 1]
        dp[i][:weight] = dp[i - 1][:weight]
        dp[i][weight:] = np.maximum(dp[i - 1][weight:], dp[i - 1][:w - weight + 1] + value)
    return dp[n][w]


if __name__ == '__main__':
    N, W = map(int, input().split())
    I = []
    for _ in range(N):
        I.append(tuple(map(int, input().split())))
    print(main(N, W, I))

Submission status: Accepted

Solution code:
def main():
    N, W = (int(i) for i in input().split())
    weight = [0] * (N+1)
    value = [0] * (N+1)
    for i in range(1, N+1):
        w, v = (int(i) for i in input().split())
        weight[i] = w
        value[i] = v
    dp = [[0 for i in range(W + 1)] for j in range(N + 1)]

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

    print(dp[N][W])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i in range(n):
    temp1, temp2 = map(int, input().split())
    w.append(temp1)
    v.append(temp2)

#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 reversed(range(n)):
    for j in reversed(range(W)):
        weight, val = w[i], v[i]

        if j + weight <= W:
            chose = dp[i+1][j + weight] + val
            unchose = dp[i+1][j]
            dp[i][j] = max(chose, unchose)
        else:
            dp[i][j] = dp[i+1][j]

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

Submission status: Accepted

Solution code:
import numpy as np
N, W = map(int, input().split())

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.buffer.readline().rstrip()
def resolve():
    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(n):
        for k in range(w+1):
            if(k+W[i]<=w):
                dp[i+1][k+W[i]]=max(dp[i][k]+V[i],dp[i+1][k+W[i]])
            dp[i+1][k]=max(dp[i+1][k],dp[i][k])
    print(dp[n][w])
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.buffer.readline().rstrip()
def resolve():
    n,w=map(int,input().split())
    W=[0]*(n+1)
    V=[0]*(n+1)
    for i in range(n):
        W[i+1],V[i+1]=map(int,input().split())
    dp=[[0]*(w+1) for _ in range(n+1)]
    for i in range(1,n+1):
        for k in range(w+1):
            if(k-W[i]>=0):
                dp[i][k]=max(dp[i-1][k-W[i]]+V[i],dp[i-1][k])
            else:
                dp[i][k]=dp[i-1][k]
    print(dp[n][w])
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
def make_v(*args,e=0):
    from copy import deepcopy
    A=e
    for i in args[::-1]: A=[deepcopy(A) for _ in range(i)]
    return A
input=lambda :sys.stdin.buffer.readline().rstrip()
def resolve():
    n,w=map(int,input().split())
    W=[0]*(n+1)
    V=[0]*(n+1)
    for i in range(n):
        W[i+1],V[i+1]=map(int,input().split())
    dp=make_v(n+1,w+1)
    for i in range(1,n+1):
        for k in range(w+1):
            if(k-W[i]>=0):
                dp[i][k]=max(dp[i-1][k-W[i]]+V[i],dp[i-1][k])
            else:
                dp[i][k]=dp[i-1][k]
    print(dp[n][w])
resolve()

Submission status: Accepted

Solution code:
from sys import stdin
N, W = [int(x) for x in stdin.readline().rstrip().split()]
 
baggage = [0]*N
 
for l in range(N):
    w, v = [int(x) for x in stdin.readline().rstrip().split()]
    baggage[l] = (w, v)
 
dp = [[0]*(W+1) for _ in range(N+1)]
 
for i in range(N):
    for w in range(W+1):
        if w >= baggage[i][0]:
            dp[i+1][w] = max(baggage[i][1]+dp[i][w-baggage[i][0]],dp[i][w])
 
        dp[i+1][w] = max(dp[i][w],dp[i+1][w])
print(dp[N][W])

Submission status: Accepted

Solution code:
def main():
    # input
    m=0
    n, W = map(int, input().split())
    v, w = [0], [0]
    for _ in range(n):
        wi, vi = map(int, input().split())
        v.append(vi)
        w.append(wi)
    cond = []
    b_list = []
    for _ in range(m):
        a, b = map(int, input().split())
        cond.append([b, a])
        b_list.append(b)
    cond.sort(reverse=True)

    # prepare
    for i in range(m):
        a, b = cond[i][1], cond[i][0]
        v[a] += v[b]
        w[a] += w[b]

    # process
    b_tuple = tuple(b_list)
    # del vi, wi, a, b
    dp = [[0]*(W+1) for _ in range(n+1)]
    skip = 0
    for i in range(1, n+1):
        if i in b_tuple:
            skip += 1
            continue
        for j in range(1, W+1):
            if j>=w[i]:
                dp[i][j] = max(dp[i-1-skip][j], dp[i-1-skip][j-w[i]]+v[i])
            else:
                dp[i][j] = dp[i-1-skip][j]
    print(max(max(dp)))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import copy

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




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


for i in range(W+1):
    if i < w[0]:
        s[0][i] = 0
    else :
        s[0][i] = v[0]

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

Submission status: Accepted

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

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)]
ans = int(0)
dp[0][0] = 0

for i in range(N):
    for j in range(W+1):
        if w[i]<=j:
            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])

ans = dp[N][W]

print(ans)

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


for i in range(N):
    for j in range(W+1):
        if w[i]<=j:
            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])

ans = dp[N][W]

print(ans)

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):
		# 品物(w[i],v[i])を選ぶとき、j-w[i]>=0に限って、価値v[i]が加算される
		if j - w[i] >= 0:
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i])
		# 品物(w[i],v[i])を選ばないとき、何も加算しない
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(dp[N][W])