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:
# python3.4.2用
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().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 m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')
def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N,W = imn()
weight = []
value = []
for _ in range(N):
    w,v = imn()
    weight.append(w)
    value.append(v)

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

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

Submission status: Accepted

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

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

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


print(ans_array[N][W])

Submission status: Accepted

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

def main():
    N, W = map(int, input().split())
    w = [0]
    v = [0]
    for _ in range(N):
        w_, v_ = map(int, input().split())
        w.append(w_)
        v.append(v_)
    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])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np


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

Submission status: Accepted

Solution code:
from sys import stdin

def main():
    n,w = map(int, input().split())
    ary = [list(map(int, stdin.readline().split())) for _ in range(n)]
    dp = [[0 for _ in range(w+1)] for _ in range(n)]
    for i in range(n):
        for y in range(1,w+1):
            if i == 0:
                dp[i][y] = ary[i][1] if ary[i][0] <= y else 0
            elif ary[i][0] <= y:
                dp[i][y] = max(dp[i-1][y-ary[i][0]] + ary[i][1],dp[i-1][y])
            else:
                dp[i][y] = dp[i-1][y]
    print(dp[n-1][w])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[0] * (N + 1) for _ in range(W+1)]

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

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


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def knapsack(n,w,wv):
    inf = float('inf')
    dp = [[-inf for _ in range(w+1)] for _ in range(n+1)]
    for i in range(w+1): dp[0][i] = 0

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

print(knapsack(n,w,wv))

Submission status: Accepted

Solution code:
import itertools
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


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


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
N, W = map(int, input().split())
w = []
v = []
for _ in range(N):
    ww, vv = map(int, input().split())
    w.append(ww)
    v.append(vv)
dp = [[0]*(W+1) for j in range(N+1)]
for i in range(N):
    for sum_w in range(W+1):
        if w[i] <= sum_w:
            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)
print(dp[N][W])

Submission status: Accepted

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

n, W = [int(x) for x in input().split()]
wv = [[int(x) for x in input().split()] for _ in range(n)]

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

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

Submission status: Accepted

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

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

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

print(dp[-1])

Submission status: Accepted

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

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

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

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

print(dp[N][W])

Submission status: Accepted

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

x, y  = map(int, input().split())
li =[]
for i in range(x):
    l = list(map(int, input().split()))
    li.append(l)
dp = [[0]*(y+1) for _ in range(x+1)]
for i in range(x):
    for j in range(1, y+1):
        if j - li[i][0] >= 0:
            dp[i+1][j] = max(dp[i][j],dp[i][j - li[i][0] ]+ li[i][1])
        else:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
print(dp[x][y])

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
inf = 10**9+7

n,W = map(int, input().split())
dp = [[0 for j in range(W+1)] for i in range(n+1)] # i個まで選んだ時の最大値

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

Submission status: Accepted

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

dp = [[-float('inf')]*(W+1) for _ in range(N+1)]
for w in range(W+1):
  dp[0][w] = 0

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

print(dp[N][W])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys

EMPTY = (0, 0, frozenset())


