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] = [int(i) for i in input().split()]
wei_val = []
for i in range(n):
    wei_val.append([int(j) for j in input().split()])
"""
dp[i][w_zantei] = v
i : i番目までの品物
w_zantei : 合計の重さがこれになる
v : 価値

更新式
dp[i][w_zantei] = max(dp[i][w_zantei],dp[i - 1][w_zantei - wei_val[0]] + wei_val[1]) (if w >= w_zantei+wei_val[i][0])
dp[i][w_zantei] = dp[i-1][w_zantei] (if w < w_zantei+wei_val[0])
"""
dp = [[0]* (w+1) for i in range(n)]
for i in range(n):
    for w_zantei in range(w+1):
        if w_zantei >= wei_val[i][0]:
            dp[i][w_zantei] = max(dp[i-1][w_zantei],dp[i - 1][w_zantei - wei_val[i][0]] + wei_val[i][1])
        else:
            dp[i][w_zantei] = dp[i-1][w_zantei]
print(dp[n-1][w])

Submission status: Accepted

Solution code:
def solve(N, W, weightValues):
    dp = [0] * (W + 1)
    s = 0
    for w, v in weightValues:
        s += w
        for j in range(min(W, s), w - 1, -1):
            if dp[j - w] + v > dp[j]:
                dp[j] = dp[j - w] + v

    print(max(dp))


N, W = map(int, input().split())
weightValues = sorted([list(map(int, input().split())) for i in range(N)])
solve(N, W, weightValues)

Submission status: Accepted

Solution code:

N,W=map(int,input().split())
dp=[0]*(W+1)
L = sorted([list(map(int,input().split())) for i in range(N)])
s=0
 
for w, v in L:
    s+=w
    for j in range(min(W,s),w-1,-1):
        if dp[j-w]+v > dp[j]: dp[j]=dp[j-w]+v
    
print(max(dp))

Submission status: Accepted

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

Submission status: Accepted

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

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

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

print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #整数1つinput
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii())
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #文字列1つinput
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

n,w = mii()
wei,val= [0],[0]
for _ in range(n):
    p,q=mii()
    wei.append(p)
    val.append(q)

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

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


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

Submission status: Accepted

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

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

    
dp=[[0]*(W+1) for _ in range(N+1)]#i番目までの商品で重さj以下の時の総和

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

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

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

ans = dp[W]
print(ans)

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

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

ans = dp[W]
print(ans)

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def add_mod(a,b): return (a+b) % MOD

N, W = imn()
wv = [iln() for _ in range(N)]

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

for i in range(N):
    for sum_w in range(W+1):
        if sum_w - wv[i][0] >= 0: dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w-wv[i][0]] + wv[i][1])
        dp[i+1][sum_w] = max(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, v = [0] * N, [0] * N

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
MOD = 10**9+7

N,W = imn()
wv = [iln() for _ in range(N)]

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""


N,W=map(int,input().split())
dp=[0]*(W+1)
L = sorted([list(map(int,input().split())) for i in range(N)])
s=0

for w, v in L:
    s+=w
    for j in range(min(W,s),w-1,-1):
        if dp[j-w]+v > dp[j]: dp[j]=dp[j-w]+v
    
print(max(dp))

Submission status: Accepted

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

Submission status: Accepted

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


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数

N,W = imn()
wv = [iln() for _ in range(N)]
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

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

Submission status: Accepted

Solution code:
def solve(N, W, weight_values):
  dp = [0 for _ in range(W + 1)]

  for i in range(N):
    i_weight, i_value = weight_values[i]
    for w in range(W, i_weight - 1, -1):
      # dp[w] = max(dp[w - i_weight] + i_value, dp[w])
      temp = dp[w - i_weight] + i_value
      if temp > dp[w]:
        dp[w] = temp

  print(dp[W])

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


N, W = iln()
w_v = []
for i in range(N):
  w_v.append(iln())
  
solve(N, W, w_v)

Submission status: Accepted

Solution code:
def solver():
	N,W = map(int, input().split())
	item = []
	for i in range(N):
		item.append(list(map(int, input().split())))
	dp = [0 for _ in range(W+1)]
 
	for i in range(0,N):
		for j in range(W, item[i][0]-1, -1):
			dp[j] = max(dp[j], dp[j-item[i][0]]+item[i][1])
	print(dp[W])
 
solver()

Submission status: Accepted

Solution code:
#Educational DP Contest
#D-Knapsack1

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

#dp table
#内側が重さw,外側がその品物をいれるかどうかのループを作る
#いきなりループに入れるように、内外共に0配列を余分に用意する
dp = [[0]*(W+1) for _ in range(N+1)]

#process1
for i in range(1,N+1):
    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],dp[i-1][j-w]+v)


