Problem:


Score : 100 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

1 \leq N \leq 100

1 \leq W \leq 10^5

1 \leq w_i \leq W

1 \leq v_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

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

Sample Input 1

3 8
3 30
4 50
5 60

Sample Output 1

90

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

Sample Input 2

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

Sample Output 2

5000000000

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

Sample Input 3

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

Sample Output 3

17

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



Sample input:
3 8
3 30
4 50
5 60


Sample output:
90

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
 
n,w=map(int,input().split())
dp=[0]*(w+1)
 
def ans(n,w):
  for _ in range(n):
    c,p=map(int,input().split())
    for j in range(w,c-1,-1):
      tmp=dp[j-c]+p
      if dp[j]<tmp:
        dp[j]=tmp
  return max(dp)
print(ans(n,w))

Submission status: Accepted

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

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

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

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

Submission status: Accepted

Solution code:
import sys
import numpy as np

ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nms = lambda: map(str, sys.stdin.readline().split())
nl = lambda: list(nm())

n, w = nm()
lis = [nl() for _ in range(n)]
lis.insert(0, [0, 0])
dp = np.zeros(w + 1, dtype=np.int64)

for i in range(1, n + 1):
    dp[lis[i][0]:] = np.maximum(dp[lis[i][0]:], dp[:-lis[i][0]] + lis[i][1])

print(dp[-1])

Submission status: Accepted

Solution code:
from itertools import accumulate
N,W = [int(i) for i in input().split()]

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

li = [[int(i) for i in input().split()] for _ in range(N)]
dp[0][li[0][0]] = li[0][1]
dp[0] = list(accumulate(dp[0]))
for i in range(1,N):
    for j in range(W+1):
        if j < li[i][0]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j-li[i][0]]+li[i][1],dp[i][j-1],dp[i-1][j])

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

Submission status: Accepted

Solution code:
import numpy as np

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

dp = np.zeros(ww+1)

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

print(int(max(dp)))

Submission status: Accepted

Solution code:
import sys

n, w = map(int, sys.stdin.readline().split())
weight = []
value = []
for i in range(n):
    wi, vi = map(int, sys.stdin.readline().split())
    weight.append(wi)
    value.append(vi)

wght = [0] * (w+1)

for i in range(n):
    for j in range(w - weight[i], -1, -1):
        wght[j + weight[i]] = max(wght[j + weight[i]], wght[j] + value[i])

print(wght[-1])

Submission status: Accepted

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

d = sorted(d)
dp = [[0] * (W + 1) for i in range(N + 1)]
for i in range(N):
    for w in range(W + 1):
        w1, v1 = d[i]
        dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])
        if w + w1 <= W:
            dp[i + 1][w + w1] = max(dp[i + 1][w + w1], dp[i][w] + v1)


num = 0
for i in range(W + 1):
    num = max(num, dp[N][i])

print(num)

Submission status: Accepted

Solution code:
#!/usr/bin/python3

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

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

    for i in range(N):
        weight, value = map(int, input().split())

        dp[i+1][:weight] = dp[i][:weight]
        dp[i+1][weight:] = np.maximum(dp[i][weight:], dp[i][:-weight] + value)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
w,v = [],[]
for i in range(N):
    wi,vi = map(int,input().split())
    w.append(wi)
    v.append(vi)
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[N][W])

Submission status: Accepted

Solution code:
import sys
import numpy as np

# input処理を高速化する
input = sys.stdin.readline

# 入力
N, W = map(int, input().split())

def knapsack(n, w):
    # dp[i][j] : i番目の品物で重さj以下の価値の最大値
    dp = np.zeros([N+1, W+1], dtype='int64')
    # forは関数の中で回す。
    for i in range(N):
        w, v = map(int, input().split())
        # i+1番目でwより小さい場合は、i番目と変更なし
        dp[i+1][:w] = dp[i][:w]
        dp[i+1][w:] = np.maximum(dp[i][w:], dp[i][:-w] + v)
        # print(dp)
    return dp[-1][-1]

