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:
import numpy as np
import math

def solve():
    n,w = map(int,input().split())
    w_list,v_list = [0]*n,[0]*n
    for i in range(n):
        w_list[i],v_list[i] = map(int,input().split())
    dp = [[0]*(w+5) for i in range(n+5)]
    for i in range(n):
        for j in range(w+1):
            if j >= w_list[i]:
                dp[i][j] = max(
                    dp[i-1][j],
                    dp[i-1][j-w_list[i]]+v_list[i])
            else:
                dp[i][j] = dp[i-1][j]
    print(dp)
    print(dp[n-1][w])
    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import numpy as np
import math
 
def solve():
    n,w = map(int,input().split())
    w_list,v_list = [0]*n,[0]*n
    for i in range(n):
        w_list[i],v_list[i] = map(int,input().split())
    dp = [[0]*(w+5) for i in range(n+5)]
    for i in range(n):
        for j in range(w+1):
            if j >= w_list[i]:
                dp[i][j] = max(
                    dp[i-1][j],
                    dp[i-1][j-w_list[i]]+v_list[i])
            else:
                dp[i][j] = dp[i-1][j]
    print(dp)
    print(dp[n-1][w])
    return 0
 
if __name__ == "__main__":
    solve()
import numpy as np
import math

def solve():
    n,w = map(int,input().split())
    w_list,v_list = [0]*n,[0]*n
    for i in range(n):
        w_list[i],v_list[i] = map(int,input().split())
    dp = [[0]*(w+5) for i in range(n+5)]
    for i in range(n):
        for j in range(w+1):
            if j >= w_list[i]:
                dp[i][j] = max(
                    dp[i-1][j],
                    dp[i-1][j-w_list[i]]+v_list[i])
            else:
                dp[i][j] = dp[i-1][j]
    print(dp)
    print(dp[n-1][w])
    return 0

if __name__ == "__main__":
    solve()
提出情報

Submission status: Runtime Error

Solution code:
import numpy as np
import math

def solve():
    n,w = map(int,input().split())
    w_list,v_list = [0]*n,[0]*n
    for i in range(n):
        w_list[i],v_list[i] = map(int,input().split())
    dp = [[0]*(w+5) for i in range(n+5)]
    for i in range(n):
        for j in range(w+1):
            if j >= w_list[i]:
                dp[i][j] = max(
                    dp[i-1][j],
                    dp[i-1][j-w_list[i]]+v_list[i]
                    )
            else:
                dp[i][j] = dp[i-1][j]
    print(dp)
    print(dp[n-1][w])
    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import numpy as np
import math

def solve():
    n,w = map(int,input().split())
    w_list,v_list = [0]*n,[0]*n
    for i in range(n):
        w_list[i],v_list[i] = map(int,input().split())
    dp = [[0]*(w+5) for i in range(n+5)]
    for i in range(n):
        for j in range(w+1):
            if j-w_list[i]>=0:
                dp[i][j] = max(
                    dp[i-1][j],
                    dp[i-1][j-w_list[i]]+v_list[i]
                    )
            else:
                dp[i][j] = dp[i-1][j]
    print(dp[n-1][w])
    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
#ABC164C
def main():
    import sys
    N, limit = map(int, sys.stdin.readline().split())
    L = tuple([tuple(map(int, sys.stdin.readline().split())) for _ in range(N)])
    dp = [[0 for _ in range(limit+1)] for _ in range(N)]
    dp[0][L[0][0]] = L[0][1] #初期値
    for i in range(1, N):
        dp[i] = dp[i-1].copy() #前回をコピー(初)
        w, v = L[i][0], L[i][1]
        dp[i][w] = max(v, dp[i][w])
        for j in range(limit+1-w):
            if dp[i-1][j] >0:
                dp[i][w+j] = max(v+ dp[i-1][j], dp[i][w+j])
            
    
    
    print(max(dp[-1]))



if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

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

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

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(500000)

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

weight = []
v = []
dp = []

for _ in range(N):
    weight1,v1 = map(int, input().split())
    weight.append(weight1)
    v.append(v1)
    dp.append([-1]*W)

def dfs(n, w):#wの容量でn番目までの商品で最大価値
    global N
    global W
    if n==0:
        if(w-weight[n]>=0):
            return v[n]
        else:
            return 0
    if dp[n][w]!=-1:
        return dp[n][w]

    if (w-weight[n])>=0:
        ret = max(dfs(n-1, w), dfs(n-1, w-weight[n])+v[n])
    else:
        ret = dfs(n-1, w)#選択肢ないので、これを選ばない
    dp[n][w] = ret
    return ret

