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

Submission status: Accepted

Solution code:
import numpy as np


def solve(w, items):
    dp = np.zeros(w + 1, dtype=int)

    for weight, value in items:
        dp[weight:] = np.maximum(dp[weight:], dp[:w-weight+1] + value)

    return dp[w]


def main():
    n, w = map(int, input().split())
    items = list(list(map(int, input().split())) for _ in range(n))

    ans = solve(w, items)
    print(ans)


main()

Submission status: Accepted

Solution code:
def solve():
    dp = [[0 for i in range(W + 1)] for j in range(N + 1)]
    for i in range(N):
        for j in range(W + 1):
            if j < w[i]:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] +v[i])
    return dp[N][W]

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
inf = 1 << 60
# dp[i][j] = i個目までの石を重さjで運んだときの価値の最大値
dp = [[-inf for j in range(W + 1)] for i in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    wi, vi = map(int, input().split())
    for w in range(0, W + 1):
        dp[i][w] = max(dp[i][w], dp[i - 1][w])
    for w in range(wi, W + 1):
        dp[i][w] = max(dp[i][w], dp[i - 1][w - wi] + vi)
    #print(dp[i])
ans = max(dp[N])
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N_W = list(map(int,input().split()))

N = N_W[0]
W = N_W[1]

w = []
v = []

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

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

for w1,v1 in zip(w,v):

    dp[w1:] = np.maximum(dp[w1:],dp[:W-w1 + 1] + v1)

print(dp.max())

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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


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

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

    print(max(dp[N]))


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


solve2()

Submission status: Accepted

Solution code:
# D
import numpy as np
n,w = map(int, input().split())
 
items = list(map(int, input().split()) for _ in [0]*n)
dp = np.zeros(w+1, dtype='int64')
 
for weight, value in items:
    dp[weight:] = np.maximum(dp[weight:], dp[:w-weight+1] + value)
print(dp.max())

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor

import heapq
import itertools
import operator


inf = float('inf')


def get_int():
    return int(input())


def get_str():
    return input().strip()


def get_list_of_int():
    return [int(i) for i in input().split()]


def get_char_list():
    return list(input().strip())


# inputs
N, W = 0, 0
Ws, Vs = [0], [0]


def set_inputs():
    global N, W, Ws, Vs
    N, W = get_list_of_int()
    ws, vs = [], []
    for _ in range(N):
        w, v = get_list_of_int()
        ws.append(w)
        vs.append(v)
    Ws, Vs = ws, vs


def main():
    set_inputs()
    values = [0] * (W + 1)
    items = [0] * (W + 1)
    for w in range(1, W + 1):
        values[w], items[w] = max((values[w - Ws[i]] + Vs[i], items[w - Ws[i]] | 1 << i) if w - Ws[i] >= 0 and (items[w - Ws[i]] & 1 << i) == 0 else (values[w-1], items[w-1]) for i in range(N))
    print(values[W])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
wv=[]
dp=[[0 for i in range(100010)]for j in range(110)]
for i in range(n):
    a=[int(j) for j in input().split()]
    wv.append(a)

from operator import itemgetter
wv.sort(key=itemgetter(0))

for i in range(n):
    for j in range(w+1):
        if j>=wv[i][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:
import numpy as np
n,w = map(int, input().split())

items = list(map(int, input().split()) for _ in [0]*n)
dp = np.zeros(w+1, dtype='int64')

for weight, value in items:
    dp[weight:] = np.maximum(dp[weight:], dp[:w-weight+1] + value)
print(dp.max())

Submission status: Accepted

Solution code:
n,k = [int(i) for i in input().split()]
w = []
v = []
for _ in range(n):
    a,b = [int(i) for i in input().split()]
    w.append(a)
    v.append(b)

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

for i in range(n):
    for j in range(k+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[-1][-1])

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ 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(1,W+1):
        if w-wv[i][0]<0:
            dp[i+1][w] = dp[i][w]
            continue
        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:
N,W = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(N)]

dp = [{0:0} for i in range(N+1)]
for i,(w,v) in enumerate(src):
    for w0,v0 in dp[i].items():
        if w0 not in dp[i+1]:
            dp[i+1][w0] = v0
        else:
            dp[i+1][w0] = max(dp[i+1][w0], v0)
        if w0+w > W: continue
        if w0+w not in dp[i+1]:
            dp[i+1][w0+w] = v0+v
        else:
            dp[i+1][w0+w] = max(dp[i+1][w0+w], v0+v)
print(max(dp[-1].values()))

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))
N, W = inpl()