print(knapsack(N, W))

Submission status: Accepted

Solution code:

import sys

input = sys.stdin.readline

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

dp = [0] * (W + 1)
def knapsack(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for wk in range(W, w-1, -1):
            tv = dp[wk - w] + v
            if tv > dp[wk]:
                dp[wk] = tv
    return dp[-1]

print(knapsack(N, W))

Submission status: Accepted

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

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

  for w, v in items:  
    for wk in range(W, w - 1, -1):
      tv = dp[wk - w] + v
      if tv > dp[wk]:
        dp[wk] = tv
  res = max(dp)
  print(res)

if __name__ == "__main__":
  solve()

Submission status: Accepted

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

dp = [0]  * (W + 1)
def knapsack():
  for i in range(N):
    w, v = map(int, input().split())
    for wk in range(W, w - 1, -1):
      tv = dp[wk - w] + v
      if tv > dp[wk]:
        dp[wk] = tv
knapsack()
res = max(dp)
print(res)

Submission status: Accepted

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

dp = [0]  * (W + 1)
def knapsack():
  for i in range(N):
    w, v = map(int, input().split())
    for wk in range(W, w - 1, -1):
      tv = dp[wk - w] + v
      if tv > dp[wk]:
        dp[wk] = tv
  return max(dp)
print(knapsack())

Submission status: Accepted

Solution code:
def nap(n, cap):
    val = [0] * (cap + 1)
    for _ in range(n):
        w, v = map(int, input().split())
        for wk in range(cap, w - 1, -1):
            nv = val[wk - w] + v
            if val[wk] < nv:
                val[wk] = nv
    return max(val)


n, cap = map(int, input().split())
print(nap(n, cap))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def nap(n, cap):
    val = [0] * (cap + 1)
    for _ in range(n):
        w, v = map(int, input().split())
        for wk in range(cap, w - 1, -1):
            nv = val[wk - w] + v
            if val[wk] < nv:
                val[wk] = nv
    return max(val)


n, cap = map(int, input().split())
print(nap(n, cap))

Submission status: Accepted

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

n, cap = map(int, input().split())
val =[0]*(cap+1)
def nap(n,cap):
    for _ in range(n):
        w, v = map(int, input().split())
        for wk in range(cap,w-1,-1):
            nv=val[wk-w]+v
            if val[wk]<nv:
                val[wk]=nv
    return max(val)
print(nap(n,cap))

Submission status: Accepted

Solution code:

import numpy as np
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
value=np.zeros((n+1,w+1),dtype=int)
for i in range(n):
    wei=wv[i][0]
    value[i+1][:wei]=value[i][:wei]
    # np.maximum([1,-3,2],0) == [1,0,2]
    value[i+1][wei:]=np.maximum(value[i][wei:],value[i][:-wei]+wv[i][1])
# print(value)
print(value[n][w])

Submission status: Accepted

Solution code:
def solve():
    N, W = map(int, input().split())
    weight = [0 for i in range(N)]
    value = [0 for i in range(N)]
    for i in range(N):
        weight[i], value[i] = map(int, input().split())
    dp = [0 for w in range(W + 1)]

    for i in range(N):
        wi = weight[i]
        vi = value[i]
        for w in range(W, -1, -1):
            _w = w + wi
            _v = dp[w] + vi
            if _w > W: continue
            if _v <= dp[_w]: continue
            dp[_w] = _v
    return dp[-1]

print(solve())

Submission status: Accepted

Solution code:
import numpy as np

N, W = map(int, input().split())
wv = [[0, 0]] + [[int(_) for _ in input().split()] for _ in range(N)]
dp = np.zeros([N+1, W+1], dtype=int)

for i in range(1, N+1):
    key = wv[i][0]
    dp[i][:key] = dp[i-1][:key]
    dp[i][key:] = np.maximum(dp[i-1][key:], dp[i-1][:-key] + wv[i][1])

print(dp[N][W])

Submission status: Accepted

Solution code:
import math
import copy
from collections import defaultdict, Counter
from itertools import product
from bisect import bisect_left, bisect_right
# import numpy as np

def s_inpl(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
INF = float("inf")

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

w, v = [], []
for _ in range(N):
    wi, vi = s_inpl()
    w.append(wi)
    v.append(vi)

for i in range(N):
    for sum_w in range(W+1):

        # i番目の品物が選べて，選ぶとき
        if sum_w >= w[i]:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w-w[i]] + v[i])

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

