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:
#!/usr/bin/env python3

from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


def debug(*x):
    print(*x)


def solve(N, W, WV):
    "void()"
    values = [0] * (W + 1)
    for i in range(N):
        next_values = values[:]
        weight, value = WV[i]
        for j in range(W - weight + 1):
            next_values[j + weight] = max(
                values[j + weight],
                values[j] + value)
        values = next_values
    return max(values)


T1 = """
3 8
3 30
4 50
5 60
"""


def main():
    N, W = map(int, input().split())
    WV = [
        list(map(int, input().split()))
        for i in range(N)
    ]
    print(solve(N, W, WV))


def _test():
    """
    >>> as_input(T1)
    >>> main()
    90
    """
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

Solution code:
def knapsack(W,weight,value):
    n = len(weight)#or len(value)
    dp = [[0]*(W+1) for _ in range(n+1)]
    # 初期化
    for j in range(W):
        dp[0][j] = 0
    for i in range(n):
        for j in range(W+1):
            if weight[i] <= j:
                dp[i+1][j] = max(dp[i][j-weight[i]]+value[i],dp[i][j])
            else:
                dp[i+1][j] = dp[i][j]
    return dp

N,W = map(int,input().split())
values, weights = [],[]
for _ in range(N):
    ｗ,ｖ = map(int,input().split())
    values.append(v)
    weights.append(w)
    
dp = knapsack(W,weights,values)
print(dp[-1][-1])

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

Submission status: Accepted

Solution code:
# from sys import stdin, stdout
n,capacity=map(int,input().split())
weights=[0]*n
values=[0]*n
for i in range(n):
    weights[i],values[i]=map(int,input().split())
dp=[[0]*(capacity+1) for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,capacity+1):
        if(weights[i-1]<=j):
            dp[i][j]=max(values[i-1]+dp[i-1][j-weights[i-1]],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[n][capacity])

Submission status: Accepted

Solution code:
inf = 2**60
'''
def table(size, init): #配列生成
  x = len(size)
  l = [init for i in range(size[x-1])]
  for i in range(x-1):
    l = [l for k in range(size[x-2-i])]
  return l
'''

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

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


for i in range(n):
  for j in range(W+1):
        if j>=w[i]:
            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:
import sys
readline = sys.stdin.readline

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

import numpy as np

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

for i in range(N):
  w,v = map(int,readline().split())
  np.maximum(dp[:-w] + v, dp[w:], out = dp[w:])
  
print(dp.max())

Submission status: Accepted

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

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

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

for i in range(N):
  w,v = map(int,readline().split())
  np.maximum(dp[:-w] + v,dp[w:],out = dp[w:])

print(dp.max())

Submission status: Accepted

Solution code:
#####################################################################################################
##### ナップサック問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_C&lang=ja
#####################################################################################################


import sys
input = sys.stdin.readline

M, W = map(int, input().split())                                # M: 品物の種類 W: 重量制限

dp_min = 0                                                      # 総和価値の最小値


price_list = [0]
weight_list = [0]

for _ in range(M):
    weight, price = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)

# price_list = [0] + list(map(int, input().split()))              # item = 0 は 0 種類の品物を用いた場合に対応するため、参照されることはない。item = 1 で品物の 0 番目に対応させるためにインクリメントが必要となる。
# weight_list = [0] + list(map(int, input().split()))             # item = 0 は 0 種類の品物を用いた場合に対応するため、参照されることはない。item = 1 で品物の 0 番目に対応させるためにインクリメントが必要となる。

# dp[item <= M ][weight <= W]
dp = [[dp_min] * (W + 1) for _ in range(M + 1)]                       # 左端と上端の境界条件で W, M を一個ずつ多めに取る

for item in range(M+1):                                         # 左端の境界条件
    dp[item][0] = 0                                             # 重さ 0 を実現するのに必要な品物の個数は 0 個

# for weight in range(W+1):                                     # 上端の境界条件
#     dp[0][weight] = dp_max                                    # 0 種類の品物で実現できる重量は存在しない　（dpの初期化で自動的に課せる場合が多い）


