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:
# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

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


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")


# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input


def out(var): sys.stdout.write(str(var))  # for fast output, always take string


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  # as stdout.write always print sring.


def testcase(t):
    for p in range(t):
        solve()


from random import randint

from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count



def ifvalid(i):
    if i<0:
        return False
    return True


def solve():
    n,W=sep()
    ar=[]
    for _ in range(n):
        ar.append(lis())
    dp=[[-1 for i in range(W+5)] for _ in range(n+5)]
    for j in range(0,ar[0][0]):
        dp[0][j]=0
    for j in range(ar[0][0],W+1):
        dp[0][j]=ar[0][1]
    for i in range(1,n):
        for w in range(W+1):
            if ifvalid(w-ar[i][0]):
                dp[i][w]=max(dp[i-1][w],dp[i-1][w-ar[i][0]]+ar[i][1])
            else:
                dp[i][w]=dp[i-1][w]
    print(dp[n-1][W])








solve()

Submission status: Accepted

Solution code:
def solve(ar_w,ar_v,n,w):
    dp = [[0] * (w+1) for _ in range(n+1)]

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


    print(dp[n][w])


if __name__ == '__main__':
    n,w = map(int,input().split())
    ar_w = [0]
    ar_v = [0]
    for i in range(n):
        a,b = map(int,input().split())
        ar_w.append(a)
        ar_v.append(b)

    solve(ar_w,ar_v,n,w)

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(w):
	dp[0][i]=0
for i in range(n):
	dp[i][0]=0
l=[]
for k in range(n):
	l.append(list(map(int,input().split())))

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

Submission status: Accepted

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

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

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

m = 0
for i in range(N + 1):
    m = max(m, max(dp[i]))

print(m)

Submission status: Accepted

Solution code:
import numpy as np

n,W=list(map(int,input().split()))

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

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

Submission status: Accepted

Solution code:
def solve():
    #start here
    n, W = map(int,input().split())
    l = []
    dp = [[0 for i in range(W+1)] for j in range(n)]
    for i in range(n):
        w, v = map(int,input().split())
        for j in range(1, W+1):
            if(w>j):
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], v+dp[i-1][j-w])
    print(dp[n-1][W])
solve()

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
w, v = [0], [0]
for i in range(N):
    w_i, v_i = map(int, input().split())
    w.append(w_i)
    v.append(v_i)
DP = [[0 for c in range(W+1)] for i in range(N+1)]
for i in range(1, N+1):
    for c in range(1, W+1):
        if c - w[i] < 0:
            DP[i][c] = DP[i-1][c]
        else:
            DP[i][c] = max(DP[i-1][c], DP[i-1][c-w[i]] + v[i])
print(DP[N][W])

Submission status: Accepted

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

# Input#
# n = int(input())
n, tar_w = map(int, input().split())

w = [-1]
v = [-1]

memo = [[-1] * (tar_w + 1) for i in range(n + 1)]

for i in range(tar_w + 1):
    memo[0][i] = 0


def dp(n, tar_w):
    if memo[n][tar_w] == -1:
        if tar_w < w[n]:
            memo[n][tar_w] = dp(n - 1, tar_w)
        else:
            memo[n][tar_w] = max(dp(n - 1, tar_w), dp(n - 1, tar_w - w[n]) + v[n])
    return memo[n][tar_w]


for i in range(n):
    w_in, v_in = list(map(int, input().split()))
    w.append(w_in)
    v.append(v_in)


ans = dp(n, tar_w)

print("{}".format(ans))

Submission status: Accepted

Solution code:
import numpy as np
[N,W]=[int(x) for x in input().split()]
dp=np.zeros([N+1,W+1],dtype=int)
for i in range(1,N+1):
  w, v=map(int,input().split())
  dp[i][:w]=dp[i-1][:w]
  dp[i][w:]=np.maximum(dp[i-1][w:],dp[i-1][:W-w+1]+v)