Submission status: Accepted

Solution code:
import numpy as np

n,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(n)]
dp=np.zeros(w+1,dtype=np.int64)
#print(np.max(dp[0:w-l[0][0]]+np.array(l[0][1]),dp[l[0][0]:w]))
for i in range(n):
    if l[i][0]<=w:
        dp[l[i][0]:w+1]=np.maximum(dp[0:w+1-l[i][0]]+np.array(l[i][1]),dp[l[i][0]:])
    #print(dp)
print(max(dp))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

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

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

Submission status: Accepted

Solution code:
def main():
    N, W = [int(n) for n in input().split()]
    baggages = [[int(n) for n in input().split()] for i in range(N)]

    VALUE, WEIGHT = 1, 0
    dp = [[-1] * (W+1) for n in range(N)]
    # dp[baggage][weight] := baggage番目までの荷物を使ってweight以下に抑える
    dp[0] = [0 if weight < baggages[0][WEIGHT] else baggages[0][VALUE] for weight in range(W+1)]

    for baggage in range(N):
        for max_weight in range(W+1):
            if dp[baggage][max_weight] != -1:
                continue
            bag_w = baggages[baggage][WEIGHT]
            bag_v = baggages[baggage][VALUE]
            val1 = dp[baggage-1][max_weight]
            val2 = dp[baggage-1][max_weight-bag_w]+bag_v if max_weight >= bag_w else 0
            dp[baggage][max_weight] = max(val1, val2)
            
    print(dp[N-1][W])



if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,w = map(int,input().split())
weighs,values = [],[]
for i in range(n):
    wa,va = map(int,input().split())
    weighs.append(wa)
    values.append(va)

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

for i in range(w+1):
    maxa = 0
    useda = [0 for i in range(n)]
    for k in range(n):
        if used[i-weighs[k]][k] == 0 and i-weighs[k] >= 0 and dp[i-weighs[k]]+values[k]>maxa:
                maxa = dp[i-weighs[k]]+values[k]
                useda = used[i-weighs[k]][:]
                useda[k] = 1
    dp[i] = maxa
    used[i] = useda

#print(used)
print(max(dp))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    n = I()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n-2):
        dp[i+1] = min(dp[i+1],dp[i]+abs(h[i+1]-h[i]))
        dp[i+2] = min(dp[i+2],dp[i]+abs(h[i+2]-h[i]))
    dp[n-1] = min(dp[n-1],dp[n-2]+abs(h[n-1]-h[n-2]))
    print(dp[n-1])
#B
def B():
    n,k = LI()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n):
        for j in range(1,min(n-i,k+1)):
            dp[i+j] = min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
    print(dp[n-1])

#C
def C():
    n = I()
    v = LIR(n)
    dp = [[0,0,0] for i in range(n+1)]
    for i in range(n):
        dp[i+1][0] = max(dp[i+1][0],dp[i][1]+v[i][0],dp[i][2]+v[i][0])
        dp[i+1][1] = max(dp[i+1][1],dp[i][2]+v[i][1],dp[i][0]+v[i][1])
        dp[i+1][2] = max(dp[i+1][2],dp[i][0]+v[i][2],dp[i][1]+v[i][2])
    print(max(dp[n]))

