Problem:


Score : 100 points

Problem Statement

There are N items, numbered 1, 2, \ldots, N.
For each i (1 \leq i \leq N), Item i has a weight of w_i and a value of v_i.

Taro has decided to choose some of the N items and carry them home in a knapsack.
The capacity of the knapsack is W, which means that the sum of the weights of items taken must be at most W.

Find the maximum possible sum of the values of items that Taro takes home.

Constraints

All values in input are integers.

1 \leq N \leq 100

1 \leq W \leq 10^5

1 \leq w_i \leq W

1 \leq v_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

Print the maximum possible sum of the values of items that Taro takes home.

Sample Input 1

3 8
3 30
4 50
5 60

Sample Output 1

90

Items 1 and 3 should be taken.
Then, the sum of the weights is 3 + 5 = 8, and the sum of the values is 30 + 60 = 90.

Sample Input 2

5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

Sample Output 2

5000000000

The answer may not fit into a 32-bit integer type.

Sample Input 3

6 15
6 5
5 6
6 4
6 6
3 5
7 2

Sample Output 3

17

Items 2, 4 and 5 should be taken.
Then, the sum of the weights is 5 + 6 + 3 = 14, and the sum of the values is 6 + 6 + 5 = 17.



Sample input:
3 8
3 30
4 50
5 60


Sample output:
90

Submission status: Accepted

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


def chmax(x, w1, w2, diff):
    if dp[x][w1] < dp[x-1][w2]+diff:
        dp[x][w1] = dp[x-1][w2]+diff
        return True
    return False


dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
    for sum_w in range(W+1):
        # 貰うDP
        if sum_w-wvs[i][0] >= 0:
            # 品物を選んだ場合(選ぶために必要な重さを減らした状態に価値を追加した状態と比較)
            chmax(i+1, sum_w, sum_w-wvs[i][0], wvs[i][1])
        chmax(i+1, sum_w, sum_w, 0)  # 品物を選んでない場合
print(max(dp[N]))

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]
 
dp = [[0 for _ in range(W+10)] for _ in range(N+10)]
 
for i, (item_weight, item_value) in enumerate(items):
    for total_weight in range(W+1):
        if (total_weight-item_weight) >= 0:
            dp[i+1][total_weight] = dp[i][total_weight-item_weight] + item_value
        dp[i+1][total_weight] = max(dp[i+1][total_weight], dp[i][total_weight])
        
print(dp[N][W])

Submission status: Accepted

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

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

for i, (item_weight, item_value) in enumerate(items):
    for total_weight in range(W+1):
        if (total_weight-item_weight) >= 0:
            dp[i+1][total_weight] = max(dp[i][total_weight-item_weight] + item_value, dp[i+1][total_weight])
        dp[i+1][total_weight] = max(dp[i+1][total_weight], dp[i][total_weight])
        
print(dp[N][W])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import numpy as np

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

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

for _ in range(N):
    w, v = map(int, input().split())  # 重さw, 価値vの荷物
    np.maximum(dp[:-w]+v, dp[w:], out=dp[w:])  # dp[:-w]はまだ重さwのもの入るナップサックの状態
    # outは戻り値を格納する配列を指定できる

print(dp[-1])


"""
今dpは一次元配列
dp[:-w]は後ろからw個より前の要素, つまり(N-w)個
dp[w:]は前からw個より後ろの要素, つまり(N-w)個
よって形状が一致する
"""

"""
dp[:-w]は今見ている"重さw, 価値v"の荷物を入れることのできる状態のナップサック
dp[:-w]+vをすることで、今見ているその荷物を入れた時の価値の総和になる.
今、"重さw, 価値v"の荷物を入れたナップサックと、dp[w:]を比較する。
それぞれの要素について大きい方が新しい要素となり、out=dp[w:]によって上書きされる。
maxmimumが返すのはnp配列。そのnp配列の形状は比較対象となっている配列の形状と一致するから、
問題なく上書きできる
"""

Submission status: Accepted

