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

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 wgt in range(1,ww+1):
            if wgt - w < 0:
                dp[i][wgt] = dp[i-1][wgt]
                continue
            dp[i][wgt] = max(dp[i-1][wgt], dp[i-1][wgt-w]+v)
            
    print(max(dp[i]))
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

for i in range(1,N+1):
    for j in range(1,W+1):
        if j-w[i]>=0:
            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:
import sys
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

input = sys.stdin.readline

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

# ---------------------------------------

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

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

Submission status: Accepted

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

for w, v in Items:
    D = DP[:]
    for i, d in enumerate(DP):
        if d < 0:
            continue
        if i + w > W:
            break
        D[i + w] = max(D[i + w], d + v)
    DP = D
print(max(DP))

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
w = [0 for i in range(N+1)]
v = [0 for i in range(N+1)]
for i in range(1, N+1):
  a, b = map(int, input().split())
  w[i] = a
  v[i] = b
dp = [[0 for j in range(W+1)] for i in range(N+1)]
for i in range(1, N+1):
  for j in range(1, W+1):
    if j - w[i] >= 0:
      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:
def main():
    N, W = map(int, input().split())
    dp = [[0]*(W + 1) for _ in range(N+1)]
    for i in range(1, N+1):
        w, v = map(int, input().split())
        for j in range(W + 1):
            if j - w < 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max([
                    dp[i-1][j-w] + v, #i番目を入れる
                    dp[i-1][j] #i番目を入れない
                ])
    print(max(dp[-1]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


# \n
def input():
    return sys.stdin.readline().rstrip()


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

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



    print(max(dp))





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
N, W = map(int, input().split())
X =[[0,0]] + [list(map(int, input().split())) for _ in range(N)]
# dp[i][j] i番目までの荷物を用いて、持ち帰る重さがj以下にするときの価値の総和の最大値
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 < X[i][0]:
      dp[i][j] = dp[i-1][j]
    else:  
      dp[i][j] = max(dp[i-1][j],dp[i-1][j-X[i][0]]+X[i][1])
print(dp[N][W])

Submission status: Accepted

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
n,w=map(int, input().split())
g=[0]
v=[0]
for i in range(n):
    G,V=map(int, input().split())
    g.append(G)
    v.append(V)

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

print(dp[n][w])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    import sys
    import numpy as np

    read = sys.stdin.read

    N, W = map(int, input().split())
    wv = np.array(read().split(), dtype=np.int64)
    w = wv[::2]
    v = wv[1::2]

    dp = np.zeros(W + 1, dtype=np.int64)
    for can_w, can_v in zip(w, v):
        dp[can_w:] = np.maximum(dp[can_w:], dp[:-can_w] + can_v)

    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    import sys
    import numpy as np

    read = sys.stdin.read

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

    dp = np.zeros(W + 1, dtype=np.int64)
    for can_w, can_v in zip(products, products):
        dp[can_w:] = np.maximum(dp[can_w:], dp[:-can_w] + can_v)

    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    import numpy as np

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

    dp = np.zeros(W + 1, dtype=np.int64)
    for can_w, can_v in products:
        dp[can_w:] = np.maximum(dp[can_w:], dp[:-can_w] + can_v)

    print(np.max(dp))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# ------------------- fast io --------------------
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")

# ------------------- fast io --------------------
from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y

def knapsack(limit, values, weights):
    """Returns the maximum value that can be reached using given weights"""
    n = len(weights)
    dp = [0]*(limit+1)
    for i in range(n):
        for j in range(limit, weights[i]-1, -1):
            dp[j] = max(dp[j], values[i] + dp[j - weights[i]])
    return dp[-1]

for _ in range(int(input()) if not True else 1):
    #n = int(input())
    n, w = map(int, input().split())
    #c, d = map(int, input().split())
    weights = []
    values = []
    for i in range(n):
        x, y = map(int, input().split())
        weights += [x]
        values += [y]

    print(knapsack(w, values, weights))

Submission status: Accepted

Solution code:
n,W = list(map(int,input().split()))
w = []
v = []
for i in range(n):
    w_,v_ = list(map(int,input().split()))
    w.append(w_)
    v.append(v_)

dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(n):
    for sum_w in range(W+1):
        dp[i+1][sum_w] = max(dp[i+1][sum_w],dp[i][sum_w])
        if sum_w-w[i]>=0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w],dp[i][sum_w-w[i]]+v[i])