for item in range(1,M+1):                                       # 境界条件を除いた M 回のループ（※ f[item] = g.f[item-i] の漸化式なので、list index out of range となる）
    for weight in range(1, W + 1):
        if weight < weight_list[item]:                          # weight (重量価値) < weight_list[item] (品物の重量) の時は無視してよい
            dp[item][weight] = dp[item - 1][weight]
        else:
            dp[item][weight] = max(dp[item-1][weight], dp[item-1][weight - weight_list[item]] + price_list[item])        # 重複なし: dp[item][weight - weight_list[item]] ⇒　dp[item-1][weight - weight_list[item]]

print(dp[M][W])

Submission status: Accepted

Solution code:
import sys
#import numpy as np
#from collections import defaultdict
import math
#from collections import deque

input = sys.stdin.readline
#import numpy as np



def main():

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

    dp = [0] * (W+2)

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

        for j in range(W+1,w-1,-1):
            dp[j] =max(dp[j-w] +v ,dp[j])

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




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#dp[i][j]:i番目までの品物の中で重さj以下になるように持った時の価値
#最終的な答えに沿うようにここは決める

N,W = map(int,input().split())
wv = [list(map(int,input().split())) for i in range(N)]#wv:01

dp = [[0]*(W+1) for i in range(0,N,1)]
for i in range(wv[0][0],W+1,1):#一番左の荷物に関しては自明なので
    dp[0][i]=wv[0][1]

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

Submission status: Accepted

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

def knapsack(sm,W,n,V):
    K = [[0]*(sm+1) for i in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,sm+1):
            K[i][j] = K[i-1][j]
            if W[i-1] <= j:
                K[i][j] = max(V[i-1]+K[i-1][j-W[i-1]], K[i-1][j])
    return K[n][sm]

n,wt = ip()
V,W = [0]*n,[0]*n
for i in range(n):
    w,v = ip()
    V[i] = v
    W[i] = w
ans = knapsack(wt,W,n,V)
print(ans)

Submission status: Accepted

Solution code:
II = lambda: int(input())
SI = lambda: input()
LI = lambda: list(map(int,input().split()))
MI = lambda: map(int,input().split())
n,m = MI()
dp = [0]*(m+1)
for i in range(n):
	w,v = MI()
	for j in range(m,w-1,-1):
		dp[j] = max(dp[j-w]+v,dp[j])
print(dp[m])

Submission status: Accepted

Solution code:
import numpy as np

def main_():
    N,W=map(int,input().strip().split())
    l=[]
    for n in range(N):
        l.append(list(map(int,input().strip().split())))
    
    dp=np.zeros(W+1,np.int64)

    for n in range(N):
        w=l[n][0]
        v=l[n][1]
        dp[w:]=np.maximum(dp[w:],dp[:-w]+v)
    return dp.max()

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

Submission status: Accepted

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

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

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

print(table[N][W])

Submission status: Accepted

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

val, wt = [], []
for _ in range(N):
    res = list(map(int, input().split()))
    val.append(res[1])
    wt.append(res[0])

dp = [[0 for _ in range(W + 1)] for _ in range(N+1)]
for n in range(N + 1):
    for w in range(W + 1):
        if n == 0 or w == 0:
            dp[n][w] = 0
        elif wt[n-1] > w:
            # If weight is bigger than knapsack capacity - this item can't be included
            dp[n][w] = dp[n - 1][w]
        else:
            # If this item can be included - decide to include it or not
            dp[n][w] = max(val[n-1] + dp[n-1][w - wt[n-1]], dp[n-1][w])  
            # first term - include, second term - not
            
print(dp[N][W])

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
w=[]
v=[]
for i in range(N):
    ww,vv=map(int,input().split())
    w.append(ww)
    v.append(vv)

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]>=0):
            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[N][W])

Submission status: Accepted

Solution code:

import numpy as np
n, W = map(int,input().split())
w = []
v = []
for i in range(n):
    w_,v_= map(int,input().split())
    w.append(w_)
    v.append(v_)
dp = np.zeros(W+1, dtype=np.int64)
for i in range(n):
	dp[w[i]:] = np.maximum(dp[:-w[i]] + v[i], dp[w[i]:])
