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: Runtime Error

Solution code:
n, ww = 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] * (110) for i in range(100100)]

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

print(dp[n][ww])

Submission status: Runtime Error

Solution code:
n, ww = 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] * (110) for i in range(100100)]

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

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

Submission status: Runtime Error

Solution code:
import sys 
sys.setrecursionlimit(2147483647)

N,W = map(int,input().split())
A = [list(map(int, input().split())) for i in range(N)]
dp = [[0 for _ in range(W+1) ] for _ in range(N + 1)] 

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

Submission status: Runtime Error

Solution code:
def knapsack(N,W,weight,value):
    #初期化
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    for i in range(W+1): 
        dp[0][i]=0
    #DP
    for i in range(N):
        for w in range(W+1):
            if weight[i]<=w: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
                dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
            else: #入る可能性はない
                dp[i+1][w]=dp[i][w]
    return dp[N][W]

n,w=map(int,input().split())
weight=[0]*n
value=[0]*n
for i in range(n):
    weight[i],value[i]=map(int,input().split())

print(knapsack(n,w,a,b))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

  print(dp[N][W])

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


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

Submission status: Runtime Error

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

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

  print(dp[N][W])

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

Submission status: Runtime Error

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())
    for p in range(W):
        dp[w:] = np.maximum(dp[w:], dp[:w] + v)

print(dp[-1])

Submission status: Runtime Error

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

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

dp = [[0 for _ in range(110)] for _ in range(100100)]

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

print(dp[N][W])

Submission status: Runtime Error

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

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

dp = [[0 for _ in range(110)] for _ in range(100100)]

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

print(dp[N][W])

Submission status: Runtime Error

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

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

dp = [[0 for _ in range(110)] for _ in range(100100)]

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

print(dp[N][W])

Submission status: Runtime Error

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

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

dp = [[0 for _ in range(110)] for _ in range(100100)]

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

print(dp[N][W])

Submission status: Runtime Error

Solution code:
from math import inf

n, w = map(int, input().split())
weight, value = [0 for _ in range(n)], [0 for _ in range(n)]

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

dp = [[-1 for i in range(w+3)] for __ in range(n)]

def memoize(index, allowed_W):
	global dp

	if allowed_W < 0:
		return -(10**20)
	elif index < 0:
		return 0

	if dp[index][allowed_W] != -1:
		return dp[index][allowed_W]

	dp[index][allowed_W] = max(value[index]+memoize(index-1,allowed_W-weight[index]), memoize(index-1, allowed_W))
	return dp[index][allowed_W]

print(memoize(n-1, w))

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
weight=[]
value=[]
for i in range(n):
    q,r=map(int,input().split())
    weight.append(q)
    value.append(r)

dp=[[0 for _ in range(10100)] for _ in range(110)]

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

print(dp[n][w])

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
weight=[]
value=[]
for i in range(n):
    q,r=map(int,input().split())
    weight.append(q)
    value.append(r)

dp=[[-1] for _ in range(10100) for _ in range(110)]

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

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

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
weight=[]
value=[]
for i in range(n):
    q,r=map(int,input().split())
    weight.append(q)
    value.append(r)

dp=[[0 for i in range(111)] for j in range(100111)]

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

print(dp[n][w])

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
weight=[]
value=[]
for i in range(n):
    q,r=map(int,input().split())
    weight.append(q)
    value.append(r)

dp=[[0 for i in range(110)] for j in range(100100)]

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

print(dp[n][w])

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, W;
    cin >> N >> W;

    vector<int> dp = vector<int>(W + 1, 0);
    vector<int> idx = vector<int>(1, 0);
    int ans = 0;

    for (int i = 0; i < N; i++) {
        int w, v;
        cin >> w >> v;
        vector<int> new_idx = vector<int>(1, 0);
        for (const auto& k : idx) {
            if (k + w <= W) {
                dp[k + w] = max(dp[k + w], dp[k] + v);
                new_idx.push_back(k + w);
                ans = max(ans, dp[k + w]);
            }
        }
        idx.insert(idx.end(), new_idx.begin(), new_idx.end());
    }

    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
import numpy
def DP():
  n,m=map(int,input().split())
  dp=[0]*(m+2)
 
  for i in range(n):  #商品を一つずつ見ていく。
    w,v=(map(int,input().split()))
    for j in range(m+1,w,-1): #w~(限界-w)までのdpの箱に入れていく。(例)w,m=3,8なら3~5
      dp[j]=max(dp[j-w]+v,dp[j])
  return max(dp)
