Problem:


Score : 100 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

1 \leq N \leq 100

1 \leq W \leq 10^5

1 \leq w_i \leq W

1 \leq v_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

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

Sample Input 1

3 8
3 30
4 50
5 60

Sample Output 1

90

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

Sample Input 2

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

Sample Output 2

5000000000

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

Sample Input 3

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

Sample Output 3

17

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



Sample input:
3 8
3 30
4 50
5 60


Sample output:
90

Submission status: Accepted

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

    ans = f(N, W, wv)
    print(ans)


def f(N, W, wv):
    """
    品物100を入れる入れないの 2^100 試せばOKだが、無理

    Nの入れる個数
        0から100
        正確にはN個までの選択なので、N個入れていないときもある
    最終容量     
        0から10^5
        正確にはWまでの重さなので、W以下のときもある
    10^7なら間に合いそう

    追加できるならば、追加してみる
    追加するものと入れ替えを試してみる
        追加の重さを引いたときの価値
        前の価値まま
            の大きい方
    """
    dp = [[-float("inf")] * (W + 1)
          for _ in range(N + 1)]

    # 品物を入れていないならば、価値はない
    # 品物を入れていないならば、重さはないので、価値はない
    # wi, vi >= 1 より
    dp[0] = [0] * (W + 1)
    for i in range(1, N + 1):
        dp[i][0] = 0

    for i, (w, v) in enumerate(wv, 1):
        for _w in range(1, W + 1):
            # まずは1つ前で補完, 価値は品物追加すれば単調増加なのでOK
            bef = dp[i-1][_w]
            dp[i][_w] = bef

            # 追加
            # 品物ループの内側にある重さのループではあるが、
            # このループでは何回も追加しないようになっている
            if _w + w <= W:
                changed = dp[i-1][_w] + v
                bef = dp[i-1][_w + w]
                # 補完と入れ替えを合わせると追加も兼ねている？
                # dp[i][_w + w] = max(bef, changed)

            # 入れ替え
            if _w - w >= 0:
                changed = dp[i-1][_w - w] + v
                bef = dp[i-1][_w]
                dp[i][_w] = max(bef, changed)

    # 補完により必ず[N][W] で最大
    # ans = max(dp[N])
    ans = dp[N][W]

    # from pprint import pprint
    # import sys
    # pprint(dp, stream=sys.stderr)
    return ans


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def 解():
    input = sys.stdin.readline

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

Submission status: Accepted

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


N, W = [int(elem) for elem in fin().split()]
weight_value_pairs = tuple(tuple(int(elem) for elem in fin().split()) for _ in range(N))

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

print(max(dp))

Submission status: Accepted

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

dp = [0] * (W+1)
for i in range(N)[::-1]:
  a = dp[:]
  for w in range(W+1):
    if A[i] <= w and a[w] < dp[w-A[i]] + V[i]:
      a[w] = dp[w-A[i]] + V[i]
  dp = a

print(dp[W])

Submission status: Accepted

Solution code:
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)] for i in range(N+1)]
for j in range(W+1):
    dp[0][j]=0