Solution code:
def knapsack(N,W,weight,value):
  #初期化
  inf=float("inf")
  dp=[[-inf for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0

  #DP
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
        dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
      else: #入る可能性はない
        dp[i+1][w]=dp[i][w]
  return dp[N][W]

N,W = map(int,input().split())
lstw = [0 for i in range(N)]
lstv = [0 for i in range(N)]

for i in range(N):
  w,v = map(int, input().split() ) 
  lstw[i] = w
  lstv[i] = v
  
ret = knapsack(N,W,lstw,lstv)
  
print(ret)

Submission status: Accepted

Solution code:
import numpy as np
import sys

N, W = [int(v) for v in input().strip().split(' ')]
dp = np.zeros(W + 1, dtype = 'uint64')

for _ in range(N):
    w, v = [int(v) for v in sys.stdin.readline().split(' ')]
    np.maximum(dp[:-w] + v, dp[w:], out = dp[w:])

print(dp[W])

Submission status: Accepted

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

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

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

res = dp[N][W]
print(res)

Submission status: Accepted

Solution code:
def main():

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

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

    max_v = 0
    for i in range(N):
        w, v = map(int, input().split())
        for j in range(W+1):
            if j - w >= 0:
                dp[(i+1)%2][j] = max(dp[i%2][j], dp[i%2][j-w]+v)
            else:
                dp[(i+1)%2][j] = dp[i%2][j]
        max_v = max(max(dp[(i+1)%2]), max_v)

    return max_v

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
def main():

    N, W = map(int, input().split())
    cur = dict()
    cur[0] = 0
    for _ in range(N):
        w, v = map(int, input().split())
        temp = cur.copy()
        for w1 in temp:
            if w1 + w <=W:
                if w1+w not in cur:
                    cur[w1+w] = temp[w1] + v
                else:
                    cur[w1+w] = max(cur[w1+w], temp[w1]+v)
    return max(cur.values()) 


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
def A(w, v, n,V):
    mem=[0 for i in range(V+1)]
    if n == 0 or V == 0:
        return 0
 
    for i in range(n):
        for j in range(V,w[i]-1,-1):
            m=v[i]+ mem[j - w[i]]
            if m>mem[j]:
                mem[j]=m
    return mem[V]
n,V=input().split()
n,V=int(n),int(V)
 
w=[0]*n
v=[0]*n
for i in range(n):
  x,y=input().split()
  w[i],v[i]=int(x),int(y)
 
print(A(w,v,n,V))

Submission status: Accepted

Solution code:
from collections import defaultdict

n, w = [int(x) for x in input().split()]
d = []
for _ in range(n):
    ww, nu = [int(x) for x in input().split()]
    d.append((ww, nu))

# dd[idx][ww] represents the maximum value that  we can get if total weight <= ww
# and allowed to use the first idx items.
dd = defaultdict(lambda: defaultdict(int))
for ww in range(w+1):
    dd[0][ww] = 0

for nn in range(n+1):
    dd[nn][0] = 0

for nn in range(1, n+1):
    www, nu = d[nn-1]
    for ww in range(1, w+1):
        # don't use item nn-1
        cur = dd[nn-1][ww]

        # use item nn-1
        if www <= ww:
            rem_ww = ww - www
            cand = dd[nn-1][rem_ww] + nu
            if cand > cur:
                cur = cand

        dd[nn][ww] = cur

print(dd[n][w])

Submission status: Accepted

Solution code:
N, capW = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]
 
def knapsack01(items, capW):
    dp = [0] * (capW+1)
    for wi, vi in items:
        for w in reversed(range(wi, capW+1)):
            v0 = dp[w-wi] + vi
            if v0 > dp[w]:
                dp[w] = v0
    return max(dp)
 
print(knapsack01(items, capW))

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
values=[[0]*(w+1) for i in range(n+1)]
# print(values)
for i in range(n):
    values[i+1][wv[i][0]]=max(values[i+1][wv[i][0]],wv[i][1])
    for j in range(1,w+1):
        if values[i][j]!=0:
            if wv[i][0]+j<=w:
                values[i+1][wv[i][0]+j]=max(values[i+1][wv[i][0]+j],values[i][j]+wv[i][1])
            values[i+1][j]=max(values[i+1][j],values[i][j])

print(max(values[-1]))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
N,W = list(map(int, input().split()))
m = []
v = []
dp = [[0 for i in range(W+1)]for j in range(N+1)]
for i in range(N):
    a,b = map(int, input().split())
    m.append(a)
    v.append(b)

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


print(max(dp[-1]))

Submission status: Accepted

Solution code:
N,W = list(map(int, input().split()))
v = []
m = []
dp = [[-1 for i in range(W+1)]for j in range(N+1)]
for i in range(N):
    a,b = list(map(int, input().split()))
    m.append(a)
    v.append(b)

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wv = [[int(i) for i in 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 >= wv[i][0] :
            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:
N, capW = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]

def knapsack01(items, capW):
    dp = [0] * (capW+1)
    for wi, vi in items:
        dp = [v1 if v1 >= v2 else v2 for v1, v2 in zip(dp, [0]*wi + [v+vi for v in dp[:capW-wi+1]])]
    return max(dp)

print(knapsack01(items, capW))

Submission status: Accepted

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

def knapsack01(items, capW):
    dp = [0] * (capW+1)
    for wi, vi in items:
        for w in reversed(range(wi, capW+1)):
            v0 = dp[w-wi] + vi
            if v0 > dp[w]:
                dp[w] = v0
    return max(dp)

print(knapsack01(items, capW))

Submission status: Accepted

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

#dp[i個目までの品物][総和がw以下]
dp=[[0]*(W+1) for _ in range(N+1)]

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

print(dp[N][W])

Submission status: Accepted

Solution code:
nums, weight = map(int,input().split())
ary  = [0 for i in range(nums)]
for i in range(nums):
    ary[i] = list(map(int,input().split()))
dp =[[0 for i in range(weight+1)]for i in range(nums+1)]
 
check = 0
for i in range(nums):
    for x in range(weight+1):
        if x - ary[i][0] >= 0:
            check = dp[i][x -ary[i][0]] + ary[i][1]
            if check > dp[i+1][x]:
                dp[i+1][x] = check
 
        check = dp[i][x]
        if check > dp[i+1][x]:
            dp[i+1][x] = check
 
print(dp[nums][weight])

Submission status: Accepted

Solution code:
n,tw = map(int, input().split())
wt = [];    val = []
for i in range(n):
    a,b = map(int, input().split())
    wt.append(a);   val.append(b)
dp = [[0 for i in range(tw+1)] for j in range(n+1)]
for i in range(n):
    for j in range(1,tw+1):
        if j < wt[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], val[i]+dp[i][j-wt[i]])
print(dp[n][tw])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main2(): 
    N, W = LI()
    things = []
    for i in range(N):
        things.append(LI())

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

    for i, wv in enumerate(things):  # 10**2
        w, v = wv
        if i == 0:
            for weight in range(W+1):  # 10**5
                knapsack_dp[i][weight] = 0 if weight < w else v
        else:
            for weight in range(W+1):
                if weight-w < 0:
                    knapsack_dp[i][weight] = knapsack_dp[i-1][weight]
                else:
                    knapsack_dp[i][weight] = max(knapsack_dp[i-1][weight], knapsack_dp[i-1][weight-w]+v)

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

def main():
    N, W = LI()
    things = []
    for i in range(N):
        things.append(LI())

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

    # knapsack_dp[考慮した品物][その重さピッタリの重さ] = 価値 とする。
    for i, wv in enumerate(things):  # 10**2
        w, v = wv
        if i == 0:
            for weight in range(W+1):  # 10**5
                knapsack_dp[i][weight] = 0 if weight != w else v
        else:
            for weight in range(W+1):
                if weight-w < 0:
                    knapsack_dp[i][weight] = knapsack_dp[i-1][weight]
                else:
                    knapsack_dp[i][weight] = max(knapsack_dp[i-1][weight], knapsack_dp[i-1][weight-w]+v)

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

main()

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
wv = [[int(x) for x in input().split()] for i in range(N)]
dp = [[0 for j in range(W+1)] for i in range(N+1)]
for i in range(N):
    for sum_w in range(W+1):
        if wv[i][0] + sum_w < W+1 and dp[i+1][wv[i][0]+sum_w] < dp[i][sum_w] + wv[i][1]:
            dp[i+1][wv[i][0]+sum_w] = dp[i][sum_w] + wv[i][1] #dp[i][weight_i + sum_weight]
        if dp[i+1][sum_w] < dp[i][sum_w]:
            dp[i+1][sum_w] = dp[i][sum_w]
print(dp[N][W])

Submission status: Accepted

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

Submission status: Accepted

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



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


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

Submission status: Accepted

Solution code:
def p_e():
    """
    ナップサック問題（制約厳しい版） 
    """
    N, W = map(int, input().split())
    dp = [0] * (W + 1)
    for i in range(1, N + 1):
        w, v = map(int, input().split())
        NEXT = [0] * (W + 1)
        for j in range(1, W + 1):
            if j - w >= 0:
                NEXT[j] = max(v + dp[j - w], dp[j])
            else:
                NEXT[j] = dp[j]
        dp = NEXT

    print(max(NEXT))


if __name__ == '__main__':
    p_e()

Submission status: Accepted

Solution code:
def p_d():
    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(1, W + 1):
            if j - w >= 0:
                dp[i][j] = max(v + dp[i - 1][j - w], dp[i - 1][j])
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j])

    print(max(dp[N]))