print(dfs(N-1,W))

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int, input().split())))
# print(wv)
dp = [[0] * 110 for _ in range(100100)]


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

        if wv[i][0] <= sum_w:
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - wv[i][0]] + wv[i][1])

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

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int, input().split())))
# print(wv)
dp = [[0] * 110 for _ in range(100100)]


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

        if sum_w - wv[i][0] >= 0:
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - wv[i][0]] + wv[i][1])

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

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
a=[0]*(w+1)
for i in range(n):
    b=a.copy()
    x,y=map(int,input().split())
    for j in range(min(x,w),w+1):
        b[j]=max(a[j-x]+y,a[j])
    a=b.copy()
print(max(b))

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
a=[0]*(w+1)
for i in range(n):
    b=a.copy()
    x,y=map(int,input().split())
    for j in range(min(x,w),w+1):
        b[j]=max(a[j-x]+y,a[j])
    a=b.copy()
print(max(a))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
noWeight = [[0 for j in range(W+1)] for i in range(N)]
wv = [[] for i in range(N)]
for i in range(N) :
	wv = [int(i) for i in input().split()]
	for j in range(1,W+1) :
		if i != 0 :
			if j < wv[0]  :
				noWeight[i][j] = noWeight[i-1][j]
			else :
				noWeight[i][j] = max(noWeight[i-1][j - wv[0]] + wv[1], noWeight[i-1][j])
		else :
			if j >= wv[0] :
				noWeight[i][j] = wv[1]
			else :
				noWeight[i][j] = 0
	
print(noWeight[N-1][W])

Submission status: Runtime Error

Solution code:
import numpy as np
N,W = map(int,input().split())
WV = [(list(map(int,input().split()))) for _ in range(N)]
DP = np.array([[0]*(W+1) for _ in range(N+1)], dtype=np.int64)

def rec(i,w,v):
    if DP[i][w] != 0:
        return DP[i][w]
    if i == N:
        return v
    if w == 0:
        return v
    else:
        res = rec(i+1,w,v)
        if w-WV[i][0] >= 0:
            res = max(res,rec(i+1,w-WV[i][0],v+WV[i][1]))
        DP[i][w] = res
        return DP[i][w]

rec(0,W,0)
print(np.max(DP))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n,w = map(int,input().split())
dp = [[0]*(w+1)] *(n+1)
for i in range(1,n+1):
    wi,vi = map(int,input().split())
    #DPテーブルの更新
    for j in range(w+1):
        if j >= wi : #選べるかどうか
            dp[i][j] = max(dp[i-1][j] , dp[i-1][j-wi]+vi) #選ぶ場合
        else:
            dp[i][j] = max(dp[i-1][j] , dp[i][j]) #選ばない場合
print(dp[n+1][w+1])

Submission status: Runtime Error

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

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


"""Module docstring
"""
import numpy as np
import sys

EMPTY = (0, 0, frozenset())


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


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


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


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


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


if __name__ == "__main__":
    import doctest

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

Submission status: 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 = [[-1]*(W+1) for i in range(N+1)]
def rec(i, j):
    if dp[i][j] != -1:
        return dp[i][j]
    else:
        if i == N+1:
            work = 0
        elif j < w[i]:
            work = rec(i+1, j)
        else:
            work = max(rec(i+1, j), rec(i+1, j-w[i])+v[i])
        dp[i][j] = work
        return work
result = rec(0, W)
print(result)

Submission status: Runtime Error

Solution code:
n,W=map(int,input().split())
wv=[[int(j) for j in input().split()] for i in range(n)]
dp=[[0]*110 for i in range(110000)]

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

Submission status: Runtime Error

Solution code:
N,W = map(int,input().rstrip().split(" "))
wv = [[0,0] for _ in range(N)]
DP = [[0 for _ in range(W + 1)]for i in range(N)]
for i in range(N):
  wv[i] = list(map(int,input().rstrip().split(" ")))
for i in range(N):
  for w in range(W + 1):
    if(w >= wv[i][0]):
      DP[i + 1][w] = max(DP[i][w - wv[i][0]] + wv[i][1], DP[i][w])
    else:
      DP[i + 1][w] = DP[i][w]