for i in range(N):
    for j in range(W+1):
        dp[i+1][j]=dp[i][j]
        if j-w[i]>=0:
            if dp[i][j]<dp[i][j-w[i]]+v[i]:
                dp[i+1][j]=dp[i][j-w[i]]+v[i]
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 = [{} for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    w,v = src[i-1]
    for w0,v0 in dp[i-1].items():
        if w0 in dp[i]:
            dp[i][w0] = max(dp[i][w0], v0)
        else:
            dp[i][w0] = v0
        if w0+w > W: continue
        if w0+w in dp[i]:
            dp[i][w0+w] = max(dp[i][w0+w], v0+v)
        else:
            dp[i][w0+w] = v0+v
print(max(dp[-1].values()))

Submission status: Accepted

Solution code:
N, W = map(int, raw_input().split())
obj = []
for i in xrange(N):
    w, v = map(int, raw_input().split())
    obj.append((w, v))
dp = [[-1 for _ in xrange(W+1)] for i in xrange(N)]

dp[0][0] = 0
dp[0][obj[0][0]] = obj[0][1]

for i in xrange(1, N):
    w, v = obj[i]
    for j in xrange(W+1):
        if dp[i-1][j] != -1:
            dp[i][j] = dp[i-1][j]
    for j in xrange(W+1):
        if dp[i-1][j] != -1 and j + w <= W:
            dp[i][j+w] = max(dp[i-1][j]+v, dp[i][j+w])
res = 0
for i in xrange(W+1):
    res = max(dp[N-1][i], res)
print res

Submission status: Accepted

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

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

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

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

print(dp[N][W])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def main():
    N, W = map(int, raw_input().split())
    Items = [list(map(int, raw_input().split())) for i in range(N)]
    
    # dp[i] := 容量Wのナップサックにおける価値の総和の最大値
    dp = [0] * (W + 1)
    
    for w, v in Items:
        for i in range(W, -1, -1):
            if i < w:
                continue
            dp[i] = max(dp[i], dp[i - w] + v)
    
    print(dp[-1])

main()

Submission status: Accepted

Solution code:
import sys

n, W = map(int, input().split())
dp = [-1] * (W + 1)
dp[0] = 0
for line in sys.stdin.readlines():
    w, v = map(int, line.split())
    for i in range(W - w, -1, -1):
        if dp[i] == -1:
            continue
        dp[i + w] = max(dp[i + w], dp[i] + v)
print(max(dp))

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

print(dp[N][W])

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()
wv = []
for _ in range(n):
    wv.append(tuple(li()))
    
dp = [[0]*(w+1) for _ in range(n+1)]

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

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
items = []
 
for i in range(n):
    items.append(list(map(int, input().split())))
 
 
def knapsack(n, w, items):
    c = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
    g = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
 
    for i in range(w + 1):
        c[0][i] = 0
        g[0][i] = 1
 
    for i in range(n + 1):
        c[i][0] = 0
 
    for i in range(1, n + 1):
        for j in range(1, w + 1):
            c[i][j] = c[i - 1][j]
            g[i][j] = 0
            item = items[i - 1]
            if item[0] > j:
                continue
            if item[1] + c[i - 1][j - item[0]] > c[i - 1][j]:
                c[i][j] = item[1] + c[i - 1][j - item[0]]
                g[i][j] = 1
 
    max_value = c[n][w]
    routes = []
    for i in range(n, 0, -1):
        if g[i][w] == 1:
            routes.append(i)
            w -= items[i - 1][0]
    return max_value, routes
 
 
result, _ = knapsack(n, w, items)
print(result)

Submission status: Runtime Error

Solution code:

def knapsack(n,w,v,we,val,dp):
    if(dp[n][we]!=-1):
        return dp[n][we]

    if(we==0 or n==0):
        return val
    res=0
    if(we<w[n-1]):
        res=knapsack(n-1,w,v,we,val,dp)
    else:
        res=max(knapsack(n-1,w,v,we,val,dp),knapsack(n-1,w,v,we-w[n-1],val+v[n-1],dp))
        
    dp[n][we]=res
    return res
    
for cases in range(int(input())):
    dp=[]
    for i in range(1001):
        x=[]
        for j in range(1001):
            x.append(-1)
        dp.append(x)
            
    n=int(input())
    we=int(input())
    for i in range(n):
      a,b=list(map(int,input().split()))
    w.append(a)
    v.append(b)
    val=0
    p=knapsack(n,w,v,we,val,dp)
    print(p)

Submission status: Runtime Error

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

dp = [0] * (w + 1)
for wi, vi in wv:
    for sum_w in range(w, wi - 1, -1):
        v = dp[sum_w - wi] + vi
        if dp[sum_w] < v:
            dp[sum_w] = vi

print(max(dp[w]))

Submission status: Runtime Error

Solution code:

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

dp = [0] * (w + 1)
for wi, vi in wv:
    for sum_w in range(w, wi - 1, -1):
        v = dp[sum_w - wi] + vi
        if dp[sum_w] < v:
            dp[sum_w] = vi

print(max(dp[w]))

Submission status: Runtime Error

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

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

print(dp[n][w])

Submission status: Runtime Error

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

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

print(dp[n][w])

Submission status: Runtime Error

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

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

print(dp[n][w])

Submission status: Runtime Error

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

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

print(dp[n][w])

Submission status: Runtime Error

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

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

print(dp[n][w])

Submission status: Runtime Error

Solution code:
n, sum_w = map(lambda x: int(x), input().split())

# goods = list[]
all_weights = []
all_values = []
for _ in range(n):  
    w, v = map(lambda x: int(x), input().split())
    all_weights.append(w)
    all_values.append(v)
    
def get_max_value(weights, values, max_sum_weight):
    if (len(weights) <= 0) | (max_sum_weight < min(weights)):
        return 0

    max_value = 0
    for i in range(len(weights)):
        if weights[i] <= max_sum_weight:
            remaining_weights = weights[:i] + weights[i+1:]
            remaining_values = values[:i] + values[i+1:]
            max_value = max(max_value, values[i] + get_max_value(remaining_weights, remaining_values, max_sum_weight - weights[i]))
    return max_value

print(get_max_value(all_weights, all_values, sum_w))

Submission status: Runtime Error

Solution code:
n,w = map(int,input().split())
wt = [];c = []
for _ in range(n):
  x,y = map(int,input().split())
  wt.append(x)
  c.append(y)
dp = [[0]*(w+1) for _ in range(n+1)]

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

Submission status: Runtime Error

Solution code:
N,W=[int(x) for x in input().split()]
w=[-1 for _ in range(N)]
v=[-1 for _ in range(N)]
for i in range(N):
	w[i],v[i]=[int(x) for x in input().split()]
#Constraints W<=10^5 w[i]<=10^5 and v[i]<=10^9
dp=[-1 for _ in range(W+1)]
dp[0]=0
for i in range(n):
	for w in range(W,w[i]-1,-1):
		dp[w]=max(dp[w],dp[w-w[i]]+v[i])
for i in range(W,-1,-1):
	if dp[i]!=-1: print(dp[i]); break
# dp[w0] stores maximum value with weight =w0 and using 1...i

Submission status: Runtime Error

Solution code:
import numpy as np
INF = 2**60 # 無限大を表す値
N, W = map(int, input().split())
wv = [tuple(map(int, input().split())) for i in range(N)]
dp = np.full((N+1, W+1), -INF, dtype = np.int64)
dp[0][0] = 0 # 初期条件
for i, (w, v) in enumerate(wv):
    dp[i+1] = np.max(dp[i+1], dp[i])
    dp[i+1][w:] = np.max(dp[i+1][w:], dp[i][:-w] + v)
print(np.max(dp[N][:W+1]))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#問題D
#これだとタイムアウト
import warnings
warnings.filterwarnings('ignore')
import pandas as pd
import numpy as np

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

dp = np.array([[0] * (W+1)] * (N+1))
for i in range(1, N+1):
    tmp_arr = np.zeros(W + 1, dtype=int)
    tmp_arr = np.zeros(W + 1, dtype=int)
    tmp_arr[w[i]:] = dp[i-1][:-w[i]] + v[i]
    dp[i] = np.maximum(dp[i-1], tmp_arr)

print(dp[N, W])

Submission status: Runtime Error

Solution code:
#問題D
import warnings
warnings.filterwarnings('ignore')
import pandas as pd
import numpy as np

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

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

Submission status: Runtime Error

Solution code:
import sys
# inputを高速化する。
input = sys.stdin.readline
# 入力
vacation = int(input())
lst_happiness = [list(map(int, input().split())) for i in range(vacation)]
# DPテーブル
# 最大化問題なので0で初期化
dp = [[0 for i in range(3)] for j in range(vacation+1)]
def chmax(a, b):
    if a > b:
        return a
    else:
        return b
# dp[i][0] から dp[i + 1][1] への遷移
# dp[i][0] から dp[i + 1][2] への遷移
# dp[i][1] から dp[i + 1][0] への遷移
# dp[i][1] から dp[i + 1][2] への遷移
# dp[i][2] から dp[i + 1][0] への遷移
# dp[i][2] から dp[i + 1][1] への遷移
# 各 j (= 0, 1, 2) と各 k (= 0, 1, 2) に対して、j ≠ k ならば
# chmin(dp[i + 1][k], dp[i [j] + lst_happiness[i][k])
for i in range(vacation):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i+1][k] = chmax(dp[i+1][k], dp[i][j] + lst_happiness[i][k])
ans = 0
for i in range(3):
    ans = chmax(ans, dp[vacation][i])