#output process
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import unittest


class TestD(unittest.TestCase):
    def test_1(self):
        self.assertEqual(
            think(8, [[3, 30], [4, 50], [5, 60]]),
            90
        )

    def test_2(self):
        self.assertEqual(
            think(
                5, [
                    [1, 1000000000], [1, 1000000000], [1, 1000000000],
                    [1, 1000000000], [1, 1000000000]
                ]
            ),
            5000000000
        )

    def test_3(self):
        self.assertEqual(
            think(15, [[6, 5], [5, 6], [6, 4], [6, 6], [3, 5], [7, 2]]),
            17
        )


def solve():
    w, list_of_w_and_v = read()
    result = think(w, list_of_w_and_v)
    write(result)


def read():
    n, w = read_int(2)
    list_of_w_and_v = []
    for _ in range(n):
        list_of_w_and_v.append(read_int(2))
    return w, list_of_w_and_v


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(w, list_of_w_and_v):
    invalid = -1

    # dp[weight] = max value at 'weight'
    dp = [invalid for _ in range(w + 1)]
    dp[0] = 0

    for weight, value in list_of_w_and_v:
        for i in range(len(dp) - 1, -1, -1):
            if dp[i] == invalid:
                continue
            if i + weight >= len(dp):
                continue
            dp[i + weight] = max(
                    dp[i + weight],
                    dp[i] + value
            )
    return max(dp)


def write(result):
    print(result)


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Accepted

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

def dp():
  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
    
  for i in range(N):
    w = WV[i][0]
    v = WV[i][1]
    for j in range(W+1):
      if w<=j: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
        dp[i+1][j]=max(dp[i][j-w]+v, dp[i][j])
      else: #入る可能性はない
        dp[i+1][j]=dp[i][j]
  return dp[N][W]
print(dp())

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,W=LI()
  dp=[[0 for _ in range(W+1)]for __ in range(n+1)]
  w=[]
  v=[]
  for _ in range(n):
    a,b=LI()
    w.append(a)
    v.append(b)

  # dp[i+1][j] iまでで最大化
  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+w[i]<=W:
        dp[i+1][j+w[i]]=max(dp[i+1][j+w[i]],dp[i][j]+v[i])
  return dp[n][W]

# main()
print(main())

Submission status: Accepted

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

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

for w, v in L:
  con += w
  for i in range(min(con, W), w - 1, -1):
    if dp[i] < dp[i - w] + v:
      dp[i] = dp[i - w] + v

print(max(dp))

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

print(dp[-1])

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
l=[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 sum_w in range(w+1):
        
        if sum_w-l[i][0]>=0:
            dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w-l[i][0]]+l[i][1])
        #l[i]を入れるとき
        dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w])
        #入れない時
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import numpy as np
n, w = map(int, input().split())
dp = np.zeros(w+1)

for i in range(1,n+1): #n個の荷物をそれぞれ持つか否か
  wn, vn = map(int, input().split())
  dp[wn:] = np.maximum(dp[wn:], dp[:-wn]+vn)#wnより小さい=>持てない=>価値変わらない
print(int(dp[-1]))

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
 
dp = [-1 for _ in range(W + 1)] # dp[重量の総和]:= 価値の総和
dp[0] = 0
 
for i in range(N):
  w, v = wv[i]
  for j in range(W, -1, -1):
    if dp[j] >= 0 and j + w <=  W:
      dp[j+w] = max(dp[j+w], dp[j]+v)
      
print(max(dp))

Submission status: Accepted