#D
def D():
    n,W = LI()
    g = LIR(n)
    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)[::-1]:
            w,v = g[i]
            if j >= w:
                dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
            else:
                dp[i+1][j] = max(dp[i+1][j],dp[i][j])
    print(max(dp[n]))
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    n = II()
    h = LI()
    dp = [0 for i in range(n)]
    dp[1] = abs(h[0] - h[1])
    for i in range(2,n):
        dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]))
    print(dp[n-1])
    return

#B
def B():
    n, K = LI()
    h = LI()
    dp = [float("INF") for i in range(n + K + 1)]
    dp[0] = 0
    for i in range(n):
        for k in range(1, K + 1):
            if i + k >= n:
                break
            dp[i + k] = min(dp[i + k], dp[i] + abs(h[i] - h[i + k]))
    print(dp[n-1])
    return

#C
def C():
    n = II()
    abc = LIR(n)
    dp = [0 for i in range(3 * n + 1)]
    dp[0] = abc[0][0]
    dp[1] = abc[0][1]
    dp[2] = abc[0][2]
    for i in range(1,n):
        dp[3 * i] = max(dp[3 * i], dp[3 * (i - 1) + 1] + abc[i][0], dp[3 * (i - 1) + 2] + abc[i][0])
        dp[3 * i + 1] = max(dp[3 * i + 1], dp[3 * (i - 1) + 2] + abc[i][1], dp[3 * (i - 1)] + abc[i][1])
        dp[3 * i + 2] = max(dp[3 * i + 2], dp[3 * (i - 1) + 1] + abc[i][2], dp[3 * (i - 1)] + abc[i][2])
    dp[3 * n] = max(dp)
    print(dp[3*n])

    return