print(ans)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h> 
using namespace std;
vector<vector<long long int>> a;
vector<vector<long long int>> dp;
int main(){
    int N,W;
    cin>>N>>W;
    a.resize(N,vector<long long int>(2));
    dp.resize(N+1,vector<long long int>(W+1,0));
    for(int i = 0 ; i < N ; ++i){
        for (int j = 0; j<2 ; ++j){
            cin>>a[i][j];
        }
    }

    for(int i = 1; i<N+1 ; ++i ){
        for (int j = 1 ; j<W+1 ; ++j ){
            if (a[i-1][0]<=j){  
                dp[i][j] = max({dp[i-1][j-a[i-1][0]]+a[i-1][1],dp[i-1][j],dp[i][j-1]});
            }
            else{
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    cout<<dp[N][W]<<'\n';
    return 0;
}

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h> 
using namespace std;
vector<vector<int>> a;
vector<vector<int>> dp;
int main(){
    int N,W;
    cin>>N>>W;
    a.resize(N,vector<int>(2));
    dp.resize(N+1,vector<int>(W+1,0));
    for(int i = 0 ; i < N ; ++i){
        for (int j = 0; j<2 ; ++j){
            cin>>a[i][j];
        }
    }

    for(int i = 1; i<N+1 ; ++i ){
        for (int j = 1 ; j<W+1 ; ++j ){
            if (a[i-1][0]<=j){  
                dp[i][j] = max({(dp[i-1][j-a[i-1][0]])+a[i-1][1],dp[i-1][j],dp[i][j-1]});
            }
            else{
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    cout<<dp[N][W]<<'\n';
    return 0;
}

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
import numpy as np

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

dp = np.zeros(W + 1, dtype = np.int64)
dp[w[0]] = v[0]

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

print(dp.max())

Submission status: Runtime Error

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)
dp[w[0]] = v[1]

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

Submission status: Runtime Error

Solution code:
#Recursive Solution
def maxWeight(MW,w,v,end):
  if end<0 or MW<=0:
	return 0
  if w[end]>MW:
    maxWeight(MW,w,v,end-1)
  else:
	return max(v[end]+maxWeight(MW-v[end],w,v,end-1),maxWeight(MW,w,v,end-1))
w = []
v = []
n,k = list(map(int,input().split(' ')))
for i in range(n):
  x = list(map(int,input().split(' ')))
  w.append(x[0])
  v.append(v[1])
print(maxWeight(k,w,v,n-1))

Submission status: Runtime Error

Solution code:
def inpl(): return list(map(int,input().split()))
 
N, W = inpl()
dp = [[0]*W for _ in range(N+1)]
for n in range(1,N+1):
  w, v = inpl()
  for x in range(W+1):
    if x < w:
      dp[n][x] = dp[n-1][x]
    else:
      dp[n][x] = max(dp[n-1][x], dp[n-1][x-w] + v)
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
def inpl(): return list(map(int,input().split()))
 
N, W = inpl()
dp = [[0]*W for _ in range(N)]
for n in range(1,N+1):
  w, v = inpl()
  for x in range(W):
    if x < w:
      dp[n][x] = dp[n-1][x]
    else:
      dp[n][x] = max(dp[n-1][x], dp[n-1][x-w] + v)
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
def inpl(): return map(int,input().split())

N, W = inpl()
dp = [[0]*W for _ in range(N)]
for n in range(1,N+1):
  w, v = inpl()
  for x in range(W):
    if x < w:
      dp[n][x] = dp[n-1][x]
    else:
      dp[n][x] = max(dp[n-1][x], dp[n-1][x-w] + v)
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long N, W;
  cin >> N >> W;
  
  vector<vector<long long>> dp(N, vector<long long>(W + 1, 0));
  
  long long w, v;
  cin >> w >> v;
  
  for (int i = 0; i <= W; i++) {
    if (i >= w) {
      dp.at(0).at(i) = v;
    }
  }
  
  for (int i = 1; i < N; i++) {
    cin >> w >> v;
    for (int j = 0; j <= W; j++) {
      if (j >= w) {
        dp.at(i).at(j) = max(dp.at(i - 1).at(j), dp.at(i - 1).at(j - w) + v);
      }
      else {
        dp.at(i).at(j) = dp.at(i - 1).at(j);
      }
    }
  }
  
  for (int i = 0; i < N; i++) {
    for (int j = 0; j <= W; j++) {
      cout << dp.at(i).at(j);
      if (j == W) {
        cout << endl;
      }
      else {
        cout << ' ';
      }
    }
  }
  
  long long ans = dp.at(N - 1).at(W);
    
  cout << ans << endl;
}

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
[N,W]=[int(x) for x in input().split()]
wv=[[0,0]]
for i in range(N):
  wv.append([int(x) for x in input().split()]) 
dp=np.zeros([N+1,W+i],dtype=int)
for i in range(1,N+1):
  dp[i][:w]=dp[i-1][:w]
  dp[i][w:]=max(dp[i-1][w:],dp[i-1][w-wv[i][0]:]+wv[i][1])

print(dp[N][W])

Submission status: Runtime Error

Solution code:
6 15
6 5
5 6
6 4
6 6
3 5
7 2

Submission status: Runtime Error

Solution code:
import numpy as np
import numpy.matlib

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

#　基本形
for i in range(1,N+1):
    dp[i][:wv[i-1][0]] = dp[i-1][:wv[i-1][0]]
    for j in range(wv[i-1][0],W+1):
        dp[i][j] = max(dp[i-1][j],dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
print(int(dp[-1,-1]))

Submission status: Runtime Error

Solution code:
import numpy as np

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

# 改善案
for i in range(1,N+1):
    dp[i][:wv[i-1][0]-1] = dp[i-1][:wv[i-1][0]-1]
    for j in range(wv[i-1][0],W+1):
        if dp[i-1][j] <= dp[i-1][j-wv[i-1][0]]+wv[i-1][1]:
            dp[i][j:N] = dp[i-1][j-wv[i-1][0]:N-wv[i-1][0]]+wv[i-1][1]
            break
        dp[i][j] = dp[i-1][j]
print(int(dp[-1,-1]))

Submission status: Runtime Error

Solution code:
import numpy as np

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
input =sys.stdin.readline 
number, weight = input().rstrip().split()
number = int(number)
weight = int(weight)

items = (tuple(map(int,input().rstrip().split())) for _ in range(number))
dp = [[0]*(weight+1) for _ in range(number+1)]

for i in range(number):
    for j in range(weight+1):
        if j < items[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-items[i][0]] + items[i][1])

print(dp[number][weight])

Submission status: Runtime Error

Solution code:

def main():
    N = int(input())
    p_list = []
    for _ in range(N):
        p_list.append(list(map(int, input().split())))

    # initialize dp table
    dp = [[0]*3 for _ in range(N+2)]

    for i in range(N):
        for j in range(3):
            for k in range(3):
                if j == k: continue # can't seclect same choice
                tmp_cost = dp[i][j] + p_list[i][k]
                if dp[i + 1][k] < tmp_cost:
                    dp[i + 1][k] = tmp_cost

    # every chain has maximize sum
    res = 0
    for j in range(3):
        if res < dp[N][j]:
            res = dp[N][j]
    print(res)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numba as nb 
from collections import defaultdict
n,W=list(map(int,input().split()))
li=[]
wr=[0]*n
vr=[0]*n
dd=defaultdict(lambda:0)
for i in range(n):
	w,v=map(int,input().split())
	wr[i]=w
	vr[i]=v
mw=min(wr)


@nb.njit()
def maxv(i,w):
	if dd[(i,w)]!=0:
		
		return dd[(i,w)]
	if i==n:
		return 0
	if W-w<mw:
		return 0
	if w+wr[i]<=W:
		a=vr[i]+maxv(i+1,w+wr[i])
	else:
		a=0
	b=maxv(i+1,w)
	c=max(a,b)
	dd[(i,w)]=c
	return c
print(maxv(0,0))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n,W=list(map(int,input().split()))
li=[]
wr=[0]*n
vr=[0]*n
dd=defaultdict(lambda:0)
for i in range(n):
	w,v=map(int,input().split())
	wr[i]=w
	vr[i]=v
mw=min(wr)
import numba as nb 

@nb.njit()
def maxv(i,w):
	if dd[(i,w)]!=0:
		
		return dd[(i,w)]
	if i==n:
		return 0
	if W-w<mw:
		return 0
	if w+wr[i]<=W:
		a=vr[i]+maxv(i+1,w+wr[i])
	else:
		a=0
	b=maxv(i+1,w)
	c=max(a,b)
	dd[(i,w)]=c
	return c
print(maxv(0,0))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n,W=list(map(int,input().split()))
li=[]
wr=[0]*n
vr=[0]*n
dd=defaultdict(lambda:0)
for i in range(n):
	w,v=map(int,input().split())
	wr[i]=w
	vr[i]=v
def maxv(i,w):
	if dd[(i,w)]!=0:
		return dd[(i,w)]
	if i==n:
		return 0
	if w+wr[i]>W:
		m=maxv(i+1,w)
		dp[(i,w)]=m
		return m
	a=vr[i]+maxv(i+1,w+wr[i])
	b=maxv(i+1,w)
	c=max(a,b)
	dd[(i,w)]=c
	return c
print(maxv(0,0))

Submission status: Runtime Error

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

print(dp[W][N])

Submission status: Runtime Error

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 i in range(N):
    tmp_w = w[i]
    tmp_v = v[i]
    for j in range(W):
        if dp[j] != 0:
            if j + tmp_w <= W:
                if dp[j + tmp_w] < tmp_v:
                    dp[j + tmp_w] = dp[j] + tmp_v
    if dp[tmp_w] < tmp_v:
        dp[tmp_w] = tmp_v
print(max(dp))

Submission status: Runtime Error

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

weight=[]
value=[]

for i in range(n):
    a,b=map(int,input().split())
    weight+=[a]
    value+=[b]

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

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

print(dp[n][w])

Submission status: Runtime Error

Solution code:
def knapsack(n,W):
  if n==0 or W==0 :
    return 0
  elif dp[n][W]!=-1:
    return dp[n][W]
  
  else:
    if wt[n-1]<=W:
      
      dp[n][W]=max(knapsack(n-1,W),p[n-1]+knapsack(n-1,W-wt[n-1]))
      return dp[n][W]
    else:
      dp[n][W]=knapsack(W,n-1)
      return dp[n][W]
    
wt,p=[],[]
n,w=map(int,input().split())
dp=[[-1 for i in range(w+1)]for j in range(n+1)]
for _ in range(n):
    temp_wt,temp_pr=map(int,input().split())
    wt.append(temp_wt)
    p.append(temp_pr)
print(knapsack(n,w))

Submission status: Runtime Error

Solution code:
def knapsack(n,W):
  if n==0 or W==0 :
    return 0
  elif dp[n][W]!=-1:
    return dp[n][W]
  
  else:
    if wt[n-1]<=W:
      
      dp[n][W]=max(knapsack(W,n-1),p[n-1]+knapsack(W-wt[n-1],n-1))
      return cache[(W,n)]
    else:
      dp[n][W]=knapsack(W,n-1)
      return cache[(W,n)]
    
wt,p=[],[]
n,w=map(int,input().split())

dp=[[-1 for i in range(W+1)]for j in range(n+1)]


for _ in range(n):
    temp_wt,temp_pr=map(int,input().split())
    wt.append(temp_wt)
    p.append(temp_pr)
print(knapsack(n,W))