print(DP())

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import numpy as np

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

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

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

print(dp[-1])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)
n,w=map(int,input().split())
l=[]
for i in range(n):
  l.append(list(map(int,input().split())))
dp=[[-1 for i in range(w+1)] for j in range(n+1)]
def knap(x,y):
  if dp[x][y]!=-1:
    return dp[x][y]
  if x==n+1:
    res=0
  elif y<l[x][0]:
    res=knap(x+1,y)
  else:
    res=max(knap(x+1,y),knap(x+1,y-l[x][0])+l[x][1])
  dp[x][y]=res
  return res
knap(0,w)
print(dp[0][w])

Submission status: Runtime Error

Solution code:
# 再帰関数使用時は再帰上限を十分にとること
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
 
# グローバル変数定義
INF = 10 ** 13
N, W = map(int, input().split())
 
# knopsock[n][0] = w    :   n = 品物の位置 , w = 重さ
# knopsock[n][1] = v    :   n = 品物の位置 , v = 価値
knapsack = [list(map(int, input().split())) for _ in range(N)]
 
# db[n][w] = v          :   w = 現在の重さ, n = 見てきた品物の数, v = 現在の価値
db = [[INF] * W for _ in range(N)]
 
 
def dfs(n, w):
    """
    品物に対する深さ優先探索による全探索（メモ化再帰）。
 
    Args:
        n (int) : 見てきた品物の数
        w (int) : ここまでの重さの総和
 
    Returns:
        v (int) : 価値の総和の最大値
    """
 
    # 終了条件：現在の個数が全ての品物の個数を越える
    if n >= N:
        return 0
 
    if w + knapsack[n][0] > W:
        # １つ前までの重さ + 今回の品物の重さが重さの最大値を越えていたら今回の品物は選べない
        return dfs(n + 1, w)
    else:
        # 今回の品物を選ぶか選ばないかで全探索
        return max([dfs(n + 1, w), dfs(n + 1, w + knapsack[n][0]) + knapsack[n][1]])
 
 
def main():
    out = dfs(0, 0)
    print(out)
 
 
if __name__ == "__main__":
    main()
# 再帰関数使用時は再帰上限を十分にとること
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

# グローバル変数定義
INF = 10 ** 13
N, W = map(int, input().split())

# knopsock[n][0] = w    :   n = 品物の位置 , w = 重さ
# knopsock[n][1] = v    :   n = 品物の位置 , v = 価値
knapsack = [list(map(int, input().split())) for _ in range(N)]

# db[n][w] = v          :   w = 現在の重さ, n = 見てきた品物の数, v = 現在の価値
db = [[INF] * W for _ in range(N)]


def dfs(n, w):
    """
    品物に対する深さ優先探索による全探索（メモ化再帰）。

    Args:
        n (int) : 見てきた品物の数
        w (int) : ここまでの重さの総和

    Returns:
        v (int) : 価値の総和の最大値
    """

    # 終了条件：現在の個数が全ての品物の個数を越える
    if n >= N:
        return 0

    if w + knapsack[n][0] > W:
        # １つ前までの重さ + 今回の品物の重さが重さの最大値を越えていたら今回の品物は選べない
        return dfs(n + 1, w)
    else:
        # 今回の品物を選ぶか選ばないかで全探索
        return max([dfs(n + 1, w), dfs(n + 1, w + knapsack[n][0]) + knapsack[n][1]])


def main():
    out = dfs(0, 0)
    print(out)


if __name__ == "__main__":
    main()
提出情報
提出日時	2019-11-17 17:37:04
問題

Submission status: Runtime Error

Solution code:
import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 
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:], dp[:-w] + v, out = dp[w:])
print(dp.max())

Submission status: Runtime Error

Solution code:
import numpy as np

def napsack(n,weight,weights,values):
  dp=[[0]*(n+1) for i in range(weight+1)]
  for i in range(1,n+1):
    for j in range(weight+1):
      if j-weights[i-1]>=0:
        dp[j][i]=np.maximum(dp[j][i],dp[j-weights[i-1]][i-1]+values[i-1])
      else:
        dp[j][i]=np.maximum(dp[j][i-1],dp[j][i])

  return  dp[weight][n]
     