print(dp[N][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 _ in range(N+1)]

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

Submission status: Accepted

Solution code:
n,w = [int(x) for x in input().split()]
wts = []
vals = []
for i in range(n):
    wi,vi = [int(x) for x in input().split()]
    wts.append(wi)
    vals.append(vi)

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

for j in range(w+1):
    if j>=wts[0]:
        dp[0][j] = vals[0]

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

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

Submission status: Accepted

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

import numpy as np

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

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

print(dp[-1])

Submission status: Accepted

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

import numpy as np

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

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

print(dp[-1])

Submission status: Accepted

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

import numpy as np

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

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

print(dp.max())

Submission status: Accepted

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

import numpy as np

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

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

print(dp.max())

Submission status: Accepted

Solution code:
import numpy as np

N,W = map(int,input().split())
wv = np.array([list(map(int,input().split())) for _ in range(N)])
dp=np.zeros([N+1,W+1])

#　繰り返し回数節約
for i in range(1,N+1):
    dp[i][:wv[i-1][0]] = dp[i-1][:wv[i-1][0]]
    dp[i][wv[i-1][0]:] = np.maximum(dp[i-1][wv[i-1][0]:],dp[i-1][:W+1-wv[i-1][0]]+wv[i-1][1])
print(int(dp[-1,-1]))

Submission status: Accepted

Solution code:
import numpy as np

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

dp = np.zeros(W+1, 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:
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())
w=[0]+w
v=[0]+v
dp=[[0 for i in range(N+1)] for j in range(W+1)]

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


from numba import njit
import numpy as np


N, K = ints()
W, V = read_col(N)
W = np.array(W, dtype=np.int64)
V = np.array(V, dtype=np.int64)


@njit('(i8,i8,i8[:],i8[:])', cache=True)
def main(N, K, W, V):
    dp = np.zeros((N + 1, K + 1), dtype=np.int64)
    for i in range(N + 1):
        dp[i, 0] = 0

    for i in range(N):
        w, v = W[i], V[i]
        for sum_w in range(K + 1):
            if sum_w - w < 0:
                dp[i + 1, sum_w] = dp[i, sum_w]
            else:
                dp[i + 1, sum_w] = max(
                    dp[i, sum_w],
                    dp[i, sum_w - w] + v)
    print(dp[-1, -1])


main(N, K, W, V)

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:
import sys
read = sys.stdin.readline


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


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def main():
    N, K = read_ints()

    dp = [[-10 for _ in range(K + 1)] for _ in range(N + 1)]

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

    for i in range(N):
        w, v = read_ints()
        for sum_w in range(K + 1):
            if sum_w - w < 0:
                dp[i + 1][sum_w] = dp[i][sum_w]
            else:
                dp[i + 1][sum_w] = max(
                    dp[i][sum_w],
                    dp[i][sum_w - w] + v)
    print(dp[-1][-1])


main()

# pythonでもpypyでもTLE

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main(N, W, P):
    dp = [[0]*(W + 1) for _ in range(N)]
    for j in range(P[0][0], W+1):
        dp[0][j] = P[0][1]

    for i in range(1, N):
        for j in range(1, W + 1):
            if j - P[i][0] < 0:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                continue

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

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

if __name__ == "__main__":
    N, W = map(int, input().split()) #N個の製品、Wの制限
    P = [tuple(map(int, input().split())) for _ in range(N)]
    main(N, W, P)

Submission status: Accepted

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

Submission status: Accepted

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

# 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(0, W + 1):
        # i番目のアイテムを入れることができる場合
        if j - wv[i][0] >= 0:
            # 実際にアイテムを入れる場合、入れない場合
            dp[i][j] = max(dp[i - 1][j - wv[i][0]] + wv[i][1], dp[i - 1][j])
        # i番目のアイテムを入れることができない場合
        else:
            dp[i][j] = dp[i - 1][j]

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

Submission status: Accepted

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


dp=[0]*(w+1)

for i in range(n):
    nextdp=[]
    x=[int(i) for i in input().split()]
    for j in range(w+1):
        if x[0] > j:
            nextdp.append(dp[j])
        else:
            nextdp.append(max(dp[j],dp[j-x[0]]+x[1]))
    dp=nextdp

print(max(dp))

Submission status: Accepted

Solution code:
n,w = list(map(int,input().split(' ')))
w_arr = [None]*(n+1)
v_arr = [None]*(n+1)
for i in range(1,n+1):
    w_arr[i],v_arr[i] = list(map(int,input().split(' ')))

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

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

Submission status: Accepted

Solution code:
import math

n, W = map(int, input().split())
dp = [0]*(W+1)
for i in range(n):
    weight, cost = map(int, input().split())
    for weight_already in range(W-weight, -1, -1):
        dp[weight_already+weight] = max(dp[weight_already+weight], dp[weight_already]+cost)
ans = max(dp)
print(ans)

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:
import math

n, w = map(int, input().split())
weights = []
costs = []
for i in range(n):
    a,b = map(int, input().split())
    weights.append(a)
    costs.append(b)
dp = [[0 for i in range(w+1)] for i in range(n)]
for i in range(w+1):
    if(i>= weights[0]):
        dp[0][i] = costs[0]

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

Submission status: Accepted

Solution code:
import sys
 
input = sys.stdin.readline
 
 
def main():
    N, W = map(int, input().split())
    wv = [None] * N
    for i in range(N):
        wv[i] = tuple(map(int, input().split()))
 
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i, (w, v) in enumerate(wv, start=1):
        dp_i = dp[i]
        dp_im = dp[i - 1]
        for j in range(1, W + 1):
            if j < w:
                dp_i[j] = dp_im[j]
            else:
                a = dp_im[j - w] + v
                b = dp_im[j]
                if a > b:
                    dp_i[j] = a
                else:
                    dp_i[j] = b
 
    ans = dp[-1][-1]
    print(ans)
 
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
import itertools


# \n


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, WW = map(int, input().split())

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

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
import itertools


# \n


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, WW = map(int, input().split())
    W = []
    V = []
    for i in range(N):
        w, v = map(int, input().split())
        W.append(w)
        V.append(v)

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

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    item_count, capacity = [int(x) for x in input().split()]
    weights, values = [], []
    for _ in range(item_count):
        w, v = [int(x) for x in input().split()]
        weights.append(w)
        values.append(v)
    # dp[i][j]
    # = (i番目までの品物を、重さがj以下になるように選んだときの価値の最大値)
    dp = [[0] * (capacity + 1) for _ in range(item_count)]
    for item_i in range(item_count):
        for weight_i in range(1, capacity + 1):
            w = weights[item_i]
            if w <= weight_i:
                dp[item_i][weight_i] = max(
                    dp[item_i - 1][weight_i - w] + values[item_i],
                    dp[item_i - 1][weight_i])
            else:
                dp[item_i][weight_i] = dp[item_i - 1][weight_i]
    print(dp[item_count - 1][capacity])


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 for i in range(N+1)] for j in range(W+1)] 
for n in range(1,N+1):
    for e in range(1,W+1):
        if e-w[n-1]>=0:
            dp[e][n]=max(dp[e][n-1],dp[e-w[n-1]][n-1]+v[n-1])
        else:
            dp[e][n]=dp[e][n-1]