print(DP[N][W])

Submission status: Runtime Error

Solution code:
N,W = map(int,input().rstrip().split(" "))
wv = [[0,0] for _ in range(N + 10)]
DP = [[0 for _ in range(N + 10)]for i in range(W + 10)]
for i in range(N):
  wv[i] = list(map(int,input().rstrip().split(" ")))
for i in range(N):
  for w in range(W + 1):
    if(w >= wv[i][0]):
      DP[i + 1][w] = max(DP[i][w - wv[i][0]] + wv[i][1], DP[i][w])
    else:
      DP[i + 1][w] = DP[i][w]
print(DP[N][W])

Submission status: Runtime Error

Solution code:
def knapSack(C, wt, val, n): 
    K = [[0 for x in range(W+1)] for x in range(n+1)] 
  
    # Build table K[][] in bottom up manner 
    for i in range(n+1): 
        for w in range(C+1): 
            if i==0 or w==0: 
                K[i][w] = 0
            elif wt[i-1] <= w: 
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]) 
            else: 
                K[i][w] = K[i-1][w] 
  
    return K[n][W] 

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

wt   = [0] * (n+1)
val  = [0] * (n+1)

for i in range(1,n+1):
    wt[i], val[i] = list(map(int,input().split()))
    
knapSack(C, wt, val, n)

Submission status: Runtime Error

Solution code:
import numpy as np

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

Submission status: Runtime Error

Solution code:
import numpy as np

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

Submission status: Runtime Error

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

def main():
    N, W = map(int, input().split())
    wv = list(map(int, input().split()) for _ in range(N))
    
    dp = [0] * (W + 1)
    
    for w, v in wv:
        for i in range(W, w - 1a, -1):
            dp[i] = max(dp[i], dp[i - w] + v)
    
    print(dp[-1])
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#include <iostream>
#define ll long long
using namespace std;

int main(){
  ll N,W; cin>>N>>W;
  ll dp[W][2];
  for(ll i=0;i<W;i++){dp[i][0]=dp[i][1]=0;}
  
  ll w,v;
  for(ll i=0;i<N;i++){
    cin>>w>>v;
    for(ll j=0;j<W;j++){dp[j][1]=0;}
    
    if(dp[w-1][0]==0){dp[w-1][0]=v;}
    else{
      if(2*w-1<W){
      	if(dp[2*w-1][0]<dp[w-1][0]+v){
          dp[2*w-1][0]=dp[w-1][0]+v;
          dp[2*w-1][1]=1;
        }
      }
      if(dp[2*w-1][0]<v){dp[2*w-1][0]=v;}
    }
    
    for(ll j=0;j<W-w;j++){
      if(j!=w-1&&dp[j][1]==0&&dp[j][0]>0&&dp[j+w][0]<dp[j][0]+v){
        dp[j+w][0]=dp[j][0]+v;
        dp[j+w][1]=1;
      }
    }
    /*
    for(ll j=0;j<W;j++){cout<<dp[j][0]<<' ';}
    cout<<endl;
    */
  }
  
  ll max=0;
  for(ll i=0;i<W;i++){
    if(max<dp[i][0]){max=dp[i][0];}
  }
  
  cout<<max;
  
  return 0;
}

Submission status: Runtime Error

Solution code:
def main():
  num,capacity,*wv =map(int,open(0).read().split())
  weights,values = wv[::2], wv[1::2]
  DP=[-1]*(capacity+1)
  DP[0]=0
  for w,v in zip(weights, values):
    left=capacity-weight
    DP[weight:]=[max(DP[i]+value,DP[i+weight]) for i in range(left,-1,-1)][::-1]
  print(max(DP))
      
if __name__=="__main__":
  main()

Submission status: Runtime Error

Solution code:
import numpy as np
import sys


def DP(i, X, w, v):
    global memo
    if (X < 0):
        return -10 ** 9
    if (memo[i, X] != -10 ** 9):
        return memo[i, X]
    result = max(DP(i + 1, X, w, v),
                 DP(i + 1, X - w[i], w, v) + v[i])
    memo[i, X] = result
    return result


def main():
    input = sys.stdin.readline
    N, W = map(int, input().split())
    w = [0] * N
    v = [0] * N
    for i in range(N):
        w[i], v[i] = map(int, input().split())
    MINUS_INF = -10 ** 9
    memo = np.full((N + 1, W + 1), MINUS_INF, dtype=np.int64)
    memo[N, :] = 0
    answer = DP(0, W, w, v)
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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