#D
def D():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**5
    1≤wi≤W
    1≤vi≤10**9"""
    n, w = LI()
    wv = LIR(n)
    dp = [[0 for k in range(w + 1)] for i in range(n + 2)]
    for i in range(1,n + 1):
        for j in range(w + 1):
            if j < wv[i-1][0]:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - wv[i - 1][0]] + wv[i - 1][1])
    print(dp[n+1][w])

    
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#I
def I():
    return 
#J

#K

#L

#M
#N
# O
# P
# Q
# R
# S
# T
# U
# V
# W
# X
# Y
# Z


#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys


N,W = map(int, sys.stdin.readline().rstrip().split())
w = [0] * N
v = [0] * N
for i in range(N):
  w[i], v[i] = list(map(int, sys.stdin.readline().rstrip().split()))

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

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

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

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

Submission status: Accepted

Solution code:
import numpy as np
n,w=map(int,input().split())
a=np.zeros([n,w+1],dtype=int)
c,d=map(int,input().split())
a[0][c:]=d
for i in range(1,n):
    e,f=map(int,input().split())
    a[i][:e]=a[i-1][:e]
    a[i][e:]=np.maximum(a[i-1][e:],a[i-1][:-e]+f)
print(a[-1][-1])

Submission status: Accepted

Solution code:
import numpy as np


N, W = map(int, input().split())
w_v = [[int(_) for _ in input().split()] for _ in range(N)]
dp = np.zeros([N, W+1], dtype=int)
dp[0][w_v[0][0]:] = w_v[0][1]

for i in range(1, N):
    key = w_v[i][0]
    dp[i][:key] = dp[i-1][:key]
    dp[i][key:] = np.maximum(dp[i-1][key:], dp[i-1][:-key] + w_v[i][1])

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

def ans(N, W):
    d = [0] * (W+1)

    for i in range(N):
        wi, vi = [int(i) for i in input().split()]
        for w in range(W, wi - 1, -1):
            v_ = d[w - wi] + vi
            if v_ > d[w]:
                d[w] = v_
    return d[W]

print(ans(N, W))

Submission status: Accepted

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

## dp[i][j]:i番目までのアイテムを重さjのナップサックに詰めるときの最大価値
dp = [[0]*(w+1) for i in range(n+1)]
for i in range(n+1):
  for j in range(w+1):
    if j-info[i][0]>=0:
      dp[i][j] = max(dp[i-1][j],dp[i-1][j-info[i][0]]+info[i][1])
    else:
      dp[i][j] = dp[i-1][j]

print(dp[n][w])

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

def f(n, W):
    dp = [0] * (W + 1)
    for i in range(n):
        wi, vi = map(int, input().split())
        for w in range(W, wi - 1, -1):
            v_ = dp[w - wi] + vi
            if dp[w] < v_:
                dp[w] = v_
    return(dp[-1])

n, w = map(int, input().split()) # 1 <= n <= 100, 1 <= w <= 10^5
print(f(n, w))

Submission status: Accepted

Solution code:
def d_knapsack1(N, W, Goods):
    """
    N個の品物のi番目について、重さはw_i, 価値はv_iである。
    品物のいくつかを選んでナップサックに入れるが、品物の重さの総和はW以下とする。
    品物の価値の総和の最大値を求めよ。
    ※ 1 <= w_i <= W <= 10^5 と、重さの制約がゆるめ
    """
    import numpy as np
    # dp[w]: 重さwの品物の入れ方で達成できる価値の最大値
    dp = np.zeros(W + 1, dtype=np.int64)
    for w, v in Goods:
        # 重さi(0<=i<=W-w)のときの価値に対し注目している荷物を入れて、
        # 重さi+wのときの価値を更新する
        np.maximum(dp[:W + 1 - w] + v, dp[w:], out=dp[w:])
        # outで指定した箇所のみ上書き。与えないと新しく配列が作られる
    return dp[-1]

N, W = [int(i) for i in input().split()]
Goods = [[int(i) for i in input().split()] for j in range(N)]
print(d_knapsack1(N, W, Goods))

Submission status: Accepted

Solution code:
from sys import stdin
n,W=map(int,input().split())
dp=[0 for i in range(W+1)]
for i in range(n):
    w,v=map(int,stdin.readline().split())
    for j in range(W-w,-1,-1):
        dp[j+w]=max(dp[j]+v,dp[j+w])
print(dp[-1])

Submission status: Accepted

Solution code:
N, W = list(map(int,raw_input().split()))
dp = [0 for i in range(W+1)]
for i in range(N):
  wi, vi = list(map(int,raw_input().split()))
  for w in range(W-wi, -1, -1):
    dp[w+wi] = max(dp[w+wi],dp[w]+vi)
print(max(dp))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
n, W = map(int, input().split())
dp = np.zeros(W+1,'i8')
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(" "))
w,v = [0]*(N+1),[0]*(N+1)
for i in range(N):
    w[i+1],v[i+1] = map(int,input().split(" "))

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

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:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/3/2
Update on 2019/3/5
Solved on 2019/3/
@author: shinjisu
"""


# Educational Dynamic Programming
# import math
import numpy as np


def getInt(): return int(input())


# def getIntList(): return [int(x) for x in input().split()]
def getIntList(): return np.array(input().split(), dtype=np.longlong)


# def zeros(n): return [0]*n
def zeros(n): return np.zeros(n, dtype=np.longlong)


def getIntLines(n): return [int(input()) for i in range(n)]


def getIntMat(n):
    mat = []
    for i in range(n):
        mat.append(getIntList())
    return mat


def zeros2(n, m): return [zeros(m)]*n


ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7
INF = 10**18


def dmp(x, cmt=''):
    global debug
    if debug:
        if cmt != '':
            print(cmt, ':  ', end='')
        print(x)
    return x


def prob_A():  # Frog 1
    N = getInt()
    H = getIntList()
    dmp((N, H), 'N, H')
    c = zeros(N)
    c[1] = abs(H[1]-H[0])
    for i in range(2, N):
        c[i] = min(c[i-1] + abs(H[i]-H[i-1]),
                   c[i-2] + abs(H[i]-H[i-2]))
    dmp(c, 'c')
    return c[N-1]