DP = [0]*(W+1)
for _ in range(N):
    DP2 = [0]*(W+1)
    w, v = inpl()
    for i in range(w):
        DP2[i] = DP[i]
    for i in range(w, W+1):
        DP2[i] = max(DP[i], DP[i-w]+v)
    DP = DP2
print(DP[-1])

Submission status: Accepted

Solution code:

n, w = map(int, raw_input().split())
items = []
for _ in range(n):
    wi, vi = map(int, raw_input().split())
    items.append((wi, vi))

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

Submission status: Accepted

Solution code:
from sys import stdin

n, W = map(int, raw_input().strip().split())
inp = stdin.readlines()

dp = [[0 for i in xrange(W + 1)] for j in xrange(n)]

# dp[i][j] is total value if using only the first i elements, weight j can be taken
# and 0 otherwise

i = 0
for line in inp:
    wi, vi = map(int, line.strip().split())

    if i == 0:
        dp[0][wi] = vi
    else:
        for X in xrange(wi):
            dp[i][X] = dp[i - 1][X]
        for X in xrange(wi, W + 1):
            dp[i][X] = max(dp[i - 1][X], dp[i - 1][X - wi] + vi)

    i += 1

print max(dp[n - 1])

Submission status: Accepted

Solution code:
import numpy as np
from inspect import signature

N, W = map(int, input().split())
w = [0]
v = [0]
for i in range(N):
    tw, tv = map(int, input().split())
    w.append(tw)
    v.append(tv)
w = np.array(w)
v = np.array(v)

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

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

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

Submission status: Accepted

Solution code:
from sys import stdin

N, W = map(int, stdin.readline().split())
dp = [0] * (W + 1)
for i in range(N):
    w, v = [int(k) for k in stdin.readline().split()]
    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:
# using dp with memoization, TLE
from sys import stdin
N, W = map(int, input().split())
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]

dp = [0] * (W + 1)

for n in range(1, N + 1):
    w0, v0 = s[n - 1]
    for w in range(W, w0 - 1, -1):

        dp[w] = max(dp[w], dp[w - w0] + v0)

print(dp[W])

Submission status: Accepted

Solution code:
# using dp with memoization, TLE
from sys import stdin
N, W = map(int, input().split())
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]

dp = [0] * (W + 1)
next_dp = [0] * (W + 1)
for n in range(1, N + 1):
    for w in range(0, W + 1):
        if w >= s[n - 1][0]:
            next_dp[w] = max(next_dp[w], dp[w - s[n - 1][0]] + s[n - 1][1])
    dp = next_dp[:]
print(dp[W])

Submission status: Accepted

Solution code:
# using dp with memoization, TLE
from sys import stdin
N, W = map(int, input().split())
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]

dp = [0] * (W + 1)
next_dp = [0] * (W + 1)
for n in range(1, N + 1):
    for w in range(0, W + 1):
        if w >= s[n - 1][0]:
            next_dp[w] = max(next_dp[w], dp[w],
                             dp[w - s[n - 1][0]] + s[n - 1][1])
    dp = next_dp[:]
print(dp[W])

Submission status: Accepted

Solution code:
# using dp with memoization, TLE
from sys import stdin
N, W = map(int, input().split())
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]

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

for n in range(1, N + 1):
    for w in range(0, W + 1):
        if w == 0:
            dp[n][0] = 0
            continue
        if w < s[n - 1][0]:
            dp[n][w] = dp[n - 1][w]
        else:
            dp[n][w] = max(dp[n - 1][w],
                           dp[n - 1][w - s[n - 1][0]] + s[n - 1][1])

print(dp[N][W])

Submission status: Accepted

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

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

for item in range(N) :
    weight_i,value_i = L[item]
    for weight in range(W+1) :
        if weight - weight_i >= 0 :
            dp[item+1][weight] = max(dp[item][weight], dp[item][weight - weight_i] + value_i)
        else :
            dp[item+1][weight] = dp[item][weight]
ans = dp[N][W]

print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
a = []
for i in range(N):
    x,y = map(int,input().split())
    a.append([x,y])
dp = [0]*(W+1)
max_weight = 0

for w, v in a:
    max_w = min(max_weight, W-w)
    for old_v, from_i in zip(dp[max_w::-1], range(max_w, -1, -1)):
        if dp[from_i+w] < old_v + v:
            dp[from_i+w] = old_v + v
    max_weight = min(max_weight+w, W)