int main(){
	#ifndef ONLINE_JUDGE
	freopen("D:\\input.txt", "r", stdin);
	freopen("D:\\out.txt", "w", stdout);
	#endif
	int n,w;
	cin>>n>>w;
	int weights[n];
	int values[n];
	for(int i=0;i<n;i++){
		cin>>weights[i]>>values[i];
	}
	long long  dp[n+1][w+1];
	for(int i=0;i<n+1;i++){
		dp[i][0] = 0;
	}
	for(int i=0;i<w+1;i++){
		dp[0][i] = 0;
	}
	for(int i = 1;i < n+1;i++){
		for(int j = 1;j<w+1;j++){
			if(j < weights[i-1]){
				dp[i][j] = dp[i-1][j];
			}
			else{
			dp[i][j] = max(dp[i-1][j],dp[i-1][max(0,j-weights[i-1])]+values[i-1]);
			
		}
		}
	}
	
	cout << dp[n][w] << endl;
	return 0;
}

Submission status: Runtime Error

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


int main(){
	int n,w;
	cin>>n>>w;
	int weights[n];
	int values[n];
	for(int i=0;i<n;i++){
		cin>>weights[i]>>values[i];
	}
	long long  dp[n+1][w+1];
	for(int i=0;i<n+1;i++){
		dp[i][0] = 0;
	}
	for(int i=0;i<w+1;i++){
		dp[0][i] = 0;
	}
	for(int i = 1;i < n+1;i++){
		for(int j = 1;j<w+1;j++){
			if(j < weights[i-1]){
				dp[i][j] = dp[i-1][j];
			}
			else{
			dp[i][j] = max(dp[i-1][j],dp[i-1][max(0,j-weights[i-1])]+values[i-1]);
			
		}
		}
	}
	
	cout << dp[n][w] << endl;
	return 0;
}

Submission status: Runtime Error

Solution code:
import numpy as np


def DP(i, X, w, v):
    global memo
    if (X < 0):
        return -10 ** 9
#    if (memo[i, X] != -10 ** 9):
#        return memo[i, X]
#       print('you used memo!')
    result = max(DP(i + 1, X, w, v),
                 DP(i + 1, X - w[i], w, v) + v[i])
    memo[i, X] = result
    return result


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())
MINUS_INF = -10 ** 9
memo = np.full((N + 1, W + 1), MINUS_INF, dtype=np.int64)
memo[N, :] = 0
answer = DP(0, W, w, v)
print(answer)

Submission status: Runtime Error

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
import numpy as np
n,W = mi()
a = [tuple(int(i) for i in input().split()) for _ in range(n)]
dp = np.array([0]*(W+1))
for w,v in a:
    ed = W+1-w
    dp[w:W+1] = np.maximum(dp[w:ed], dp[0:ed] + v)
print(dp[W])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
N, L = map(int, input().split())
W = []
V = []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)


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


def knap(i, j):
    if dp[i][j] >= 0:
        return dp[i][j]

    if i == N:
        dp[i][j] = 0
    elif j < W[i]:
        dp[i][j] = knap(i+1, j)
    else:
        dp[i][j] = max(knap(i+1, j), knap(i+1, j - W[i]) + V[i])

    return dp[i][j]


print(knap(0, L))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**10)
N, L = map(int, input().split())
W = []
V = []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)


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


def knap(i, j):
    if dp[i][j] >= 0:
        return dp[i][j]

    if i == N:
        dp[i][j] = 0
    elif j < W[i]:
        dp[i][j] = knap(i+1, j)
    else:
        dp[i][j] = max(knap(i+1, j), knap(i+1, j - W[i]) + V[i])

    return dp[i][j]


print(knap(0, L))

Submission status: Runtime Error

Solution code:
import sys
N, L = map(int, input().split())
W = []
V = []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)

sys.setrecursionlimit(10**8)

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


def knap(i, j):
    if dp[i][j] >= 0:
        return dp[i][j]

    if i == N:
        dp[i][j] = 0
    elif j < W[i]:
        dp[i][j] = knap(i+1, j)
    else:
        dp[i][j] = max(knap(i+1, j), knap(i+1, j - W[i]) + V[i])

    return dp[i][j]


print(knap(0, L))

Submission status: Runtime Error