n,w=map(int,input().split())
items=[list(map(int,input().split())) for i in range(n)]
W=[items[i][0] for i in range(n)]
V=[items[i][1] for i in range(n)]
print(napsack(n,w,W,V))

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.buffer.readline


def main():
    N, K = map(int, readline().split())
    H = list(map(int, readline().split()))
    for i in range(K):
        H.append(10**10)

    dp = [10**10] * (N+K)
    dp[0] = 0

    for i in range(N):
        for k in range(1, K+1):
            dp[i+k] = min(dp[i+k], dp[i] + abs(H[i+k]-H[i]))

    print(dp[N-1])


main()

Submission status: Runtime Error

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

dp = [0]*(W+1)

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

print dp[-1]

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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)

#メイン
#dp[j] : 重さの総和がjを超えないように選んだ時の価値の総和の最大値
for i in range(n):
    j=W
    while j>=w[i]:
        dp[j]=max(dp[j],dp[j-w[i]]+v[i])
        j-=1

print(dp[W])

Submission status: Runtime Error

Solution code:

#入力,準備
n=int(input())
w=[0]*n
v=[0]*n
for i in range(n):
    w[i],v[i]=map(int,input().split())
W=int(input())
dp=[0]*(W+1)

#メイン
#dp[j] : 重さの総和がjを超えないように選んだ時の価値の総和の最大値
for i in range(n):
    j=W
    while j>=w[i]:
        dp[j]=max(dp[j],dp[j-w[i]]+v[i])
        j-=1

print(dp[W])

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
array = [[0] * (W+1) for i in range((N+1))]
for i in range(N):
  wei,V = map(int,input().split())
  for j in range(W,wei-1,-1):
    if(wei<=j+1):
      if(array[i][j] < array[i][j-wei+1]+V):
        array[i+1][j+1]=array[i][j-wei+1]+V
      else:
        array[i+1][j+1]=array[i][j+1]
    else:
      array[i+1][j+1]=array[i][j+1]
print(array[N][W])

Submission status: Runtime Error

Solution code:
    n, maxweight = map(int, input().rstrip().split())
    dp = [0 for i in range(maxweight+1)]

    for wn in range(n):
        weight, value = map(int, input().rstrip().split())
        for w in range(maxweight-weight+1):
            dp[w] = max(dp[w], dp[w+weight] + value)
    print(max(dp))

Submission status: Runtime Error

Solution code:
def main(n,w,itemWeights,itemValues):
    m = 0
    for i in range(n):
        if itemValues[i] > itemValues[m]:
            m = i
    if w - itemWeights[m] < 0:
        return 0
    else if w - itemWeights[m] == 0:
        return itemValues[i]
    else:
        v = itemValues[m]
        itemWeights.pop(m)
        itemValues.pop(m)
        return v+main(n,w,itemWeights,itemValues)
    

inp1 = input().split()
n = inp1[0]
w = inp[1]
itemWeights = []
itemValues = []

for i in range(n)
    inp = input()
    itemWeights.append(int(inp[0]))
    itemValues.append(int(inp[1]))

print(main(n,w,itemWeights,itemValues))

Submission status: Runtime Error

Solution code:
n, W = map(int, input().split())
w, v = [], []
dp = [[None for i in range(W+1)] for j in range(n+1)]

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

def solve(i, total):
    if dp[i][total] is not None:
        return dp[i][total]

    if i > n-1:
        return 0
    if total > W:
        return 0

    weight, val = w[i], v[i]
    if total + weight <= W:
        chose = val + solve(i+1, total + weight)
	unchose = solve(i+1, total)
        dp[i][total] = max(chose, unchose)
	return dp[i][total]
    else:
        dp[i][total] = solve(i+1, total)
	return dp[i][total]

print(solve(0, 0))

Submission status: Runtime Error

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

V = sum(v)
# dp[i][j]:i番目までの品物から価値がj以上になるよう選んだときの重さの総和の最小値
dp = [[float("inf")] * (V + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
	for j in range(V + 1):
		# i+1番目を選ぶ場合
		if j - v[i] >= 0:
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v[i]] + w[i])
		# i+1番目を選ばない場合
		dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

# dp[N][j]がW以下であるようなjの最大値が答えになる
ans = 0
for j in range(V + 1):
	if dp[N][j] <= W:
		ans = j