print(dp[W])

Submission status: Accepted

Solution code:
def main():
    n, maxW, weight, value = getInputs()

    accumulatedValue = [0] * (maxW + 1)

    possible = [False] * (maxW + 1)
    possible[0] = True

    used = []
    for i in range(maxW + 1):
        used.append([0] * n)

    for x in range(min(weight), maxW + 1):
        for w in range(n):
            weightW = weight[w]

            if (x - weightW >= 0) and possible[x - weightW] and used[x - weightW][w] == 0:
                newValue = accumulatedValue[x - weightW] + value[w]

                if newValue > accumulatedValue[x]:
                    accumulatedValue[x] = newValue
                    used[x] = used[x - weightW].copy()
                    used[x][w] = 1
                    possible[x] = True

    print(max(accumulatedValue))

def getInputs():
    n, maxW = map(lambda x: int(x), input().split())

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

    return n, maxW, weight, value

main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

ans = dp.max()
print(ans)

Submission status: Accepted

Solution code:
import sys
def main():
    N,W=tuple(map(int,sys.stdin.readline().split()))
    w,v=[0],[0]
    for _ in [0]*N:
        wi,vi=tuple(map(int,sys.stdin.readline().split()))
        w.append(wi)
        v.append(vi)
    dp=[[0 for _ in [0]*(W+1)] for _ in [0]*(N+1)]
    for i in range(1,N+1):
        for j in range(1,W+1):
            dp[i][j]=max(dp[i-1][j], dp[i][j-1])
            if w[i]<=j:dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i])
    print(dp[N][W])
if __name__=='__main__':main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def main():
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    #ps = list(map(int, input().split()))

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

    dp = [defaultdict(int)]
    dp[0][0] = 0
    for i in range(N):
        w, v = map(int, input().split())
        keys = sorted(list(dp[i].keys()))
        new_dp = defaultdict(int)
        for key in keys:
            new_dp[key] = max([new_dp[key], dp[i][key]])
            new_w = key + w
            if new_w <= W:
                new_dp[new_w] = max([new_dp[new_w], dp[i][key] + v])

        max_value = 0
        for key in sorted(new_dp.keys()):
            if max_value > new_dp[key]:
                del new_dp[key]
            else:
                max_value = new_dp[key]

        dp.append(new_dp)
    print(max(dp[N].values()))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


def sub(w, v, b):
    """重みリストw, 価値リストv, 重さ上限bのナップサックを解く
    """
    dp = [0] * (b+1)
    for i in range(len(w)):
        for j in range(b, -1, -1):
            if w[i]<=j:
                dp[j] = max(dp[j], dp[j-w[i]]+v[i])
    return dp
n,w = map(int, input().split())
ws = [None]*n
vs = [None]*n
for i in range(n):
    ws[i], vs[i] = map(int, input().split())
dp = sub(ws, vs, w)
print(dp[w])

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ 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:
n, k = 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()))


dp = []

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


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

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

Submission status: Accepted

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

import numpy as np

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

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

Submission status: Accepted

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

print(dp[n][w])

Submission status: Accepted

Solution code:
mod=10**9+7
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a,b=mi()
dp=[0]*(b+1)
for i in range(a):
  x,y=mi()
  for i in range(b-x,-1,-1):
      dp[i+x]=max(dp[i]+y,dp[i+x])
print(max(dp))

Submission status: Accepted

Solution code:
#ナップサック問題
#dp[i][w]=i番目までのお菓子で、リュックの中身の重さがw以下となる、選び方の価値の最大値

n,w=map(int,input().split())
weight=[0]
value=[0]
for i in range(n):
    f,s=map(int,input().split())
    weight.append(f)
    value.append(s)
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(w+1):
        dp[i][j]=dp[i-1][j]#選ばないときはi-1の価値を受け継ぐ
        if j-weight[i]<0:
            continue
        else:
            dp[i][j]=max(dp[i][j],dp[i-1][j-weight[i]]+value[i])