def prob_B_TLE():  # Frog 2 3/16 TLE
    N, K = getIntList()
    H = getIntList()
    dmp((N, K, H), 'N, K, H')
    c = np.zeros(N)
    c[0] = 0
    for i in range(1, N):
        #c[i] = INF
        for j in range(max(0, i-K), i):
            c[i] = min(c[i], c[j] + abs(H[i]-H[j]))
    dmp(c, 'c')
    return c[N-1]


def prob_B():  # Frog 2
    N, K = getIntList()
    H = np.array(input().split(), dtype='int')
    dmp((N, K, H), 'N, K, H')
    c = np.zeros(N, dtype=np.longlong)
    c[0] = 0
    for i in range(1, N):
        c[i] = np.min(c[max(0, i-K):i] + np.abs(H[max(0, i-K):i] - H[i]))
    dmp(c, 'c')
    return c[N-1]


def prob_C():  # Vacation
    N = getInt()
    a = zeros(N)
    b = zeros(N)
    c = zeros(N)
    for i in range(N):
        a[i], b[i], c[i] = getIntList()
    dmp(N, 'N')
    dmp(a, 'a')
    dmp(b, 'b')
    dmp(c, 'c')
    dpa = zeros(N)
    dpb = zeros(N)
    dpc = zeros(N)
    dpa[0] = a[0]
    dpb[0] = b[0]
    dpc[0] = c[0]
    for i in range(1, N):
        dpa[i] += max(dpb[i-1], dpc[i-1]) + a[i]
        dpb[i] += max(dpc[i-1], dpa[i-1]) + b[i]
        dpc[i] += max(dpa[i-1], dpb[i-1]) + c[i]
    dmp(dpa, 'dpa')
    dmp(dpb, 'dpb')
    dmp(dpc, 'dpc')
    return max(dpa[N-1], dpb[N-1], dpc[N-1])


def prob_D():  # Knapsack 1
    N, W = getIntList()
    w, v = zeros(N), zeros(N)
    dmp((N, W))
    for i in range(N):
        w[i], v[i] = getIntList()
    dmp(w, 'weight')
    dmp(v, 'value')
    dp = zeros(W+1)
    dmp(dp.size)
    for i in range(N):
        dmp(dp, 'dp')
        dmp(w[i],'w[i]')
        #prevIdx = max(0, i-w[i])
        #dmp(prevIdx,'prevIdx')
        dmp(w[i],'w[i]')
        dp[w[i]:] = np.maximum(dp[w[i]:], 
                                  dp[:W-w[i]+1] + v[i])
    dmp(dp, 'dp')
    return dp[W]


debug = False  # True False
ans = prob_D()
print(ans)
#for row in ans:
#    print(row)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import os
import sys
from atexit import register
from io import StringIO

sys.stdin = StringIO(os.read(0, os.fstat(0).st_size).decode())
sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue().encode()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

n, m = 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] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

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

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

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:
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+1-w] + c)     
print(dp[W])

Submission status: Accepted

Solution code:

N, W  = (int(i) for i in input().split()) 
w = []
v = []
for i in range(N):
    aa, bb = [int(i) for i in input().split()] 
    w.append(aa)
    v.append(bb)

# dp[i][w] : i-1番目までで重さがwのときの最大価値

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

print(dp[N][W])

Submission status: Accepted

Solution code:
# /user/bin/python
# -*- coding: utf-8 -*-
import numpy as np
import sys

N,W = map(int, sys.stdin.readline().rstrip().split())

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

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

print(dp[-1])

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(2)]
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[1][j]=max(v+k[0][j-w],k[0][j])
        else:
            k[1][j]=k[0][j]
    k[0]=[i for i in k[1]]
    k[1]=[0]*(W+1)
print(k[0][-1])