#print(dp)
print(dp[-1][-1])

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

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

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
dp=[0]*(W+1)
dd=dp.copy()
for i in range(n):
	w,v=map(int,input().split())
	for j in range(W):
		cw=j+w
		cv=dp[j]+v
		if cw <=W and dd[cw]<cv:
			dd[cw]=cv
	dp=dd.copy()
print(dp[W])

Submission status: Accepted

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

w_list = [0] * n
v_list = [0] * n
for i in range(n):
    w_list[i], v_list[i] = map(int, input().split())

dp = [0] * (w + 1)
for i in range(n):
    for j in range(w, -1, - 1):
        v = dp[j] + v_list[i]
        if j + w_list[i] <= w and dp[j + w_list[i]] < v:
            dp[j + w_list[i]] = v
print(dp[-1])

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
w_v = [list(map(int, input().split())) for _ in range(n)]
#import numpy as np
dp = [[0]*(w+1) for _ in range(n+1)]
for i in range(n):
    for j in range(w+1):
        dp[i+1][j] = max(dp[i][j], dp[i+1][j])
        if j-w_v[i][0] >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-w_v[i][0]] + w_v[i][1])

    
print(dp[n][w])

Submission status: Accepted

Solution code:
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 _ in range(N + 1)]

if w[1] == 1:
    dp[1][1] = v[1]

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

print(dp[N][W])