def solve(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        for j in range(max_capacity, w - 1, -1):
            tmp = dp[j - w] + v
            if dp[j] < tmp:
                dp[j] = tmp
    return dp[max_capacity]


def solve_better(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        # dp = dp[:w] + [max(dp[j], dp[j - w] + v) for j in range(w, max_capacity + 1)]
        dp[w:] = [max(dpj, dpjw + v) for dpj, dpjw in zip(dp[w:], dp[:-w])]
    return dp[max_capacity]


def solve_slow(values, nb, max_capacity):
    dp = [[0 for _ in range(max_capacity + 1)] for _ in range(nb + 1)]
    for i in range(1, nb + 1):
        w, v = values[i - 1]
        for j in range(1, max_capacity + 1):
            if w <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            else:
                dp[i][j] = dp[i - 1][j]
    # print("\n".join(map(str, dp)))
    return dp[nb][max_capacity]


def do_job():
    "Do the work"
    # first line is number of test cases
    N, W = map(int, input().split())
    values = []
    for _ in range(N):
        values.append(list(map(int, input().split())))
    result = solve(values, N, W)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Submission status: Accepted

Solution code:
# DP
def main():
    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 - w, -1, -1):
            if dp[i] == -1:
                continue
            if dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v
    print(max(dp))


main()

Submission status: Accepted

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

def solve(n, w ,weights, values):
    def rec_solve(cw, cv, max_w, i):
        nonlocal weights, values
        #print(cw, cv, i)
        if i == -1:
            return cv
        
        # take
        if weights[i] + cw <= max_w:
            return max(rec_solve(cw+weights[i], cv + values[i], max_w, i-1),
                        rec_solve(cw, cv, max_w, i-1))

        else:
            # dont take
            return rec_solve(cw, cv, max_w, i-1)

    return rec_solve(0, 0, w, n-1)

def solve_fast(n_items, max_w, weights, values):
    dp =  [[0]*(max_w+1) for _ in range(n_items)]
    dp[0] = [values[0] if i >= weights[0] else 0 for i in range(max_w+1)]

    for r in range(1, n_items):
        cw, cv = weights[r], values[r]
        for c in range(max_w+1):
            if cw > c:
                dp[r][c] = dp[r-1][c]
            else:
                dp[r][c] = max(dp[r-1][c], dp[r-1][c-cw] + cv)

    #for r in dp:
        #print(r)

    return dp[-1][-1]


print(solve_fast(N, W, weights, values))

Submission status: Accepted

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

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

print(int(np.max(dp)))

Submission status: Accepted

Solution code:
def solve(c, a):
    dp = [0]*(c+1)
    for w, p in a:
        for i in range(c, -1, -1):
            if dp[i] > 0 and i+w < c+1:
                dp[i+w] = max(dp[i+w], dp[i] + p)
        if w < c+1:
            dp[w] = max(dp[w], p)
    return max(dp)
  
n, k = map(int, input().split())
a = []
for _ in range(n):
    a.append(list(map(int, input().split())))
print(solve(k, a))

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
weights, values = zip(*[tuple(map(int, input().split()))for _ in range(n)])
dp = [0]*(w+1)
for i in range(1, n+1):
    for j in reversed(range(1, w+1)):
        if j-weights[i-1] < 0:
            continue
        dp[j] = max(dp[j], dp[j-weights[i-1]]+values[i-1])
print(dp[-1])

Submission status: Accepted

Solution code:
import numpy as np
n, w = map(int, input().split())
wv_list = [[int(i) for i in input().split()] for i in range(n)]

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

print(int(np.max(dp)))

Submission status: Accepted

Solution code:
import numpy as np

n, w = map(int, input().split())
wv_list = [[int(i) for i in input().split()] for i in range(n)]

dp = np.zeros(w+1)

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

print(int(np.max(dp)))

Submission status: Accepted

Solution code:
def resolve():
    N, W = map(int, input().split())
    weight = []
    value = []
    for i in range(N):
        w, v = map(int, input().split())
        weight.append(w)
        value.append(v)
    dp = [[0] * (W + 1)]
    for i in range(N):
        d = []
        for w in range(W + 1):
            if w >= weight[i]:
                d.append(max(dp[-1][w - weight[i]] + value[i], dp[-1][w]))
            else:
                d.append(dp[-1][w])
        dp.append(d)
    print(dp[-1][-1])


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)

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

wv.sort()

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

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

ans = dp[-1]
print(ans)

Submission status: Accepted

Solution code:
n,W = map(int,input().split())
w = []
v = []
dp = [[0]*(W+1) for _ in range(n+1)]
for _ in range(n):
    w1,v1 = map(int,input().split())
    w.append(w1)
    v.append(v1)
    
for i in range(n):
    for sumw in range(W+1):
        if sumw -w[i]>=0:
            dp[i+1][sumw] = max(dp[i+1][sumw],dp[i][sumw-w[i]]+v[i])
        dp[i+1][sumw] = max(dp[i][sumw],dp[i+1][sumw])
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 for _ in range(w + 1)] for _ in range(n)]

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[0 for i in range(W+1)] for i in range(N)]
    for i in range(N):
        for j in range(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)
    print(max(dp[-1]))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N,W = [int(v) for v in input().split()]
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(1,N+1):
    w,v = [int(v) for v in input().split()]
    for cap in range(W+1):
        if cap - w >= 0:
            dp[i][cap] = max(dp[i][cap],dp[i-1][cap-w]+v)
        dp[i][cap] = max(dp[i][cap],dp[i-1][cap])

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

Submission status: Accepted

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

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

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

dp = [[0] * (W + 1) for _ in range(N)]
for w in range(W + 1):
  if (w == 0):
    continue
  for i, wv in enumerate(WV):
    if(w < wv[0]):
      if (i - 1 < 0):
        dp[i][w] = 0
      else:
        dp[i][w] = dp[i - 1][w]
    else:
      if (i - 1 < 0):
        val1 = 0
      else:
        val1 = dp[i - 1][w]
      
      if (((i - 1) < 0) or ((w - wv[0]) < 0)):
        val2 = wv[1]
      else:
        val2 = wv[1] + dp[i - 1][w - wv[0]]
      dp[i][w] = val1 if (val1 > val2) else val2

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

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

print(dp[-1])

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
x=[0]+[-1]*W

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

    for j in range(W-w,-1,-1):
        if x[j]>=0:
            x[j+w]=max(x[j+w],x[j]+v)

print(max(x))

Submission status: Accepted

Solution code:
n, w = [int(i) for i in input().split()]
dp = [0] * (w + 1)
for _ in range(n):
    u, v = [int(i) for i in input().split()]
    for i in reversed(range(w - u + 1)):
        dp[i + u] = max(dp[i + u], dp[i] + v)