print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin

n,w = [int(x) for x in stdin.readline().rstrip().split()]
nw = [0]*n
nv = [0]*n
for i in range(n):
    nw[i],nv[i] = [int(x) for x in stdin.readline().rstrip().split()]
def knapsack(n,w,nw,nv):
    dp = [[0*(w+1)]for j in range(n+1)]
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(w+1):
            if total_w - nw[i] >= 0:
                dp[i+1][total_w] = max(dp[i][total_w],dp[i][total_w-nw[i]]+nv[i])
            else:
                dp[i+1][total_w] = dp[i][total_w]
    return dp[-1][-1]
print(knapsack(n,w,nw,nv))

Submission status: Runtime Error

Solution code:
from sys import stdin
import numpy as np

n,w = [int(x) for x in stdin.readline().rstrip().split()]
nw = [0]*n
nv = [0]*n
for i in range(n):
    nw[i],nv[i] = [int(x) for x in stdin.readline().rstrip().split()]
def knapsack(n,w,nw,nv):
    dp = [[0*(w+1)]for j in range(n+1)]
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(w+1):
            if total_w - nw[i] >= 0:
                dp[i+1][total_w] = max(dp[i][total_w],dp[i][total_w-nw[i]]+nv[i])
            else:
                dp[i+1][total_w] = dp[i][total_w]
    return dp[-1][-1]
print(knapsack(n,w,nw,nv))

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000000000)

n, W = map(int, input().split())
w, v = [], []

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

#print(w, v)
#dp[i] = max(dp[i-1], dp[i]) + dp[i-2]

@lru_cache(maxsize=None)
def solve(total, i):
    if i > n-1:
        return 0
    weight, val = w[i], v[i]
    if total + weight <= W:
        chose = val + solve(total + weight, i+1)
        unchose = solve(total, i+1)
        return max(chose, unchose)
    else:
        return 0

print(solve(0, 0))

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**10)

n, W = map(int, input().split())
w, v = [], []

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

#print(w, v)
#dp[i] = max(dp[i-1], dp[i]) + dp[i-2]

@lru_cache(maxsize=None)
def solve(total, i):
    if i > n-1:
        return 0
    weight, val = w[i], v[i]
    if total + weight <= W:
        chose = val + solve(total + weight, i+1)
        unchose = solve(total, i+1)
        return max(chose, unchose)
    else:
        return 0

print(solve(0, 0))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(500000)
n, W = map(int, input().split())
w, v = [], []

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

#print(w, v)
#dp[i] = max(dp[i-1], dp[i]) + dp[i-2]

def solve(total, i):
    if i > n-1:
	return 0
    weight, val = w[i], v[i]
    if total + weight <= W:
        chose = val + solve(total + weight, i+1)
        unchose = solve(total, i+1)
        return max(chose, unchose)
    else:
        return 0

print(solve(0, 0))

Submission status: Runtime Error

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

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

#print(w, v)
#dp[i] = max(dp[i-1], dp[i]) + dp[i-2]

def solve(total, i):
    if i > n-1:
	return 0
    weight, val = w[i], v[i]
    if total + weight <= W:
        chose = val + solve(total + weight, i+1)
        unchose = solve(total, i+1)
        return max(chose, unchose)
    else:
        return 0

print(solve(0, 0))

Submission status: Runtime Error

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

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

c#print(w, v)
#dp[i] = max(dp[i-1], dp[i]) + dp[i-2]

def solve(total, i):
    if i > n-1:
	return 0
    weight, val = w[i], v[i]
    if total + weight <= W:
        chose = val + solve(total + weight, i+1)
        unchose = solve(total, i+1)
        return max(chose, unchose)
    else:
        return 0

print(solve(0, 0))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)

class Solver(object):
    def __init__(self,N:int,W:int,values:list,weights:list):
        self.N = N   ## MAX number of item
        self.values = values  ## list of item value
        self.weights = weights ## list of item weight
        self.dp = [[None for _ in range(W+1)] for _ in range(N+1)] ## memorize the result

    ## i番目以降から重さがj以下になるように選ぶ時に価値が最大になるようにする。
    def solve(self,i:int,j:int) -> int:
        if self.dp[i][j] != None:
            return self.dp[i][j]
        if i == self.N:
            res = 0
        if j < self.weights[i]:
            res = self.solve(i+1,j)
        else:
            res = max(self.solve(i+1,j),self.solve(i+1,j-self.weights[i])+self.values[i])
        self.dp[i][j] = res
        return res