Solution code:
n,w = map(int,input().split())
dp = [[0]*110 for _ in range(10**5 + 10)]
for i in range(n):
  w_v = list(map(int,input().split()))
  for sum_w in range(w+1):
    if sum_w - w_v[0] >= 0:
      dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w_v[0]] + w_v[1])
    dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
print(dp[n][w])

Submission status: Runtime Error

Solution code:
n,w = map(int,input().split())
d = {}
p = []
for i in range(n):
    k,v = map(int,input().split())
    d[k] = v
    p.append(k)

dp = []
for i in range(n+1):
    o = []
    for j in range(w+1):
        o.append(0)

    dp.append(o)


for i in range(n):
    for j in range(w+1):
        if p[i] > j:
            dp[i+1][j] = dp[i][j]

        else:
            dp[i+1][j] = max(d[p[i]] + dp[i][j - p[i]], dp[i][j])

print(dp[n][w])n,w = map(int,input().split())
d = {}
p = []
for i in range(n):
    k,v = map(int,input().split())
    d[k] = v
    p.append(k)

dp = []
for i in range(n+1):
    o = []
    for j in range(w+1):
        o.append(0)

    dp.append(o)


for i in range(n):
    for j in range(w+1):
        if p[i] > j:
            dp[i+1][j] = dp[i][j]

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
# D - Knapsack 1
N, W = list(map(int, input().split()))

def knapsack(n, w):
    # dp[i][j] : i番目の品物で重さj以下の価値の最大値
    dp = np.zeros((N+1, W+1), dtype='int64')
    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)
    return dp[-1][-1]

print(knapsack(N, W))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
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)
    return dp[-1][-1]

print(knapsack(N, W))

Submission status: Runtime Error

Solution code:
n,w = map(int, input().split())
lst_weight = [0 for _ in range(n)]
lst_value = [0 for _ in range(n)]
for i in range(n):
    lst_weight[i], lst_value[i] = map(int, input().split())
dp = [[0 for i in range(w)] for j in range(n+1)]

#後者が前者よりも大きい時に更新→DPテーブルを-infに初期化
def chmax(a,b):
    if(a< b):
        return b
    else:
        return a

#各品物の選択
for i in range(n):
    for sum_w in range(w+1):
        #選択した品物を加える
        if sum_w >= lst_weight[i]:
            #今回の手の暫定最大値と1つ前までの手の確定最大値を比較する
            dp[i+1][sum_w] = chmax(dp[i+1][sum_w], dp[i][sum_w-lst_weight[i]] + lst_value[i])
        else:
            # i番目の品物を選ばない→前までの手で最適化されている最大値が次の手の最大値になるはず
            dp[i+1][sum_w] = chmax(dp[i+1][sum_w], dp[i][sum_w])
            
print(dp[n][w])

Submission status: Runtime Error

Solution code:
n,w = map(int, input().split())
lst_weight = [0 for _ in range(N)]
lst_value = [0 for _ in range(N)]
for i in range(N):
    lst_weight[i], lst_value[i] = map(int, input().split())
dp = [[0 for i in range(w)] for j in range(n+1)]

#後者が前者よりも大きい時に更新→DPテーブルを-infに初期化
def chmax(a,b):
    if(a< b):
        return b
    else:
        return a

#各品物の選択
for i in range(n):
    for sum_w in range(w+1):
        #選択した品物を加える
        if sum_w >= lst_weight[i]:
            #今回の手の暫定最大値と1つ前までの手の確定最大値を比較する
            dp[i+1][sum_w] = chmax(dp[i+1][sum_w], dp[i][sum_w-lst_weight[i]] + lst_value[i])
        else:
            # i番目の品物を選ばない→前までの手で最適化されている最大値が次の手の最大値になるはず
            dp[i+1][sum_w] = chmax(dp[i+1][sum_w], dp[i][sum_w])
            
print(dp[n][w])

Submission status: Runtime Error

Solution code:
#ナップザック問題
import numpy as np

N,W=map(int,input())
wv = np.array([list(map(int, input().split())) for i in range(0, N)])  


dp=np.zeros((N+1,W+1),dtype=int)
for n in range(0, N):  
    for w in range(0, W + 1):  
        if w < wv[n, 0]:  
            dp[n+1, w] = dp[n, w]  
        else:  
            dp[n+1, w] = max(dp[n, w], dp[n, w - wv[n, 0]] + wv[n, 1])  