Solution code:
def solve():
    N, W = map(int, input().split())
    weight = []
    value = []
    for i in range(N):
        tmpw, tmpv = map(int, input().split())
        weight.append(tmpw)
        value.append(tmpv)
    
    dp = [[0] * (W+1) for i in range(N+1)]
    for i in range(N):
        for w_i in range(W+1):
            if w_i - weight[i] >= 0:
                dp[i+1][w_i] = max(dp[i+1][w_i], dp[i][w_i - weight[i]] + value[i])
            
            dp[i+1][w_i] = max(dp[i+1][w_i], dp[i][w_i])

    print(dp[N][W])
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
N, W = map(int, input().split())
dp = np.zeros(W+1, dtype=np.int)
for n in range(1,N+1):
  wn, vn = map(int, input().split())
  dp[wn:]=np.maximum(dp[wn:], dp[:-wn]+vn)
print(dp[W])

Submission status: Accepted

Solution code:
N, W = [int(i) for i in input().split()]
weight, value = [], []

for i in range(N):
    w, v = [int(i) for i in input().split()]
    weight.append(w); value.append(v);
weight.append(0)
value.append(0)

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

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,w = inpl()
wei = [0] * n
val = [0] * n
for i in range(n):
    wei[i],val[i] = inpl()

dp = [[0]*(w+5) for i in range(n+5)]
for i in range(n):
    for j in range(w+1):
        if wei[i] > j:
            dp[i+1][j] = dp[i][j]
            continue
        dp[i+1][j] = max(dp[i+1][j], dp[i][j-wei[i]]+val[i], dp[i][j])
print(dp[n][w])

Submission status: Accepted

Solution code:
n, max_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 for _ in range(max_w+1)] for _ in range(n+2)]

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

print(max(dp[n]))

Submission status: Accepted

Solution code:
def knapsack1(weight_value, w):
    cur = [0] * (w + 1)
    
    for weight, value in weight_value:
        for i in reversed(range(weight, w + 1)):
            cur[i] = max(cur[i], cur[i - weight] + value)

    return cur[w]


def main():
    n, w = [int(x) for x in input().split()]
    weight_value = [None] * n
    for i in range(n):
        weight_value[i] = [int(x) for x in input().split()]
    return knapsack1(weight_value, w)


print(main())

Submission status: Accepted

Solution code:
def knapsack1(weight_value, w):
    cur = [0] * (w + 1)
    nxt = [0] * (w + 1)

    for weight, value in weight_value:
        for i in range(1, weight):
            nxt[i] = cur[i]
        for i in range(weight, w + 1):
            nxt[i] = max(cur[i], cur[i - weight] + value)
        cur, nxt = nxt, cur
    return cur[w]


def main():
    n, w = [int(x) for x in input().split()]
    weight_value = [None] * n
    for i in range(n):
        weight_value[i] = [int(x) for x in input().split()]
    return knapsack1(weight_value, w)


print(main())

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
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(dp[i-1][j], dp[i-1][j-w]+v)
        else:
            dp[i][j] = dp[i-1][j]
#print(dp)
print(dp[N][W])

Submission status: Accepted

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

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

print(dp[N][W])

Submission status: Accepted

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

import numpy as np

EDPC = "https://atcoder.jp/contests/DP/"
TDPC = "https://atcoder.jp/contests/tDPc/tasks"

############### TESTCASE ###############
test = ""
#test = \
"""
3 8
3 30
4 50
5 60
ans 90
"""

"""
5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
ans 5000000000(>int32)
"""

"""
6 15
6 5
5 6
6 4
6 6
3 5
7 2
ans 17
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################
#np.maximum(*arrays) == np.max(np.vstack(*arrays), axis=0)
(np.maximum(np.array([1,3,2]), np.array([2, 1, 3])) == 
 np.max(np.vstack([np.array([1,3,2]), np.array([2, 1, 3])]), axis=0)).all()
################# MAIN #################

N, W = map(int, input2().split())
WV = np.array([tuple(map(int, input2().split())) for _ in range(N)])

dp = np.zeros(W + 1, dtype="int64")
for w, v in WV:
    dp[W:w-1:-1] = np.max(np.vstack([dp[W:w-1:-1], dp[W-w::-1] + v]), axis=0)
    
print(dp[-1])

Submission status: Accepted

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

import numpy as np

EDPC = "https://atcoder.jp/contests/DP/"
TDPC = "https://atcoder.jp/contests/tDPc/tasks"

################ DANGER ################
test = ""
#test = \
"""
3 8
3 30
4 50
5 60
ans 90
"""

"""
5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
ans 5000000000(>int32)
"""

"""
6 15
6 5
5 6
6 4
6 6
3 5
7 2
ans 17
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################  
# np.maximum(np.array([1,3,2]), np.array([2, 1, 3]))
N, W = map(int, input2().split())
WV = np.array([tuple(map(int, input2().split())) for _ in range(N)])

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