def main():
    N,W = [int(i) for i in input().split()]
    items = [[int(i) for i in input().split()] for _ in range(N)]
    weights = [item[0] for item in items]
    values = [item[1] for item in items]
    solver = Solver(N,W,values,weights)
    ans = solver.solve(0,W)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

dp=[[0 for i in range(N+100)] for j in range(W+100)]

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

Submission status: Runtime Error

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

dp=[[0 for i in range(N+10)] for j in range(W+10)]

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

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
wv_list = [list(map(int, input().split())) for _ in range(n)]
 
def dp1(N, W, wv_list):
    weights = list(map(lambda x: x[0], wv_list))
    values = list(map(lambda x: x[1], wv_list))
    
    dp_dic = {i: {} for i in range(0, N+1)}
    
    for w in range(0, W):
        dp_dic[0][w] = 0
    for i in range(0, N):
        for w in range(0, W):
            if weights[i] <= w:
                dp_dic[i+1][w] = max(dp_dic[i][w], dp_dic[i][w-weights[i]] + values[i])
            else:
                dp_dic[i+1][w] = dp_dic[i][w]
    return dp_dic
  
print(dp1(N, W, wv_list)[N][W-1])

Submission status: Runtime Error

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

def dp1(N, W, wv_list):
    weights = list(map(lambda x: x[0], wv_list))
    values = list(map(lambda x: x[1], wv_list))
    print(weights, values)
    dp_dic = {i: {} for i in range(0, N+1)}
    
    for w in range(0, W):
        dp_dic[0][w] = 0
    for i in range(0, N):
        for w in range(0, W):
            if weights[i] <= w:
                dp_dic[i+1][w] = max(dp_dic[i][w], dp_dic[i][w-weights[i]] + values[i])
            else:
                dp_dic[i+1][w] = dp_dic[i][w]
    return dp_dic
  
print(dp1(N, W, wv_list)[N][W-1])

Submission status: Runtime Error

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

def knapsack_dp(weight_capacity, weights, values):
    """Solve knapsack problem by dynamic programming"""
    N = len(weights)
    dp = [[0] * (weight_capacity + 1) for _ in range(len(weights) + 1)]

    for i in range(N + 1):
        for w in range(weight_capacity + 1):
            if w >= weights[i]:
                dp[i + 1][w] = max(dp[i][w], dp[i][w - weights[i]] + values[i])
            else:
                dp[i + 1][w] = dp[i][w]

    return dp[N][weight_capacity]

print(knapsack_dp(weight_capacity, weights, values))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, int> pii;
typedef pair<double, pair<int, int>> tii;
int n, w;
ll dp[105][100005];
vector<ll> vals;
vector<ll> weights;
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> w;
    for (int i = 0; i<n;i++) {
        ll z, x;
        cin >> z >> x;
        vals.pb(x);
        weights.pb(z);
    }
    for (int i = 0; i<=n;i++) {
        for (int j = 0; j<=w ;j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            }
            else if (weights[i-1] <= j) {
                dp[i][j] = max(vals[i-1] + dp[i-1][j-weights[i-1]], dp[i-1][j]);
            }
            else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout << dp[n][w] << "\n";

}

Submission status: Runtime Error

Solution code:
def f(n, m, WV):
  def shift(w, v, Arr):
    return [max(Arr[i], Arr[i - w] + v) if i >= w else Arr[i] for i in range(M + 1)]
  def red(WV):
    return [0] * (M+1) if not WV else shift(*WV[0], red(WV[1:]))
  return red(WV)
N, M = map(int, input().split())
WV = [map(int, input().split()) for _ in range(N)]
print(f(N, M, WV)[M])

Submission status: Runtime Error

Solution code:
def f(n, m, VW):
  def shift(w, v, Arr):
    return [max(Arr[i], Arr[i - w] + v) if i >= w else Arr[i] for i in range(M + 1)]
  def red(VW):
    return [0] * (M+1) if VW == [] else shift(*VW[0], red(VW[1:]))
  return red(VW)
N, M = map(int, input().split())
VW = [map(int, input().split()) for _ in range(N)]
print(f(N, M, VW)[M])