Submission status: Accepted

Solution code:
from sys import stdin, stdout
import numba as nb 

@nb.njit()
def solve(n,w,weights, values):
	dp = [[0 for _ in range(w+1)] for k in range(n+1)]
	for i in range(1,n+1):
		for j in range(1,w+1):
			if weights[i] <= j:
				dp[i][j] = max(dp[i-1][j],
			   	dp[i-1][j-weights[i]] + values[i])
			else:
				dp[i][j] = dp[i-1][j]
	return dp[n][w]

def main():
	n, w = map(int,stdin.readline().split())
	values = []
	weights = []

	for _ in range(n):
		v,a = map(int, stdin.readline().split())
		values.append(a)
		weights.append(v)

	values = [0] + values
	weights = [0] + weights
	print(solve(n,w,weights,values))

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import copy
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)
tmp_dp = [0] * (W+1)
for i in range(N):
    tmp_dp = copy.copy(dp)
    for j in range(W):
        if dp[j] != 0:
            if j + w[i] <= W:
                if dp[j + w[i]] < tmp_dp[j] + v[i]:
                    dp[j + w[i]] = tmp_dp[j] + v[i]
    if dp[w[i]] < v[i]:
        dp[w[i]] = v[i]
print(max(dp))

Submission status: Accepted

Solution code:
import sys

import numpy as np

input = sys.stdin.readline


def main():
    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 = np.zeros(shape=(N + 1, W + 1), dtype=np.int64)
    for i, (w_, v_) in enumerate(zip(w, v)):
        dp[i + 1] = dp[i]
        dp[i + 1, w_:] = np.maximum(dp[i, w_:], dp[i, :W + 1 - w_] + v_)

    ans = np.max(dp[-1])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, W = map(int, input().split())
    
    dpt = [0] * (W+1)
    
    for i in range(N):
        w, v = map(int, input().split())
        for j in range(W, w-1, -1):
            a = dpt[j]
            b = dpt[j-w]+v
            if a > b:
                dpt[j] = a
            else:
                dpt[j] = b
    
    print(dpt[W])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:


INF = float('inf')


def tc():
    n, cap = map(int, input().split())

    # dp[i]: max total value with weights exactly i
    dp = [0] * (cap + 1)

    for i in range(n):
        w, v = map(int, input().split())
        for prev_w in reversed(range(cap - w + 1)):
            dp[prev_w + w] = max(dp[prev_w + w], dp[prev_w] + v)

    ans = max(dp)
    print(ans)


tc()

Submission status: Accepted

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

# dp[i][j]:i番目の品物までから重さj（以下）になるようにモノを詰めた時の価値の最大
# 配ってみるのはダルいからまずは普通に貰ってみる

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

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

Submission status: Accepted

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

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, W = in_nn()
    wv = in_nl2(N)

    dp = [0] * (W + 1)

    for i in range(N):

        next_dp = copy(dp)
        for j in range(W):
            w, v = wv[i]
            if j + w <= W:
                next_dp[j + w] = max(next_dp[j + w], dp[j] + v)
            else:
                break
        dp = next_dp

    print(dp[W])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

print(dp.max())

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for _ in range(N)]
dp=[[0]*W for _ in range(N)]
for n in range(N):
    if n==0:
        for j in range(WV[0][0]-1,W):
          dp[n][j]=WV[0][1]
    else:
        for j in range(W):
            if (j-WV[n][0])>=0:
                dp[n][j]=max(dp[n-1][j-WV[n][0]]+WV[n][1],dp[n-1][j])
            else:
                dp[n][j]=dp[n-1][j]
print(dp[N-1][W-1])

Submission status: Accepted

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

dp = [[0]*(W+1) for j in range(N+1)] # DPテーブルの作成

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())
wi=[]
vi=[]

for i in range(n):
  a,b=map(int,input().split())
  wi+=[a]
  vi+=[b]
  
dp=[[0]*(w+1) for i in range(n+1)]

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

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(n)]

dp = [[0]*(w+8) for _ in range(n+10)]
weight = [0] * (n)
value = [0] * (n)

for i in range(n):
    weight[i] = li[i][0]
    value[i] = li[i][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])

print(dp[n][w])