if __name__ == '__main__':
    p_d()

Submission status: Accepted

Solution code:
def p_d():
    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(1, W + 1):
            if j - w >= 0:
                dp[i][j] = max(v + dp[i - 1][j - w], dp[i][j], dp[i - 1][j])
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j])

    print(max(dp[N]))


if __name__ == '__main__':
    p_d()

Submission status: Accepted

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

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

for weight,value in wv_list:
    for w in range(W+1)[::-1]:
        if w  >= weight:
            memo[w] = max(memo[w], memo[w-weight]+value)
            
print(memo[W])

Submission status: Accepted

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

def main():
    N,W = map(int,input().split())
    dp = [-1 for _ in range(W+1)]
    dp[W] = 0
    for _ in range(N):
        nm,nv = [int(a) for a in input().split()]
        for j in range(nm,W+1):
            a = nm
            if dp[j] == -1:
                continue
            if dp[j-a] < dp[j] + nv:
                dp[j-a] = dp[j] + nv
    print(max(dp))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
from copy import *

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

Submission status: Accepted

Solution code:
from sys import stdin
def main():
  from builtins import int, range
  readline = stdin.readline
  n, w = map(int, readline().split())
  t = [-1] * (w + 1)
  t[w] = 0
  for _ in range(n):
    nw, nv = map(int, readline().split())
    for i in range(nw, w + 1):
      ti = t[i]
      if ti == -1:
        continue
      if t[i - nw] < ti + nv:
        t[i - nw] = ti + nv
  print(max(t))