print(max(dp))

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
L = list(list(map(int,input().split())) for i in range(N))
dp = [[0 for j in range(W+1)] for i in range(N+1)] #dp[i][j] : i番目までのitemを認めたとき、weight = j のときの最大の価値

for item in range(N) :
    weight_i,value_i = L[item]
    for weight in range(W+1) :
        if weight - weight_i >= 0 :
            dp[item+1][weight] = max(dp[item][weight], dp[item][weight - weight_i] + value_i)
        else :
            dp[item+1][weight] = dp[item][weight]

ans = dp[N][W]

print(ans)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
L = list(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) :
    w_i,v_i = L[i]
    for weight in range(W+1) :
        if weight - w_i >= 0 :
            dp[i+1][weight] = max(dp[i][weight], dp[i][weight - w_i] + v_i)
        else :
            dp[i+1][weight] = dp[i][weight]

ans = dp[-1][-1]

print(ans)

Submission status: Accepted

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

n, k = IN()
dp = np.zeros(k + 1)

for i in range(n):
    w, c = IN()
    dp[w:] = np.maximum(dp[w:], dp[:-w] + c)
    
print(int(dp[-1]))

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
# FROM :  https://atcoder.jp/contests/dp/submissions/4127921

import numpy as np
N,W = list(map(int, input().split()))

wvlist = sorted( [ [int(x) for x in input().split()] for _ in range(N)] ) 