print(max(dp[n]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

for i in range(N):
    t1, t2 = map(int, input().split())
    w.append(t1)
    v.append(t2)

# Initialize dp[0]
for weight in range(W+1):
    if w[0] <= weight:
        dp[0][weight] = v[0]
    else:
        dp[0][weight] = 0

# print('dp[0]:', dp[0])

for idx in range(1, N):
    for weight in range(1, W+1):
        # Cannot select
        if weight - w[idx] < 0:
        # if weight - w[idx - 1] < 0:
            dp[idx][weight] = dp[idx - 1][weight]
            continue

        # Select
        v1 = dp[idx - 1][weight - w[idx]] + v[idx]
        # v1 = dp[idx - 1][weight - w[idx - 1]] + v[idx - 1]

        # Not Select
        v2 = dp[idx - 1][weight]

        dp[idx][weight] = max(v1, v2)

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

for i in range(N):
    t1, t2 = map(int, input().split())
    w.append(t1)
    v.append(t2)

for idx in range(1, N+1):
    for weight in range(W+1):
        if weight - w[idx - 1] < 0:
            dp[idx][weight] = dp[idx - 1][weight]
            continue

        # Select
        # v1 = dp[idx - 1][weight - w[idx]] + v[idx]
        v1 = dp[idx - 1][weight - w[idx - 1]] + v[idx - 1]

        # Not Select
        v2 = dp[idx - 1][weight]

        dp[idx][weight] = max(v1, v2)

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
from sys import stdin, gettrace
if not gettrace():
    def input():
        return next(stdin)[:-1]
 
 
# def input():
#    return stdin.buffer.readline()
def main():
    n,w=map(int,input().split())
    li=[]
    for i in range(n):
        temp=[int(x) for x in input().split()]
        li.append(temp)
    dp=[[-1 for j in range(w+1)] for i in range(n+1)]
    for i in range(n,-1,-1):
        for j in range(0,w+1,1):
            if i==n or j==0:
                dp[i][j]=0        
            elif li[i][0]>j:
                dp[i][j]=dp[i+1][j]
            else:
                dp[i][j]=max(dp[i+1][j-li[i][0]]+li[i][1],dp[i+1][j])
    print(dp[i][w])
 
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin, gettrace
import sys
sys.setrecursionlimit(1000000)
if not gettrace():
    def input():
        return next(stdin)[:-1]
 
 
# def input():
#    return stdin.buffer.readline()

def recursion(li,i,n,w,dp):
    if i==n or w==0:
        return 0
    if li[i][0]>w:
        if dp[i+1][w]==-1:
            x=recursion(li,i+1,n,w,dp)
            dp[i+1][w]=x            
        else:
            x=dp[i+1][w]
        return x
    else:
        if dp[i+1][w]==-1:
            x=recursion(li,i+1,n,w,dp)
            dp[i+1][w]=x            
        else:
            x=dp[i+1][w]
        if dp[i+1][w-li[i][0]]==-1:
            y=recursion(li,i+1,n,w-li[i][0],dp)
            dp[i+1][w-li[i][0]]=y
        else:
            y=dp[i+1][w-li[i][0]]            
        return max(li[i][1]+y,x)

def main():
    n,w=[int(x) for x in input().split()]
    li=[]
    for i in range(n):
        temp=[int(x) for x in input().split()]
        li.append(temp)
    dp=[[-1 for j in range(w+1)] for i in range(n+1)]
    print(recursion(li,0,n,w,dp))
 
 
if __name__ == "__main__":
    main()

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=W + 1, dtype=np.int64)

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

print(dp[-1])

Submission status: Accepted

Solution code:
def main():
    n, w = map(int, input().split())
    wv = [tuple(map(int, input().split())) for _ in range(n)]
    ws, vs = zip(*wv)

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

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

    res = max(dp[-1])
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!python3

LI = lambda: list(map(int, input().split()))

# input
N, W = LI()
WV = [LI() for _ in range(N)]


def main():
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        w, v = WV[i - 1]
        for j in range(W + 1):
            if j < w:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
    ans = max(dp[-1])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys;
import math;
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def get_array(): return list(map(int, sys.stdin.readline().strip().split()))
def get_string(): return sys.stdin.readline().strip()

N,W = get_ints();
arr = [];
for i in range(N):
    tarr = get_array();
    arr.append(tarr);
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(j-arr[i-1][0])>=0:
            dp[i][j]=max(dp[i-1][j],arr[i-1][1]+dp[i-1][j-arr[i-1][0]]);
        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)