print(dp[-1])

Submission status: Accepted

Solution code:
def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista

def plecak_rozwiazanie(pojemnosc, lista_przedmiotow): 
    bez_przedmiotu = [0] * (pojemnosc + 1)
    for waga, wartosc in lista_przedmiotow:
        z_przedmiotem = [None] * (pojemnosc + 1)
        for i in range(pojemnosc+1): 
            if waga > i: 
                z_przedmiotem[i] = bez_przedmiotu[i]
            else: 
                z_przedmiotem[i] = max(bez_przedmiotu[i-waga]+wartosc, bez_przedmiotu[i])
        bez_przedmiotu = z_przedmiotem
    return bez_przedmiotu[pojemnosc]

def plecak_1(): 
    N, W = wczytaj_liste()
    przedmioty = []
    for i in range(N): 
        waga, wartosc = wczytaj_liste()
        przedmioty.append((waga, wartosc))
    print (plecak_rozwiazanie(W,przedmioty))   
    
plecak_1()

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
#[w,v]
#重さに対応するインデックスに価値を保存する
dp=[[0]*(w+1) for i in range(n+1)]
 
for i in range(n):
    for sum_w in range(1,w+1):
        if sum_w-l[i][0]>=0:
            dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w-l[i][0]]+l[i][1])
        #i番目の品を入れる場合
    
        dp[i+1][sum_w]=max(dp[i][sum_w],dp[i+1][sum_w])
        #i番目の品を入れない場合
print(dp[-1][-1])

Submission status: Accepted

Solution code:
def main():
    N, W = map(int, input().split())
    dp = [[0] * (W + 1) for _ in range(2)]
    ws, vs = [], []
    for _ in range(N):
        w, v = map(int, input().split())
        ws.append(w)
        vs.append(v)

    for i in range(N):
        now_i, next_i = i & 1, (i+1) & 1
        for j in range(W+1):
            if j - ws[i] >= 0:
                dp[next_i][j] = max(dp[now_i][j], dp[now_i][j-ws[i]] + vs[i])
            else:
                dp[next_i][j] = dp[now_i][j]
    print(max(dp[N & 1]))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import numpy as np

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

# 持ち帰る最大値の重さまでのリストを作る。
# 持ち帰れる重さが10なら、添字が10までのリストを作る。
# 持ち帰る各重さ毎の最大値を持つ。
dp = np.zeros(W+1, dtype=np.int64)

for _ in range(N):
    # dp[:W-w+1]+v
    # 次の品物を持ち帰っても重さの上限Wを超えない値以降だけを取得して、次の品物の価値を追加する
    # 持ち帰れる最大値-次の品物の重さしているので、同じ重さの品物が複数あった場合もより価値が高い方で比較される

    # dp[w:]
    # 現在の重さw以上の値を取得する

    # maximum(dp[:W-w+1]+v, dp[w:], out=dp[w:])
    # 2つの配列の要素を比較して、大きい方の要素を返す。
    # 次の品物を持ち帰った方が価値の総和が大きくなる場合は価値が更新される。
    w, v = map(int, input().split())
    np.maximum(dp[:W-w+1]+v, dp[w:], out=dp[w:])

print(dp[-1])

Submission status: Accepted

Solution code:
def solve():
    N, W = map(int, input().split())
    w = []
    v = []
    for i in range(N):
        tmpw, tmpv = map(int, input().split())
        w.append(tmpw)
        v.append(tmpv)
    
    dp = [[0] * (W+1) for i in range(N+1)]
    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+1][sum_w], dp[i][sum_w-w[i]]+ v[i])
            
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
    
    print(dp[-1][-1])


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

dp = [[-1 for _ in range(w + 5)] for _ in range(n + 5)]
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 - item[i][0] >= 0:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - item[i][0]] + item[i][1])

print(max(dp[n][: w + 1]))

Submission status: Accepted

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

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

print(value[N][W])