dp = [0] * (W+1)
cnt = 0
for w,v in wvlist:
    cnt = cnt+w
    for i in range(min(cnt, 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:
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 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[N][W])

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
cf=sorted( [ [int(x) for x in input().split()] for _ in range(N) ] )
dp = [0]*(W+1)
cnt=0
for w, c in cf:
    cnt=cnt+w
    for i in range(min(cnt, W), w-1, -1):
        if dp[i]<dp[i-w]+c:
            dp[i]=dp[i-w]+c
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, c = map(int, input().split())
    dp[w:] = np.maximum(dp[w:], dp[:-w] + c)
print(dp[W])

Submission status: Accepted

Solution code:
import sys
 
n, we = map(int, input().split())
 
cf = sorted( [[int(x) for x in sys.stdin.readline().split()] for _ in range(n)] )
 
dp=[0]*(we+1)
cnt=0
 
for w,c in cf:
    cnt=cnt+w
    for j in range(min(cnt, we-w), -1, -1):
        if dp[j+w]<(dp[j] + c): dp[j+w]=dp[j] + c
 
print(max(dp))

Submission status: Accepted

Solution code:
import sys

n, we = map(int, input().split())

cf = sorted( [[int(x) for x in sys.stdin.readline().split()] for _ in range(n)] )

dp=[0]*(we+1)
cnt=0

for w,c in cf:
    cnt=cnt+w
    for j in range(min(cnt, we-w), -1, -1):
        if dp[j+w]<(dp[j] + c): dp[j+w]=dp[j] + c

print(max(dp))

Submission status: Accepted

Solution code:
import sys

n, we = map(int, input().split())

cf=[(0, 0)]*n

cf = sorted( [[int(x) for x in sys.stdin.readline().split()] for _ in range(n)] )

dp=[0]*(we+1)

best=0
cnt=1
lim=0

for w,c in cf:
    cnt=cnt+w
    lim=min(cnt, we-w)
    for j in range(lim, -1, -1):
        if dp[j+w]<(dp[j] + c) : dp[j+w]=dp[j] + c

print(max(dp))

Submission status: Accepted

Solution code:
import sys

n, we = map(int, input().split())

cf=[(0, 0)]*n

cf = sorted(tuple( int(x) for x in sys.stdin.readline().split()) for _ in range(n))

dp=[0]*(we+1)

best=0
cnt=1
lim=0

for w,c in cf:
    cnt=cnt+w
    lim=min(cnt, we-w)
    for j in range(lim, -1, -1):
        if dp[j+w]<(dp[j] + c) : dp[j+w]=dp[j] + c

print(max(dp))

Submission status: Accepted

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

cf=[(0, 0)]*n

cf = sorted(tuple( int(x) for x in input().split()) for _ in range(n))

dp=[0]*(we+1)

best=0
cnt=1
lim=0

for w,c in cf:
    cnt=cnt+w
    lim=min(cnt, we-w)
    for j in range(lim, -1, -1):
        if dp[j+w]<(dp[j] + c) : dp[j+w]=dp[j] + c

print(max(dp))

Submission status: Accepted

Solution code:
import numpy as np 

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

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

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

print(w_all[W])

Submission status: Accepted

Solution code:
from sys import stdin, stdout

INF = float('inf')
n, W = map(int, stdin.readline().split())

dp = [[-INF for i in range(W + 1)] for j in range(2)]
dp[0][0] = 0
cur = 0

for i in range(n):
    w, c = map(int, stdin.readline().split())
    for j in range(W + 1):
        dp[cur ^ 1][j] = max(dp[cur ^ 1][j], dp[cur][j])
        
        if j + w <= W:
            dp[cur ^ 1][j + w] = max(dp[cur ^ 1][j + w], dp[cur][j] + c)
        
        dp[cur][j] = -INF
    
    cur ^= 1

stdout.write(str(max(dp[cur])))

Submission status: Accepted

Solution code:
import numpy as np
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

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

Submission status: Accepted

Solution code:
import numpy as np

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

value = np.zeros(W+1, dtype=np.int64) #value[w]は全重さwのときの持ち帰る品の価値の総和の最大値 

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

print(value[-1])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N, W = [int(_) for _ in input().split()]
WV = [[int(_) for _ in input().split()] for _ in range(N)]
dp = {}
dp[0] = 0
for w, v in WV:
    dp_o = dp.copy()
    for k in dp_o:
        if k + w <= W:
            dp[k + w] = max(dp_o.get(k + w, 0), dp_o[k] + v)
print(max([v for k, v in dp.items()]))

Submission status: Accepted

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

dp = [0]*(W+1)

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

print(dp[W])

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_d
#2019-01-13
import numpy as np
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    a, b = map(int, input().split())
    w += [a]
    v += [b]

DP = np.zeros(W+1, dtype=int)
# i 円以下で買える商品の最大価値
for i in range(N):
    DP[w[i]:] = np.maximum(DP[:-w[i]]+ v[i], DP[w[i]:])
print(DP[-1])

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import numpy as np


input = sys.stdin.readline
N, W = map(int, input().split())
dp = np.zeros(W+1, dtype=int)

for _ 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:
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 n_ in range(1, n+1):
    for w_ in range(1, w+1):
        temp_w = wv[n_-1][0]
        temp_v = wv[n_-1][1]
        
        if temp_w <= w_:
            dp[n_][w_] = max(dp[n_-1][w_-temp_w]+temp_v, dp[n_-1][w_])
        else:
            dp[n_][w_] = dp[n_-1][w_]

print(dp[n][w])

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
W_list = []
V_list = []
for i in range(N):
    w, v = map(int, input().split())
    W_list.append(w)
    V_list.append(v)
dp = [[0]*(W+1)]
for n in range(N):
    tmp = [0] * (W + 1)
    tmp_w = W_list[n]
    tmp_v = V_list[n]
    for w in range(W+1):
        if w-tmp_w >= 0:
            tmp[w] = max(dp[-1][w], dp[-1][w-tmp_w] + tmp_v)
        else:
            tmp[w] =dp[-1][w]
    dp.append(tmp)
print(dp[-1][-1])

Submission status: Accepted

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

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

for w,v in A:
	for i in range(W,-1,-1):
		if dp[i] is not None:
			if 0<=i+w<=W:
				dp[i+w]=max( dp[i+w],  dp[i]+v )
print max(dp)

Submission status: Accepted

Solution code:
from numpy import*
f=lambda:map(int,input().split())
N,W=f()
T=zeros(W+1,'i8')
exec('w,v=f();T[w:]=maximum(T[w:],T[:-w]+v);'*N)
print(T[-1])

Submission status: Accepted

Solution code:
from numpy import*
f=lambda:map(int,input().split())
N,W=f()
J=arange(0,W+1,1,'i8')
T=J*0
exec('w,v=f();T=maximum(T,(T[J-w]+v)*(J>=w));'*N)
print(T[-1])

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
ws, vs = zip(*[map(int, input().split()) for _ in range(N)])

def maxvalue_recursive(N, W):
    def memoize(func):
        func.d = d = {}
        def _f(*va):
            if va not in d: d[va] = func(*va)
            return d[va]
        return _f

    @memoize
    def maxvalue(i, w):
        if i < 0: return 0
        if w < ws[i]:
            return maxvalue(i - 1, w)
        else:
            return max(maxvalue(i - 1, w), maxvalue(i - 1, w - ws[i]) + vs[i])

    res = maxvalue(N - 1, W)
    return res

def maxvalue_dp(N, W, ws, vs):
    import numpy as np
    dp = np.zeros(W + 1, 'int64')
    ws = np.array(ws, 'int64')
    vs = np.array(vs, 'int64')
    for i in range(N):
        idx = np.arange(W + 1) - ws[i]
        dp = np.maximum(dp, (dp[idx] + vs[i]) * (idx >= 0))
    return dp[-1]

#print(maxvalue_recursive(N, W))
print(maxvalue_dp(N, W, ws, vs))

#import timeit
#print(timeit.timeit('maxvalue_recursive(N, W)', globals=globals(), number=10000))
#print(timeit.timeit('maxvalue_dp(N, W)', globals=globals(), number=10000))

Submission status: Accepted

Solution code:
import numpy as np

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

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

for _ in range(N):
  w,v=map(int,input().split())
  #dp[:-w]までの部分は、wの荷物を抱えても重量制限を超えないため、
  #ここに価値を乗せたものと今までのものを要素ごとに比べるnp.maximumを使う
  dp[w:]=np.maximum(dp[:-w]+v,dp[w:])

print(dp[W])

Submission status: Accepted

Solution code:
import sys
import numpy as np
N, W = map(int, input().split())
it = iter(map(int, sys.stdin.read().split()))
dp = np.zeros(W + 1, dtype=np.int64)
for w, v in zip(it, it):
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
import numpy as np
N, W = map(int, input().split())
it = iter(map(int, sys.stdin.read().split()))
dp = np.zeros(W + 1, dtype=int)
for w, v in zip(it, it):
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
N, W = map(int, input().split())
dp = [0] * (W + 1)
for weight, value in map(lambda x: map(int, x.split()), sys.stdin):
    for w in range(W - weight, -1, -1):
        if dp[w + weight] < dp[w] + value:
            dp[w + weight] = dp[w] + value
print(dp[-1])

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,w = LI()
    aa = sorted([LI() for _ in range(n)])
    r = [0] * (w+1)
    mx = 0
    for a,b in aa:
        mx += a
        for i in range(min(mx, w-a),-1,-1):
            if r[i+a] < b + r[i]:
                r[i+a] = b + r[i]

    return max(r)


print(main())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
raw_input = sys.stdin.readline
N,W = map(int,raw_input().split())
dp = [0 for x in range(W+1)]
for i in range(N):
    a,b = map(int,raw_input().split())
    for j in range(W,a-1,-1):
        dp[j] = max(dp[j],dp[j-a]+b)
print max(dp)

Submission status: Accepted

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


if __name__ == "__main__":
    main()

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())
w_v = [list(map(int, input().split())) for _ in range(N)]