main()

Submission status: Accepted

Solution code:
from sys import stdin
def main():
  from builtins import int, range
  readline = stdin.readline
  n, w = map(int, readline().split())
  t = [-1 for i in range(w + 1)]
  t[w] = 0
  for _ in range(n):
    nw, nv = map(int, readline().split())
    for i in range(nw, w + 1):
      ti = t[i]
      if ti == -1:
        continue
      if t[i - nw] < ti + nv:
        t[i - nw] = ti + nv
  print(max(t))
main()

Submission status: Accepted

Solution code:
from sys import stdin
def main():
  from builtins import int, range
  readline = stdin.readline
  n, w = [int(e) for e in readline().split()]
  t = [-1 for i in range(w + 1)]
  t[w] = 0
  for _ in range(n):
    nw, nv = [int(e) for e in readline().split()]
    for i in range(nw, w + 1):
      if t[i] == -1:
        continue
      if t[i - nw] < t[i] + nv:
        t[i - nw] = t[i] + nv
  print(max(t))
main()

Submission status: Accepted

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

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

    return dp[W]

print(d())

Submission status: Accepted

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

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

    return max(dp)

print(d())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, W = list(map(int, input().split()))
W += 1
A = [0] * W
wi, vi = list(map(int, input().split()))
A[wi] = vi

for _ in range(N-1):
    wi, vi = list(map(int, input().split()))
    tmp = [0] * W

    for w in range(W):
        if w-wi < 0:
            tmp[w] = A[w]
        else:
            tmp[w] = max(A[w-wi] + vi, A[w])

    A = tmp

print(max(A))

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for i in range(n)]
#wv[i][0]:i番目の品物の重さ
#wv[i][1]:i番目の品物の価値

dp = [0]*(w+1)#dp[i]:重さiにおける最大価値
for i in range(n):#あるi番目の品物について
    for j in range(w,wv[i][0]-1, -1):#ある重さjについて
        dp[j] = max( dp[j], dp[j-wv[i][0]]+wv[i][1] )#i番目の品物を使うほうが重さjでの価値が高い場合は値を更新

print(max(dp))

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for i in range(n)]
#wv[i][0]:i番目の品物の重さ
#wv[i][1]:i番目の品物の価値

dp = [0]*(w+1)#dp[i]:重さiにおける最大価値
for i in range(n):#あるi番目の品物について
    for j in range(w,wv[i][0]-1, -1):
        dp[j] = max( dp[j], dp[j-wv[i][0]]+wv[i][1] )#i番目の品物を使うほうが良い場合は値を更新

print(max(dp))

Submission status: Accepted

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

dp_v = [0] * (W+1)

for i in range(N):
    for j in (reversed(range(W+1))):
        if (j == 0 or dp_v[j] != 0) and j+w[i] <= W and dp_v[j+w[i]] < dp_v[j] + v[i]:
            dp_v[j+w[i]] = dp_v[j] + v[i]
            
max = 0        
for i in range(W+1):
    if max < dp_v[i]:
        max = dp_v[i]

print(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+1) for _ in range(N+1)]

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

Submission status: Accepted