for i in range(N):
    w, v = map(int, input().split())
    dp[w:] = np.maximum(dp[w:], dp[:-w] + v)

print(int(dp.max()))

Submission status: Accepted

Solution code:

def knapsack01iter(n, W, weights, values, dp):
    for i in range(1,n+1):
        for j in range(0, W+1):
            if j < weights[i-1]: # if knapsack cannot fit item i
                dp[i][j] = dp[i-1][j]
            elif j >= weights[i-1]: # knapsack can fit item i
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1])
    
    return dp[-1][-1]
    
    
n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

# repeatableKnapsack(n, W, weights, values)

# dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
# res = knapsack01rec(n, W, weights, values, dp, n, W)
# print(dp)
dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01iter(n, W, weights, values, dp)
# print(dp)
print(res)

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, lim = map(int, readline().split())
WV = np.array(read().split(), np.int64)

W = WV[::2]
V = WV[1::2]

# weight -> value
dp = np.zeros(lim + 1, np.int64)
for w, v in zip(W, V):
    np.maximum(dp[w:], dp[:-w] + v, out=dp[w:])
print(dp.max())

Submission status: Accepted

Solution code:
import numpy as np
n, targw = map(int,input().split())
w = [0 for _ in range(n)]
v = [0 for _ in range(n)]
for i in range(n):
	w[i], v[i] = map(int,input().split())
dp = np.zeros(targw+1, dtype=np.int64)
for i in range(n):
	dp[w[i]:] = np.maximum(dp[:-w[i]] + v[i], dp[w[i]:])
print(dp[targw])

Submission status: Accepted

Solution code:
"""配列の再利用,numpyの利用の練習"""

from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,datetime,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))
import numpy as np

N,W= inpl()
WV = []
for _ in range(N):
    w_v = inpl()
    WV.append(w_v)

dp = np.full(W+1,0,dtype=np.int64)
for i in range(N):
    w = WV[i][0]
    v = WV[i][1]
    np.maximum(dp[w:],dp[:W+1-w]+v,out=dp[w:])

print(np.max(dp))

Submission status: Accepted

Solution code:
def knapsack(n, W, w, v):
  dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
  for i in range(n+1):
    for j in range(W+1):
      if(i==0 or j==0):
        dp[i][j] = 0
      elif(w[i-1]<=j):
        dp[i][j] = max(v[i-1]+dp[i-1][j-w[i-1]], dp[i-1][j])
      else:
        dp[i][j] = dp[i-1][j]
  return dp[n][W]


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

Submission status: Accepted

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

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

dp = [[0]*(W+1) for i in range(N)]
#dp[i][w] indexi 番目まででwになるような価値の最大値

w = li[0][0]
if w<=W:
    dp[0][w]= li[0][1]

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

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

Submission status: Accepted

Solution code:
import sys

if __name__ == "__main__":
    n,w = map(int,input().split())
    W = []
    V = []
    for i in range(n):
        a,b = map(int,input().split())
        W.append(a)
        V.append(b)
    dp = [[0]*(w+1) for i in range(n+1)]
    for i in range(n+1):
        for j in range(w+1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif W[i-1] <= j:
                dp[i][j] = max(dp[i-1][j-W[i-1]]+V[i-1],dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]
    print(dp[-1][-1])

Submission status: Accepted

Solution code:
from collections import Counter
import math
from collections import Counter
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
##########################################################
# for i in range(int(input())):
# arr = list(map(int, input().split()))
# a,b= map(int, input().split())
import bisect
#for i in range(int(input())):
def knapSack(W, wt, val, n):
    K = [[0 for x in range(W + 1)] for x in range(n + 1)]

    # Build table K[][] in bottom up manner
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i - 1] <= w:
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
            else:
                K[i][w] = K[i - 1][w]

    return K[n][W]


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