# 1~i-1番目の品物から重さの総和がj以下になるように選んだときの価値
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

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

print(max(dp[N]))

Submission status: Accepted

Solution code:
n,wgt=map(int,input().split())
a=[]
v=[]
for i in range(n):
    x,y=map(int,input().split())
    a.append(x)
    v.append(y)

dp=[[0 for x in range(wgt+1)] for x in range(n+1)]

for i in range(n+1):
    for j in range(wgt+1):
        if i==0 or j==0:
            dp[i][j]=0
        elif a[i-1]<=j:
            dp[i][j]=max(v[i-1]+dp[i-1][j-a[i-1]],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]

print(dp[n][wgt])

Submission status: Accepted

Solution code:
N,W=[int(x) for x in raw_input().split()]
A=[]
for i in range(N):
    w,v=[int(x) for x in raw_input().split()]
    A.append([w,v])
B=[[ 0  for i in range(W+1)] for j in range(N)]
B[0][W-A[0][0]]=A[0][1]

for i in range(1,N):
    w,v=A[i]
    for j in range(W-w+1):
        B[i][j]=max(B[i-1][j], B[i-1][j+w]+v)
    for j in range(W-w+1, W+1):
        B[i][j]=B[i-1][j]
print(max(B[-1]))

Submission status: Accepted

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

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

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

print(dp[i][W])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np

ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


N, W = ds_in()

values = np.zeros(W + 1, dtype=int)  # 重さi以下の最大価値
for _ in range(N):
    pre = values.copy()
    wv = ds_in()  # [weight, value]
    values[wv[0]:] = np.maximum(values[:-wv[0]] + wv[1], values[wv[0]:])

print(values[-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wl = [0]*(N+1)
vl = [0]*(N+1)
for i in range(1, N+1):
    wl[i], vl[i] = map(int, input().split())

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

for i in range(1, N+1):
    w, v = wl[i], vl[i]
    for k in reversed(range(MAX+1-w)):
        if k + w > MAX:
            break
        else:
            dp[k+w] = max(dp[k+w], dp[k] + v)
print(max(dp))

Submission status: Accepted

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