Solution code:
# AtCoder DP Task D - Knapsack 1
def knapsack(target, W, V): # target=knapsack weight
    P = [[0] * (target + 1) for _ in range(len(V))]
    for vi in range(len(V)):
        row, prev = P[vi], P[vi - 1]
        for w in range(target + 1):
            if vi > 0:
                row[w] = prev[w] # same value without vi-th item
                if w >= W[vi]:
                    new = P[vi - 1][w - W[vi]] + V[vi]
                    if new > P[vi][w]: # most value
                        row[w] = new
            else:
                if w >= W[vi]:
                    row[w] = V[vi]
    return P[len(V) - 1][target]

def knapsack_rec(target, W, V): # target=knapsack weight
    P = [-1] * (target + 1)
    P[target] = 0 # default + max

    for vi in range(len(V)):
        we = W[vi]
        va = V[vi]
        for i in range(we, target + 1):
            if P[i] != -1 and P[i - we] < P[i] + va:
                P[i - we] = P[i] + va

    return max(P)

assert knapsack_rec(15, [6, 5, 6, 6, 3, 7], [5, 6, 4, 6, 5, 2]) == 17

if __name__ == "__main__":
    import sys
    n, w, *r = map(int, sys.stdin.read().split())
    W, V = r[::2], r[1::2]
    ans = knapsack_rec(w, W, V)
    print(ans)

Submission status: Accepted

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

for i in range(1, n+1):
    for w in range(W+1):
        weight, value = obj[i-1]
        DP[i][w] = max(DP[i-1][w], DP[i][w])
        if w + weight <= W:
            DP[i][w + weight] = max(DP[i - 1][w] + value, DP[i][w + weight])

ans = max(DP[n])
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
N, W = map(int, input().split())
def knapsack():
  dp = np.zeros((N+1, W+1), dtype=int)
  c = np.arange(1, N+1)
  for i in c:
    w, v = map(int, input().split())
    dp[i][w:] = np.maximum(dp[i-1][w:], dp[i-1][:-w] + v)
    dp[i][:] = np.maximum(dp[i][:], dp[i-1][:])
  return dp[-1][-1]
print(knapsack())

Submission status: Accepted

Solution code:
def main():
    n, wn = map(int, input().split())
    w = [0 for _ in range(n)]
    v = w[:]
    for i in range(n):
        w[i], v[i] = map(int, input().split())
    dp = [[0 for _ in range(wn + 1)] for _ in range(n)]  # dp[n][wn + 1]を定義
    for i in range(w[0], wn + 1):
        dp[0][i] = v[0]
    for i in range(1, n):
        for j in range(wn + 1):
            if j < w[i]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
    print(max(dp[n - 1]))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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


for i in range(n):
    for j in range(w + 1):
        use = 0
        if j - wv[i][0] >= 0:
            use = dp[i - 1][j - wv[i][0]] + wv[i][1]
        nouse = dp[i - 1][j]

        dp[i][j] = max(use, nouse)

print(max(dp[-1]))

Submission status: Accepted

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

Submission status: Accepted

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

def main():
    N, W = tuple(map(int, input().split()))
    A = tuple(tuple(map(int, input().split())) for _ in range(N))
    dp = [0] * (W + 1)
    for i in range(N):
        for j in range(W, A[i][0] - 1, -1):
            dp[j] = max(dp[j], dp[j - A[i][0]] + A[i][1])
    print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
items = [None] * N
for n in range(N):
    w, v = map(int, input().split())
    items[n] = (w, v)

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

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

Submission status: Accepted

Solution code:
n,W=map(int,raw_input().split())
w=[]
val=[]
for i in range(n):
    p=map(int,raw_input().split())
    w.append(p[0])
    val.append(p[1])
dp = [0]*(W+1)
for i in range(n):
    for j in range(W,w[i]-1,-1):
        dp[j]=max(dp[j],dp[j-w[i]]+val[i])
print(dp[-1])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

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

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

answer = dp.max()
print(answer)

Submission status: Accepted

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np

n, w = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(n)]
table = np.zeros(w+1, dtype=np.int64)

for i in range(n):
    l = table[:-wv[i][0]]
    r = table[wv[i][0]:]
    np.maximum(l + wv[i][1], r, out = r)

print(table[w])

Submission status: Accepted

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

dp[0][wv[0][0]] = wv[0][1]

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

Submission status: Accepted

Solution code:
import copy

def solve(N, W, w, v):
    dp = [[0]*(W+1) for _ in range(N+2)]
    for i in range(N):
        for sum_w in range(W):
            if sum_w+w[i] <=W:
                dp[i+1][sum_w+w[i]] = max(dp[i][sum_w+w[i]], dp[i][sum_w]+v[i])
        dp[i+2] = copy.copy(dp[i+1])
    return max(dp[-1])

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

print(solve(N, W, w, v))