print(dp[n][W])

Submission status: Accepted

Solution code:

# def solve(i,W,weight,value):
#     if i <0:
#         return 0
#     if weight[i]<=W:
#         return max(value[i]+solve(i-1,W-weight[i],weight,value),solve(i-1,W,weight,value))
#     else:
#         return solve(i-1,W,weight,value)



N,W=map(int,input().split())
weight=[]
value=[]
for i in range(N):
    n,m=map(int,input().split())
    weight.append(n)
    value.append(m)
# print(solve(N-1,W,weight,value))
dp=[[0]*(W+1) for i in range(N+1)]
for i in range(1,N+1):
    for j in range(1,W+1):
        if weight[i-1]<=j:
            dp[i][j]=max(dp[i-1][j-weight[i-1]]+value[i-1],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
    # print(dp[i])
print(dp[-1][-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
w = []
v = []
for _ in range(N):
  wi, vi = map(int, input().split())
  w.append(wi)
  v.append(vi)
dp = [[0]*(W+1) for _ in range(N+1)]
3
for i in range(N):
  for sum_w in range(W+1):
    if sum_w-w[i] >= 0:
      dp[i+1][sum_w] = max(dp[i][sum_w], dp[i][sum_w-w[i]]+v[i])
    else:
      dp[i+1][sum_w] = dp[i][sum_w]
      
print(dp[N][W])

Submission status: Accepted

Solution code:
N,W=[int(x) for x in input().split()]
w=[-1 for _ in range(N)]
v=[-1 for _ in range(N)]
for i in range(N):
	w[i],v[i]=[int(x) for x in input().split()]
#Constraints W<=10^5 w[i]<=10^5 and v[i]<=10^9
dp=[0 for _ in range(W+1)]
for i in range(N):
	for w_ in range(W,w[i]-1,-1):
		dp[w_]=max(dp[w_],dp[w_-w[i]]+v[i])
print(dp[W])
# dp[w0] stores maximum value with weight =w0 and using 1...i

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np

N, W = map(int, input().split())
knap = []

for _ in range(N):
    knap.append(tuple(map(int, input().split())))
    
dp = np.zeros((N+1, W+1), dtype=np.int64)

for i, (w, v) in enumerate(knap):
    dp[i+1] = np.maximum(dp[i+1], dp[i])
    dp[i+1][w:] = np.maximum(dp[i][w:], dp[i][:-w]+v)
       
print(dp[N][-1])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N,W=map(int,input().split())

dp=[-1]*(W+1)
dp[0]=0

for _ in range(N):
    w,v=map(int,input().split())
    for i in range(W+1)[::-1]:
        if dp[i]!=-1 and i+w<=W:
            dp[i+w]=max(dp[i+w],dp[i]+v)

print(max(dp))

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

Submission status: Accepted

Solution code:
def edu_dp_d_knapsack1():
    n, c = map(int, input().split())
    w, v = [], []
    for _ in range(n):
        a, b = map(int, input().split())
        w.append(a)
        v.append(b)
    dp = [[0] * (c + 1) for _ in range(n)]
    dp[0][w[0]] = v[0]
    for i in range(1, n):
        for j in range(0, c + 1):
            dp[i][j] = dp[i - 1][j]
            if j >= w[i]:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i])
    print(max(dp[n - 1]))
edu_dp_d_knapsack1()

Submission status: Accepted

Solution code:
n,w=map(int,input().split()) 
wt=[] 
val=[] 
for i in range(n):
	x,y=map(int,input().split()) 
	val.append(y) 
	wt.append(x) 
dp=[[0 for j in range(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 j>=wt[i-1]:
			dp[i][j]=max(dp[i-1][j],val[i-1]+dp[i-1][j-wt[i-1]]) 
		else:
			dp[i][j]=dp[i-1][j] 
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit, i8


@njit(i8(i8, i8, i8[:], i8[:]), cache=True)
def solve(N, W, weights, values):
    dp = np.full((N + 1, W + 1), 0, dtype=np.int64)
    dp[0][0] = 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 + weights[i] <= W:
                dp[i + 1][j + weights[i]] = max(
                    dp[i + 1][j + weights[i]], dp[i][j] + values[i]
                )
    return dp[-1].max()


N, W = map(int, input().split())
weights = np.zeros(N, dtype=np.int64)
values = np.zeros(N, dtype=np.int64)
for i in range(N):
    w, v = map(int, input().split())
    weights[i] = w
    values[i] = v
print(solve(N, W, weights, values))

Submission status: Accepted

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

# i番目に重さがj以下となるように選んだときの価値の総和の最大値
dp = [[0] * (w + 1) for _ in range(n)]

for i in range(0, n):
    for j in range(w + 1):
        # i 番目の品物の重さと価値
        wi, vi = data[i]
        if i == 0:
            take = vi if j - wi >= 0 else 0
            miss = 0
            dp[i][j] = max(take, miss)
        else:
            # i番目の品物を入れる場合
            take = dp[i - 1][j - wi] + vi if j - wi >= 0 else 0
            # 入れない場合
            miss = dp[i - 1][j]
            dp[i][j] = max(take, miss)

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

Submission status: Accepted

Solution code:
import numpy as np
INF = 2**60 # 無限大を表す値
N, W = map(int, input().split())
wv = [tuple(map(int, input().split())) for i in range(N)]
dp = np.full((N+1, W+1), -INF, dtype = np.int64)
dp[0][0] = 0 # 初期条件
for i, (w, v) in enumerate(wv):
    dp[i+1] = np.maximum(dp[i+1], dp[i])
    dp[i+1][w:] = np.maximum(dp[i+1][w:], dp[i][:-w] + v)
print(np.max(dp[N][:W+1]))

Submission status: Accepted

Solution code:
import numpy as np
INF = 2**60 # 無限大を表す値
N, W = map(int, input().split())
wv = [map(int, input().split()) for i in range(N)]
dp = np.full((N+1, W+1), -INF, dtype = np.int64)
dp[0][0] = 0 # 初期条件
for i, (w, v) in enumerate(wv):
    dp[i+1] = np.maximum(dp[i+1], dp[i])
    dp[i+1][w:] = np.maximum(dp[i+1][w:], dp[i][:-w] + v)
print(np.max(dp[N][:W+1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, w = list(map(int, raw_input().split()))
weights = []
values = []

for _ in range(n):
    wi, vi = list(map(int, raw_input().split()))
    weights.append(wi)
    values.append(vi)

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

print(dp[n][w])

Submission status: Accepted

Solution code:
n,w = map(int,input().split())
wait = [""]*n
value = [""]*n
for i in range(n):
    wait[i],value[i] = map(int,input().split())
# print(wait,value)

# dp[i][j]=(i番目までの品物を、重さがj以下になるように選んだときの価値の最大値)を考える
# dp[i][j]は、
# i番目の品物を使うとき      i−1番目までで重さが(j − w[i])以下の価値の最大値 + v[i]
#              使わないとき  i−1番目までの重さがj以下の価値の最大値

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

for i in range(1,n+1):
    for j in range(0,w+1):
        # print(j-wait[i-1])
        if(j-wait[i-1]>= 0):
            knapsak[i][j] = max(knapsak[i-1][j],knapsak[i-1][j-wait[i-1]]+value[i-1])
            # print(knapsak)
        else:
            knapsak[i][j] = knapsak[i-1][j]
print(knapsak[n][w])

Submission status: Accepted

Solution code:
#問題D
#これだとタイムアウト
import numpy as np
import warnings
warnings.filterwarnings('ignore')

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

dp = np.array([[0] * (W+1)] * (N+1))
for i in range(1, N+1):
    tmp_arr = np.zeros(W + 1, dtype=int)
    tmp_arr = np.zeros(W + 1, dtype=int)
    tmp_arr[w[i]:] = dp[i-1][:-w[i]] + v[i]
    dp[i] = np.maximum(dp[i-1], tmp_arr)

print(dp[N, W])

Submission status: Accepted

Solution code:
def num():
    x, y = map(int, input().split())
    dp = [0]*(y+1)

    for i in range(x):
        w, v = map(int, input().split())
        for j in range(y, w-1, -1):
            num = dp[j-w]+v
            if num > dp[j]:
                dp[j] = num
    print(dp[-1])

num()

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
w,v=[],[]
for _ in range(N):
  aw,V=map(int,input().split())
  w.append(aw)
  v.append(V)
dp=[[0 for _ in range(W+1)] for _ in range(N)]
#print(dp)
for i in range(N):
  for j in range(W+1):
    if j-w[i]>=0:
      #print(dp[i-1][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[-1][-1])

Submission status: Accepted

Solution code:
# D - Knapsack 1
N,W = map(int,input().split())
value = []
weight = []
for _ in range(N):
    w,v = map(int,input().split())
    value.append(v)
    weight.append(w)

# DP テーブル
# dp[i][j]: i-1 番目までの品物から重さが j を超えないように選んだときの価値の最大値
# W <= 100000, N <= 100 よりテーブルの個数を決める
dp = [[0]*100010 for _ in range(102)]

# DP テーブル全体を初期化
for i in range(102):
    for j in range(100010):
        dp[i][j] = 0# 最大化問題

# DP ループ
# v-1 番目の荷物に対する情報を dp[v] に記録
for v in range(1,N+1):
    for w in range(W+1):
        # v-1 番目の品物を選ぶ場合
        if (w - weight[v-1]) >= 0:
            dp[v][w] = max(dp[v][w],dp[v-1][w - weight[v-1]] + value[v-1])
        # v-1 番目の品物を選ばない場合
        dp[v][w] =  max(dp[v][w],dp[v-1][w])
        
# 価値の総和の最大値を出力
print(dp[N][W])

Submission status: Accepted

Solution code:
import numpy as np
def main():
    N,W = map(int,input().split())
    w,v = [],[]
    for _ in range(N):
        w_,v_ = map(int,input().split())
        w.append(w_)
        v.append(v_)

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

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

Submission status: Accepted

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

Submission status: Accepted

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

#vもwもdpも全て1-indexedみたいにした。わかりやすいので。
v=[0]*(N+1)
w=[0]*(N+1)
for i in range(1,N+1):
  w_i,v_i=map(int,input().split())
  w[i]=w_i
  v[i]=v_i


dp=[[0]*(W+1) for i in range(N+1)] #初期化もこの段階で済んでいる

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

print(dp[N][W])

Submission status: Accepted

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

print(solve())

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

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

print(dp.max())

Submission status: Accepted

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

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

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:
import numpy as np

N, W = map(int, input().split())
w = np.empty(N, dtype = np.int64)
v = np.empty(N, dtype = np.int64)
for i in range(N):
	w[i], v[i] = map(int, input().split())

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

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

print(dp.max())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
"""
n, k = [int(i) for i in input().split(' ')]

arr = [int(i) for i in input().split(' ')]

dp = [10**10]*n

k += 1
dp[0] = 0

for i in range(0, n):
    for j in range(1, k):
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i] + abs(arr[i+j]-arr[i]))

print(dp[n-1])
n = int(input())

a = [int(i) for i in input().split(' ')]

for i in range(1, n):
    new_a = [int(i) for i in input().split(' ')]
    new_a[0] = max(new_a[0]+a[1], new_a[0]+a[2])
    new_a[1] = max(new_a[1]+a[0], new_a[1]+a[2])
    new_a[2] = max(new_a[2]+a[1], new_a[2]+a[0])
    a, new_a = new_a, a

print(max(a))
"""

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

dp = [0]*(W+1)

for _ in range(n):
    curwt, val = [int(i) for i in input().split(' ')]
    for wt in range(W-curwt, -1, -1):
        dp[wt+curwt] = max(dp[wt+curwt], dp[wt]+val)

print(max(dp))

Submission status: Accepted

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

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

for w in range(1, W+1):
	for i in range(1, N+1):
		# take one
		if D[i-1][0] <= w:
			dp[w][i] = max(dp[w][i-1], dp[w-D[i-1][0]][i-1] + D[i-1][1])
		# ignore
		dp[w][i] = max(dp[w][i], dp[w][i-1])

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

Submission status: Accepted

Solution code:
def knapsack_weight(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    """ dp[weight <= W] = 重さ上限を固定した時の最大価値 """
    dp_min = 0  # 総和価値の最小値
    dp = [dp_min] * (W + 1)

    for item in range(N):
        S = range(W, weight_list[item] - 1, -1)
        for weight in S:
            if dp[weight] < dp[weight - weight_list[item]] + price_list[item]:
                dp[weight] = dp[weight - weight_list[item]] + price_list[item]
    return dp[W]

import sys
input = sys.stdin.readline  

N, W = map(int, input().split())                                # N: 品物の種類 W: 重量制限
 
price_list = []
weight_list = []
for _ in range(N):
    weight, price = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)
 
print(knapsack_weight(single=True))

Submission status: Accepted

Solution code:
def knapsack_weight(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    """ dp[weight <= W] = 重さ上限を固定した時の最大価値 """
    dp_min = 0  # 総和価値の最小値
    dp = [dp_min] * (W + 1)

    for item in range(N):
        if single:
            S = range(W, weight_list[item] - 1, -1)
        else:
            S = range(weight_list[item], W + 1)
        for weight in S:
            if dp[weight] < dp[weight - weight_list[item]] + price_list[item]:
                dp[weight] = dp[weight - weight_list[item]] + price_list[item]
    return dp[W]

N, W = map(int, input().split())                                # N: 品物の種類 W: 重量制限
 
price_list = []
weight_list = []
for _ in range(N):
    weight, price = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)
 
print(knapsack_weight(single=True))

Submission status: Accepted

Solution code:
import numpy as np

n,wmax = 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((n+1, wmax+1))

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

print(int(dp.max()))

Submission status: Accepted

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

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

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

ans = 0
for i in range(1,n+1):
    ans = max(ans, max(dp[i]))
print(ans)

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
P=[]
for _ in range(n):
  iw,iv=map(int,input().split())
  P.append([iw,iv])
INF=float('inf')

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

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

Submission status: Accepted

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

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

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

ans = 0
for i in range(n+1):
    ans = max(ans, max(dp[i]))
print(ans)

Submission status: Accepted

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

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
def inpl(): return list(map(int,input().split()))
 
N, W = inpl()
dp = [[0]*(W+1) for _ in range(N+1)]
for n in range(1,N+1):
  w, v = inpl()
  for x in range(W+1):
    if x < w:
      dp[n][x] = dp[n-1][x]
    else:
      dp[n][x] = max(dp[n-1][x], dp[n-1][x-w] + v)
print(dp[-1][-1])

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
cost=[[0 for i in range(w+1)] for j in range(n+1)] #DP配列です
value=[tuple(map(int,input().split())) for i in range(n)]#品物の情報を受けとります
for i in range(1,n+1):
  for j in range(w+1):
    weight_=value[i-1][0] #i-1番目の品物の重さ
    value_=value[i-1][1] #i-1番目の品物の価値
    if j < weight_:
      cost[i][j]=cost[i-1][j]
    else:
      cost[i][j]=max(cost[i-1][j-weight_]+value_,cost[i-1][j])
print(cost[n][w])