print(dp[N,W])

Submission status: Runtime Error

Solution code:
#ナップザック問題
import numpy as np

N = int(input())  
wv = np.array([list(map(int, input().split())) for i in range(0, N)])  
W = int(input()) 

dp=np.zeros((N+1,W+1),dtype=int)
for n in range(0, N):  
    for w in range(0, W + 1):  
        if w < wv[n, 0]:  
            dp[n+1, w] = dp[n, w]  
        else:  
            dp[n+1, w] = max(dp[n, w], dp[n, w - wv[n, 0]] + wv[n, 1])  
print(dp[N,W])

Submission status: Runtime Error

Solution code:
from math import inf
def rec(n,w):
    s=sum(val)
    dp=[[inf for i in range(s+1)] for j in range(n+1)]
    for i in range(n+1):
        for j in range(s+1):
            if j==0:
                dp[i][j]=0
            elif i==0:
                continue
            elif val[i-1]>j:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=min(dp[i-1][j-val[i-1]]+wt[i-1],dp[i-1][j])
    m=0
    for i in range(s+1):
        if dp[n][i]<=w:
            m=max(m,i)
    return m
  
n,w=map(int,input().split())
val=[]
wt=[]
for i in range(n):
    a,b=map(int,input().split())
    wt.append(a)
    val.append(b)
print(rec(n,w))

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

n,w = MI()
item = []
for i in range(n):
	item.append(LI())

def main():
 	dp = [0]*(w+1)
	for i in range(n):
		for j in range(w,item[i][0]-1,-1):
			dp[j] = max(dp[j], dp[j-item[i][0]]+item[i][1])
	print(dp[w])

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

n,w = MI()
item = []
for i in range(n):
	item.append(LI())

def main():
 	dp = [0]*(w+1)
	for i in range(n):
		for j in range(w,item[i][0]-1,-1):
			dp[j] = max(dp[j], dp[j-item[i][0]]+item[i][1])
	print(dp[w])

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
N, W = [int(i) for i in input().split()]
weight, value = [0] * (N + 1), [0] * (N + 1)
for i in range(1, N + 1):
    weight[i], value[i] = [int(i) for i in input().split()]
#%%
import  numpy as np
dp = np.zeros((N + 1, W + 1))

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

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline()
n,w=map(int,raw_input().split())

ans=[]
for i in range(n):
    z=list(map(int,raw_input().split()))
    ans.append(z)
dps=[[0 for i in range(w+1)] for i in range(n+1)]
vi=[[0 for i in range(w+1)] for i in range(n+1)]
#first index denotes row number , second denotes coloumn number
inde=0
def dp(w,inde):
    
    if(w<=0):
        return 0;
    if(inde>=n):
        return 0;
    
    if(vi[inde][w]):
        return dps[inde][w];
    vi[inde][w]=1
    
    if(w-ans[inde][0]==0 or dp(w-ans[inde][0],inde+1)!=0):
        dps[inde][w]=max(dp(w,inde+1),(dp(w-ans[inde][0],inde+1)+ans[inde][1]))
    else:
        dps[inde][w]=dp(w,inde+1)
        
    return dps[inde][w];

maxa=0
#driver code for finding out maximum of array
for i in range(n+1):
    for j in range(w+1):
        dps[i][j]=dp(j,i)
        maxa=max(maxa,dps[i][j])

print(maxa)

Submission status: Runtime Error

Solution code:
import numpy as np
input = sys.stdin.readline

N,W = 102,10**5+3
# weight,value = [None for _ in range(W)],[None for _ in range(N)]
weight,value = np.empty(W, dtype=int),np.empty(N, dtype=int)
n,w = None,None

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

def solve(n,w):
    global dp, weight

    if w < 0:
        return float('-inf')
    elif n < 0:
        return 0
    elif dp[n][w] != -1:
        return dp[n][w]
    dp[n][w] = max(value[n] + solve(n-1,w-weight[n]),solve(n-1,w))
    return dp[n][w]

def main():
    global n, w, weight, value

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

    print(solve(n-1,w))

main()

Submission status: Runtime Error

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

import numpy as np
weight = np.empty((110), int)
value = np.empty((110), int)
dp = np.zeros((110, 10010), int)
#print(weight.shape, value.shape, dp.shape)

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

dp[0, :W+1] = 0

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

ans = dp[N, W]
print(ans)