print(max(dp))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n,w = map(int,readline().split())
WV = []
for i in range(n):
	WV.append(list(map(int,readline().split())))

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

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

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
W, V = [], []
for i in range(n):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
A = [0 for j in range(m+1)]
for i in range(n):
    B = []
    for j in range(W[i]):
        B.append(A[j])
    for j in range(W[i], m+1):
        B.append(max(A[j], A[j-W[i]]+V[i]))
    A = B
print(A[m])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
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+1)]
for i in range(N):
    for j in range(W+1):
        if j>=w[i]:
            dp[i+1][j]=max(dp[i][j-w[i]]+v[i],dp[i][j])
        else:dp[i+1][j]=dp[i][j]

print(dp[N][W])

Submission status: Accepted

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

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

print(dp[n][w])

Submission status: Accepted

Solution code:
import numpy as np

N,W = map(int,input().split())
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())
wv = [list(map(int,input().split())) for _ in range(n)]
dp = [[0]*(w+1) for _ in range(n+1)]
for i in range(n):
    wi, vi = wv[i]
    for j in range(w+1):
        if j<wi:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-wi]+vi)
            
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[i][j]:i番目の品物を詰めて重さjのときの価値の最大値
dp = [[0]*(W+1) for i in range(N+1)]

#w[i-1]を使うかどうか
for i in range(1,N+1):
    #ナップサックの残りの容量(0-Wまで) 
    for j in range(W+1):
        if j >= w[i-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[-1][-1])

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
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

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

Submission status: Accepted

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


for i in range(N+10):
  WV.append([0,0])


dp = []
for i in range(N+1):
  dp.append([0]*(W+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:
import numpy as np

N,W = list(map(int,input().split()))
dp = np.zeros(W+1,dtype = int)
for i in range(N):
    w,v = list(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())
items = [list(map(int, input().split())) for _ in range(N)]
weights = list(map(lambda x: x[0], items))
values = list(map(lambda x: x[1], items))

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

for i in range(N):
    for w in range(1, W+1):
        # もらう場合
        if w - weights[i] >= 0: # もらえるならもらった方がいい
            dp[i+1][w] = dp[i][w-weights[i]] + values[i]
        
        # もらわない場合と比較、別の入れ方をしてここに至った方がいいかもしれない
        dp[i+1][w] = max(dp[i+1][w], dp[i][w])
    
print(dp[N][W])

Submission status: Accepted

Solution code:
def solve(items, n, w):
    dp = [0] * (w+1)
    for i in range(n):
        wi, vi = items[i]
        for j in range(w, wi-1, -1):
            dp[j] = max(dp[j], dp[j-wi] + vi)

    return dp[w]


def main():
    inp = lambda: [int(x) for x in input().split()]
    n, w = inp()
    items = [inp() for _ in range(n)]
    print(solve(items, n, w))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve(items, n, w):
    f = [[0] * (w + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wi, vi = items[i-1]
        for j in range(w + 1):
            f[i][j] = f[i-1][j]
            if j >= wi:
                f[i][j] = max(f[i][j], f[i-1][j-wi] + vi)
    return f[n][w]


def main():
    inp = lambda: [int(x) for x in input().split()]
    n, w = inp()
    items = [inp() for _ in range(n)]
    print(solve(items, n, w))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

for n 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 = list(map(int,input().split()))

w = []
v = []

for i in range(N):
    a,b = list(map(int,input().split()))
    w.append(a)
    v.append(b)

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

print(max(DP[N]))

Submission status: Accepted

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

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

print(dp[W])

Submission status: Accepted

Solution code:
import numpy as np
import sys


def main():
    input = sys.stdin.readline
    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())
    ndp = np.zeros(W + 1, dtype=np.int64)
    for w, v in zip(w, v):
        np.maximum(ndp[:-w] + v, ndp[w:], out=ndp[w:])
    print(ndp[-1])


if __name__ == "__main__":
    main()

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

Submission status: Accepted

Solution code:
import numpy as np
N, W = map(int, input().split())
dp = np.zeros(W+1, dtype=int) #0~Wまでのリストを作る
for i in range(N):
  w, v = map(int, input().split())
  dp[w:] = np.maximum(dp[:-w] + v, dp[w:])
print(dp[W])

Submission status: Accepted

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

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

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

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

print(max(dp[N]))

Submission status: Accepted

Solution code:
def main():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(N)]
    dp = [[0] * (W+10) for _ in range(N+1)]
    for i in range(N):
        for w in range(W+1):

            # i番目の商品を選ぶ場合
            if w - wv[i][0] >= 0:
                dp[i+1][w] = max(dp[i+1][w], dp[i][w-wv[i][0]] + wv[i][1])

            # i番目の商品を選ばない場合
            dp[i+1][w] = max(dp[i+1][w], dp[i][w])
    print(dp[N][W])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,w=list(map(int,input().split()))
a=[]
for i in range(n):
    a.append(list(map(int,input().split())))
a.sort()
b=[]
for i in range(n):
    b.append([0]*(w+1))
for i in range(1,w+1):
    if i>=a[0][0]:
        b[0][i]=a[0][1]

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