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 sys
sys.setrecursionlimit(10**9)
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase
def knapsack(W,n):
  if n==0 or W==0 :
    return 0
  elif cache.get((W,n)):
    return cache[(W,n)]
  
  else:
    if wt[n-1]<=W:
      cache[(W,n)]=max(knapsack(W,n-1),p[n-1]+knapsack(W-wt[n-1],n-1))
      return cache[(W,n)]
    else:
      cache[(W,n)]=knapsack(W,n-1)
      return cache[(W,n)]
    

def main():
    n,w=map(int,input().split())
    wt,p=[],[]
    cache={}
    for _ in range(n):
      temp_wt,temp_pr=map(int,input().split())
      wt.append(temp_wt)
      p.append(temp_pr)
    print(knapsack(w,n))


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
t = [[-1 for i in range(W + 1)] for j in range(n + 1)] 
  
  
def knapsack(wt, val, W, n):     
  
    # base conditions 
    if n == 0 or W == 0: 
        return 0
    if t[n][W] != -1: 
        return t[n][W] 
  
    # choice diagram code 
    if wt[n-1] <= W: 
        t[n][W] = max(val[n-1] + knapsack(wt, val, W-wt[n-1], n-1),knapsack(wt, val, W, n-1)) 
        return t[n][W] 
    elif wt[n-1] > W: 
        t[n][W] = knapsack(wt, val, W, n-1) 
        return t[n][W] 
n,W=map(int,input().split())
weight,profit=[],[]
for _ in range(n):
  w,p=map(int,input().split())
  weight.append(w)
  profit.append(p) 
print(knapsack(weight,profit, W, n))

Submission status: Runtime Error

Solution code:
import sys
import numba as nb

input = sys.stdin.readline

@nb.njit
def main():
    N, W = map(int, input().split())
    x = [tuple(map(int, input().split())) for _ in range(N)]

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

    for i, (w, v) in enumerate(x, 1):
        dpi = dp[i]
        dpim = dp[i-1]    
        for j in range(1, W + 1):
            if w <= j:
                a = dpim[j - w] + v
                if a > dpim[j]:
                    dpi[j] = a
                else:
                    dpi[j] = dpim[j]
            else:
                dpi[j] = dpim[j]

    print(dp[-1][W])

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
import numba as nb

input = sys.stdin.readline

@nb.njit
N, W = map(int, input().split())
x = [tuple(map(int, input().split())) for _ in range(N)]

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

for i, (w, v) in enumerate(x, 1):
    dpi = dp[i]
    dpim = dp[i-1]    
    for j in range(1, W + 1):
        if w <= j:
            a = dpim[j - w] + v
            if a > dpim[j]:
                dpi[j] = a
            else:
                dpi[j] = dpim[j]
        else:
            dpi[j] = dpim[j]

print(dp[-1][W])

Submission status: Runtime Error

Solution code:
import sys
#import math
import numpy as np
#= int(input())
#= input()
N, W = map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]

x = [list(map(int, sys.stdin.readline())) for _ in range(N)]

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

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

print(dp[-1][W])

Submission status: Runtime Error

Solution code:
#import
#import math
import numpy as np
#= int(input())
#= input()
N, W = map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]

weight = [0] * N
value = [0] * N

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



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

for i in range(1, N + 1):
    for j in range(1, W + 1):

        if x[i - 1][0] <= j:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1])
        else:
            dp[i][j] = dp[i - 1][j]

print(dp[-1][W])

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

Solution code:
n, w = input("").strip().split(' ')
n, w = int(n), int(w)
weights = [0]*n
values = [0]*n
for i in range(0, n):
  wi, ni = input("").strip().split(' ')
  values[i] = int(ni)
  weights[i] = int(wi)

mem = {}
def best(i, rem_weight):
  key = (i, rem_weight)
  if key in mem:
    return mem[(i, rem)]
  if rem_weight <= 0:
  	return 0
  if i < 0:
   	return 0
  result = 0
  if weights[i] <= rem_weight:
    result = max(result,
                 values[i] + best(i-1, rem_weight - weights[i]))
  result = max(result,
               best(i-1, rem_weight))
  mem[key] = result
  return result
print(best(n-1, w))

Submission status: Runtime Error

Solution code:
def bits(val):
  arr = []
  while val > 0:
    arr.append(val & 1)
    val >>= 1
  return arr
def select_vals(arr, b):
  acc = 0
  for i, v in enumerate(b):
    if v:
      acc += arr[i]
  return acc  
      	
first = input("").strip()
n, w = first.split(' ')
n, w = int(n), int(w)
weights = [0]*n
values = [0]*n
for i in range(0, n):
  line = input("").strip()
  wi, ni = line.split(' ')
  values[i] = int(ni)
  weights[i] = int(wi)

def best(weights, values, rem_weight):
  if rem_weight <= 0:
  	return 0
  result = 0
  if weights[0] < rem_weight:
    result = max(result,
                 values[0] + best(weights[1:], values[1:], rem_weight - weights[0]))
  result = max(result,
               best(weights[1:], values[1:], rem_weight))
print(best(weights, values, w))

#for index in range(0, 2**n):
#  acc = bits(index)
#  #print("{} -> {}".format(index, acc))
#  weight = select_vals(weights, acc)
#  value = select_vals(values, acc)
#  if weight <= w:
#    best_value = max(best_value, value)
#print(best_value)

Submission status: Runtime Error

Solution code:
def bits(val):
  arr = []
  while val > 0:
    arr.append(val & 1)
    val >>= 1
def select_bits(arr, bits):
  acc = 0
  for i, v in enumerate(bits):
    if v:
      acc += arr[i]
  return acc  
      	
first = raw_input("").strip()
n, w = first.split(' ')
weights = []
values = []
for i in range(0, n):
  line = raw_input("").strip()
  n, w = line.split(' ')
  values.append(n)
  weights.append(w)

best_value = 0

for index in range(0, 2**n):
  acc = bits(index)
  weight = select_vals(weights, bits)
  value = select_vals(values, bits)
  if weight < w:
    best_value = max(best_value, value)
print(best_value)

Submission status: Runtime Error

Solution code:
import sys
n,w=map(int,sys.stdin.read().split())
weight=[]
value=[]
total=w
for i in range(n):
    x,y=map(int,sys.stdin.read().split())
    weight.append(x)
    value.append(y)
l=len(weight)
dp=[[0]*(w+1) for j in range(l)]
for i in range(l):
    for w in range(total+1):
        if weight[i]<=w:
            dp[i][w]=max(value[i]+dp[i-1][w-weight[i]],dp[i-1][w])
        else:
            dp[i][w] = dp[i-1][w]
print(dp[l-1][total])

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
weight=[]
value=[]
total=w
for i in range(n):
    x,y=map(int,input().split())
    weight.append(x)
    value.append(y)
l=len(weight)
dp=[[0]*w for j in range(l)]
for i in range(l):
    for w in range(total+1):
        if weight[i]<=w:
            dp[i][w]=max(value[i]+dp[i-1][w-weight[i]],dp[i-1][w])
        else:
            dp[i][w] = dp[i-1][w]
print(dp[l-1][total])

Submission status: Runtime Error

Solution code:
def resolve():
    import sys
    import numpy as np
 
    readline = sys.stdin.readline
 
    N, W = map(int, readline().split())
    lst = [list(map(int, readline().split())) for _ in [0] * N]
    
    dp = np.zeros((N, W + 1), np.int64)
 
    for i in range(N):
        w, v = lst[i][0], lst[i][1]
        for sum_w in range(W + 1):
            if sum_w >= w:
                dp[i][sum_w] = max(dp[i][sum_w],
                                   dp[i - 1][sum_w - w] + v)
            dp[i][sum_w] = max(dp[i][sum_w], dp[i - 1][sum_w])
    print(max(dp[-1]))
 
 
resolve()

Submission status: Runtime Error

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_d
N,W = map(int,input().split())
Goods_List=[]
for i in range(N):
    Goods_List.append(list(map(int,input().split())))

Sum_Weight = sum(map(lambda x:x[0],Goods_List))
dp = [[-1] * Sum_Weight for i in range(N)]

for i in range(N):
    Current_Weight = Goods_List[i][0]
    Current_Value  = Goods_List[i][1]
    dp[i][0] = 0
    if i == 0:
        dp[i][Current_Weight] = Current_Value
    else:
        Search_List = [j for j, x in enumerate(dp[i-1]) if x > -1]
        Comb_List = [0,Current_Weight]
        for k in Search_List:
            for l in Comb_List:
                if k + l > W:
                    break
                elif l == 0:
                    dp[i][k+l] = dp[i-1][k+l]
                else:
                    dp[i][k+l] = max(dp[i-1][k+l],dp[i-1][k]+Current_Value)
                    
print(max(dp[N-1]))

Submission status: Runtime Error

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_d
N,W = map(int,input().split())
Goods_List=[]
for i in range(N):
    Goods_List.append(list(map(int,input().split())))

Sum_Weight = sum(map(lambda x:x[0],Goods_List))
dp = [[-1] * Sum_Weight for i in range(N)]

for i in range(N):
    Current_Weight = Goods_List[i][0]
    Current_Value  = Goods_List[i][1]
    dp[i][0] = 0
    if i == 0:
        dp[i][Current_Weight] = Current_Value
    else:
        Search_List = [i for i, x in enumerate(dp[i-1]) if x > -1]
        Comb_List = [0,Current_Weight]
        for j in Search_List:
            for k in Comb_List:
                if j + k > W:
                    break
                elif k == 0:
                    dp[i][j+k] = dp[i-1][j+k]
                else:
                    dp[i][j+k] = max(dp[i-1][j+k],dp[i-1][j]+Current_Value)
                    
print(max(dp[N-1]))

Submission status: Runtime Error

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_d
N,W = map(int,input().split())
Goods_List=[]
for i in range(N):
    Goods_List.append(list(map(int,input().split())))

Sum_Weight = sum(map(lambda x:x[0],Goods_List))
dp = [[-1] * Sum_Weight for i in range(N)]

for i in range(N):
    Current_Weight = Goods_List[i][0]
    Current_Value  = Goods_List[i][1]
    dp[i][0] = 0
    if i == 0:
        dp[i][Current_Weight] = Current_Value
    else:
        Search_List = [i for i, x in enumerate(dp[i-1]) if x > -1]
        Comb_List = [0,Current_Weight]
        for j in Search_List:
            for k in Comb_List:
                if j + k > W:
                    break
                elif k == 0:
                    dp[i][j+k] = dp[i-1][j+k]
                else:
                    dp[i][j+k] = max(dp[i-1][j+k],dp[i-1][j]+Current_Value)
                    
            

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

Submission status: Runtime Error

Solution code:
"""
https://atcoder.jp/contests/dp/tasks/dp_d
"""
import sys

N,W = [int(i) for i in sys.stdin.readline().split(" ")]
wt = []
val = []
for i in range(N):
    w, v = [int(i) for i in sys.stdin.readline().split(" ")]
    wt.append(w)
    val.append(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, sum(wt) + 1):
        if wt[i-1] <= j:
            dp[i][j] = max(
                val[i-1] + dp[i-1][j-wt[i-1]],
                dp[i-1][j]
            )
        else:
            dp[i][j] = dp[i-1][j]
    
print(dp[N][W])

Submission status: Runtime Error

Solution code:
import numpy as np

N, W = [int(x) for x in input().split()]
weight = np.zeros((N,2))
for x in range(N):
    weight[x] = [int(y) for y in input().split()]
#topdown
memo = np.zeros((N+1,W+1))
for x in range(N+1):
    memo[x] = [-1]*(W+1)

def dp(n,w):
    if w < 0:
        return -float('inf')
    elif n == 0 or w == 0:
        return 0
    elif memo[n][w] != -1:
        return memo[n][w]
    else:
        memo[n][w] = max(dp(n-1,w), dp(n-1,w - int(weight[n-1][0])) + weight[n-1][1])
        return memo[n][w]

print(int(dp(N,W)))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

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]*110]*11010
#dp=[[0 for _ in range(W+1)] for _ in range(N+1)]
dp=[[0 for _ in range(110)] for _ in range(11010)]


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]

print(dp[N][W])

Submission status: Runtime Error

Solution code:
def main():
    n,w = map(int,input().split())
    dp = [[0 for j in range(w+1)] for i in range(n+1)]
    for i in range(n):
        w1,v1 = map(int,input().split())
        for j in range(w+1):
            dp[i+1][j] =  max(dp[i][j-w1]+v1,dp[i][j]) if j-w1>= 0 else dp[i+1][j] = dp[i][j]      
    print(dp[n][w])

main()

Submission status: Runtime Error

Solution code:
N,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ 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(1,W+1):
        if wv[i-1][0]<=j:
            dp[i][j]=max(dp[i-1][j],dp[i-1][max(0,j-wv[i-1][0])]+wv[i-1][1])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
# from sys import stdin, stdout
n,capacity=map(int,input().split())
weights=[0]*n
values=[0]*n
for i in range(n):
    weights[i],values[i]=map(int,input().split())
dp=[[0]*(capacity+1) for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,weights+1):
        if(weights[i-1]<=j):
            dp[i][j]=max(values[i-1]+dp[i-1][j-weights[i-1]],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[n][capacity])

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout
n,capacity=map(int,stdin.readline().split())
weights=[0]*n
values=[0]*n
for i in range(n):
    weights[i],values[i]=map(int,stdin.readline().split())
dp=[[0]*(capacity+1) for i in range(n+1)]
for i in range(n+1):
    for j in range(weights+1):
        if(weights[i-1]<=j):
            dp[i][j]=max(values[i-1]+dp[i-1][j-weights[i-1]],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[n][capacity])

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout
def knapsack(weights,values,capacity,n,memo):
    if(memo[n][capacity]!=-1):
        return memo[n][capacity]
    if(n==0 or capacity==0):
        return 0
    val=0
    left=values[n-1]+knapsack(weights,values,capacity-weights[n-1],n-1,memo)
    right=knapsack(weights,values,capacity,n-1,memo)
    if(weights[n-1]<=capacity):
        temp=max(left,right)
        memo[n][capacity]=temp
        return temp
    memo[n][capacity]=right
    return right

n,capacity=map(int,stdin.readline().split())
weights=[0]*n
values=[0]*n
for i in range(n):
    weights[i],values[i]=map(int,stdin.readline().split())
memo=[[-1]*(capacity+1) for i in range(n+1)]
stdout.write(str(knapsack(weights,values,capacity,n,memo)))

Submission status: Runtime Error

Solution code:
import sys
#import numpy as np
#from collections import defaultdict
import math
#from collections import deque

input = sys.stdin.readline
import numpy as np



def main():

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

    dp = [0] * (W+2)

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

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

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




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
def main():
    N,W=tuple(map(int,sys.stdin.readline().split()))
    w,v=[0],[0]
    for _ in [0]*N:
        wi,vi=tuple(map(int,sys.stdin.readline().split()))
        w.append(wi)
        v.append(vi)
    dp=[[0 for _ in [0]*(W+1)] for _ in [0]*(N+1)]
    print(dp)
    for i in range(1,N+1):
        for j in range(1,W+1):
            print(f'i,j = {i}, {j}')
            dp[i][j]=max(dp[i-1][j], dp[i][j-1])
            if w[i]<=j:dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i])
        print(dp[i])
    print(dp[N][W])
if __name__=='__main__':main()

Submission status: Runtime Error

Solution code:
mod=10**9+7
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
import numpy as np
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a,b=mi()
dp=[0]*(b+1)
for i in range(a):
  x,y=mi()
  for i in range(b-x,-1,-1):
      dp[i+x]=max(dp[i]+y,dp[i+x])
print(max(dp))

Submission status: Runtime Error

Solution code:
from sys import stdin, gettrace
 
if not gettrace():
    def input():
        return next(stdin)[:-1]
 
 
# def input():
#    return stdin.buffer.readline()
 
def main():
    n,w=map(int,input().split())
	li=[]
	for i in range(n):
    	temp=[int(x) for x in input().split()]
    	li.append(temp)
	dp=[[[-1,-1] for j in range(w+1)] for i in range(n)]
	dp[n-1][0]=[li[n-1][1],li[n-1][1]]
	for i in range(n-1,-1,-1):
    	for j in range(w,-1,-1):
        	if j==0:
            	dp[i][j]=li[i][1],li[i][1]
        	if i==(n-1):
            	if li[i][0]<=j:
                	dp[i][j]=li[i][1],li[i][1]
            	else:
                	dp[i][j]=0,0
        	else:
            	mx=li[i][1]
            	for k in range(i+1,n):
                	if (j-li[i][0])>=li[k][0]:
                    	val=dp[k][j-li[i][0]]
                    	mx=max(mx,val[0]+li[i][1])
            	val=dp[i+1][j]
            	overall=max(mx,val[1])
            	dp[i][j]=[mx,overall]
	print(dp[0][w][1])
 
 
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin, gettrace
 
if not gettrace():
    def input():
        return next(stdin)[:-1]
 
 
# def input():
#    return stdin.buffer.readline()
 
def main():
    dn,w=map(int,input().split())
	li=[]
	for i in range(n):
    	temp=[int(x) for x in input().split()]
    	li.append(temp)
	dp=[[[-1,-1] for j in range(w+1)] for i in range(n)]
	dp[n-1][0]=[li[n-1][1],li[n-1][1]]
	for i in range(n-1,-1,-1):
    	for j in range(w,-1,-1):
        	if j==0:
            	dp[i][j]=li[i][1],li[i][1]
        	if i==(n-1):
            	if li[i][0]<=j:
                	dp[i][j]=li[i][1],li[i][1]
            	else:
                	dp[i][j]=0,0
        	else:
            	mx=li[i][1]
            	for k in range(i+1,n):
                	if (j-li[i][0])>=li[k][0]:
                    	val=dp[k][j-li[i][0]]
                    	mx=max(mx,val[0]+li[i][1])
            	val=dp[i+1][j]
            	overall=max(mx,val[1])
            	dp[i][j]=[mx,overall]
	print(dp[0][w][1])
 
 
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def knapsack01rec(n, W, weights, values, dp, i, j):
    # i = up until item i, j = up until weight j
    if i == 0 or j <= 0:
        return 0

    if dp[i][j] != -1:
        return dp[i][j]

    if weights[i-1] > j:
        # weights[i] doesn't fit in knapsack
        dp[i][j] = knapsack01rec(n, W, weights, values, dp, i-1, j)
    else:
        dp[i][j] = max(
            knapsack01rec(n, W, weights, values, dp, i-1, j),
            knapsack01rec(n, W, weights, values, dp, i-1, j-weights[i-1]) + values[i-1])
    return dp[i][j]

dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01rec(n, W, weights, values, dp, n, W)

print(res)

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
items = [[int(j) for j in input().split()] for i in range(n)]
dp = [[0] * 2*10*5 for i in range(110)]
for i in range(1, n + 1):
    for sum_w in range(1, w + 1):
        if sum_w >= items[i - 1][0]:
            dp[i][sum_w] = max(dp[i][sum_w], dp[i - 1][sum_w - items[i - 1][0]] + items[i - 1][1])
        dp[i][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())
items = [[int(j) for j in input().split()] for i in range(n)]
dp = [[0] * (10*5 + 10*4) for i in range(110)]
for i in range(1, n + 1):
    for sum_w in range(1, w + 1):
        if sum_w >= items[i - 1][0]:
            dp[i][sum_w] = max(dp[i][sum_w], dp[i - 1][sum_w - items[i - 1][0]] + items[i - 1][1])
        dp[i][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())
items = [[int(j) for j in input().split()] for i in range(n)]
dp = [[0] * 10*5 + 10*4 for i in range(110)]
for i in range(1, n + 1):
    for sum_w in range(1, w + 1):
        if sum_w >= items[i - 1][0]:
            dp[i][sum_w] = max(dp[i][sum_w], dp[i - 1][sum_w - items[i - 1][0]] + items[i - 1][1])
        dp[i][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())
items = [[int(j) for j in input().split()] for i in range(n)]
dp = [[0] * 110 for i in range(10*5 + 10*4)]
for i in range(1, n + 1):
    for sum_wgt in range(1, w + 1):
        if sum_wgt >= items[i - 1][0]:
            dp[i][sum_wgt] = max(dp[i][sum_wgt], dp[i - 1][sum_wgt - items[i - 1][0]] + items[i - 1][1])
        dp[i][sum_wgt] = max(dp[i][sum_wgt], dp[i - 1][sum_wgt])
print(dp[n][w])

Submission status: Runtime Error

Solution code:
def knapSack(W, 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(W + 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())
w=[]
v=[]
for i in range(n):
    a,b= map(int, input().split())
    w.append(a)
    v.append(b)
print(knap(c,w,v,n))

Submission status: Runtime Error

Solution code:
import sys
import math
def I():return int(sys.stdin.readline().replace("\n",""))
def I2():return map(int,sys.stdin.readline().replace("\n","").split())
def S():return str(sys.stdin.readline().replace("\n",""))
def L():return list(sys.stdin.readline().replace("\n",""))
def Intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def Lx(k):return list(map(lambda x:int(x)*-k,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":
    N ,W = I2()
    w = [0]*N
    v = [0]*W
    dp = [[0]*N+1 for i in range(W+1)]
    for i in range(N):
        a,b = I2()
        w[i] = a
        v[i] = b
    for i in range(N):
        for j in range(0,W+1):
            if(j >= w[i]):
                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)
    print(dp[N][W])

Submission status: Runtime Error

Solution code:
import sys
import math
import numpy as np
def I():return int(sys.stdin.readline().replace("\n",""))
def I2():return map(int,sys.stdin.readline().replace("\n","").split())
def S():return str(sys.stdin.readline().replace("\n",""))
def L():return list(sys.stdin.readline().replace("\n",""))
def Intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def Lx(k):return list(map(lambda x:int(x)*-k,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":
    N ,W = I2()
    w = [0]*N
    v = [0]*W
    dp = [[0]*N+1 for i in range(W+1)]
    for i in range(N):
        a,b = I2()
        w[i] = a
        v[i] = b
    for i in range(N):
        for j in range(0,W+1):
            if(j >= w[i]):
                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)
    print(dp[N][W])

Submission status: Runtime Error

Solution code:
import sys
import math
import numpy as np
def I():return int(sys.stdin.readline().replace("\n",""))
def I2():return map(int,sys.stdin.readline().replace("\n","").split())
def S():return str(sys.stdin.readline().replace("\n",""))
def L():return list(sys.stdin.readline().replace("\n",""))
def Intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def Lx(k):return list(map(lambda x:int(x)*-k,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":
    N ,W = I2()
    w = [0]*N
    v = [0]*W
    dp = np.zeros([N+1,W+1],dtype = "int64")
    for i in range(N):
        a,b = I2()
        w[i] = a
        v[i] = b
    for i in range(N):
        for j in range(0,W+1):
            if(j >= w[i]):
                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)
    print(dp[N][W])

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())

dp = [[0] * (W + 1) for _ in range(N + 1)]
# dp[i][j](j=0,1,...,W)の値が求まっている状態で、dp[i+1][j]を更新することを考える

for i in range(N):
    for j in range(W+1):#重さ0からWまでチェック
        if j-w[i]>=0:#入れてもOKな場合,容量と価値を足す
            dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i])
        else:#何も入れずに先に進む
            dp[i+1][j]=dp[i][j]
print(max(set(dp)))

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())

dp = [[0] * (W + 1) for _ in range(N + 1)]
# dp[i][j](j=0,1,...,W)の値が求まっている状態で、dp[i+1][j]を更新することを考える

for i in range(N):
    for j in range(W+1):#重さ0からWまでチェック
        if j-w[i]>=0:#入れてもOKな場合,容量と価値を足す
            dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i])
        else:#何も入れずに先に進む
            dp[i+1][j]=dp[i][j]
print(max(set(dp))

Submission status: Runtime Error

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

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

d = {(W, 0)}

for w, v in items:
    tmp = set()
    for rw, rv in d:
        if rw >= w:
            tmp.add((rw-w, rv+v))
    d |= tmp

d = {elm[1] for elm in d}

print(max(d))

Submission status: Runtime Error

Solution code:
import numpy as np

N, W = map(int, input().split())
dp = np.array([ [0]*(W+1) ] * (N+1))
for n in range(1,N+1):
    w, v = map(int, input().split() )
    dp[n][:] = dp[n-1][:]
    dp[n][w:W+1] = max(dp[n-1][w:W+1], dp[n-1][:W+1-w]+v )
    # for w_lim in range(1,W+1):
    #     if w_lim - wv[n][0] >= 0 :
    #         dp[n][w_lim] = max( dp[n-1][w_lim], dp[n-1][w_lim-wv[n][0]]+wv[n][1] )
    #     else :
    #         dp[n][w_lim] = dp[n-1][w_lim]
print(dp[N][W])

Submission status: Runtime Error

Solution code:
import numpy as np

N, W = map(int, input().split())
dp = np.array([ [0]*(W+1) ] * (N+1))
wv = [[0,0]]
for n in range(1,N+1):
    w, v = map(int, input().split() )
    dp[n][:] = dp[n-1][:]
    dp[n][w:W+1] = max(dp[n-1][w:W+1], dp[n-1][W+1-w]+v )
    # for w_lim in range(1,W+1):
    #     if w_lim - wv[n][0] >= 0 :
    #         dp[n][w_lim] = max( dp[n-1][w_lim], dp[n-1][w_lim-wv[n][0]]+wv[n][1] )
    #     else :
    #         dp[n][w_lim] = dp[n-1][w_lim]
print(dp[N][W])

Submission status: Runtime Error

Solution code:
import numpy as np

N, W = map(int, input().split())
dp = np.array([ [0]*(W+1) ] * (N+1))
wv = [[0,0]]
for n in range(1,N+1):
    w, v = map(int, input().split() )
    dp[n][w:W+1] = max(dp[n-1][w:W+1], dp[n-1][W+1-w]+v )
    # for w_lim in range(1,W+1):
    #     if w_lim - wv[n][0] >= 0 :
    #         dp[n][w_lim] = max( dp[n-1][w_lim], dp[n-1][w_lim-wv[n][0]]+wv[n][1] )
    #     else :
    #         dp[n][w_lim] = dp[n-1][w_lim]
print(dp[N][W])

Submission status: Runtime Error

Solution code:
import numpy as np

N, W = map(int, input().split())
wv = [[0,0]]
for _ in range(N):
    wv.append( list(map(int, input().split())))
dp = np.array([ [0]*(W+1) ] * (N+1))
for n in range(1,N+1):
    for w_lim in range(1,W+1):
        if w_lim - wv[n][0] >= 0 :
            dp[n][w_lim] = max( dp[n-1][w_lim], dp[n-1][w_lim-wv[n][0]]+wv[n][1] )
        else :
            dp[n][w_lim] = dp[n-1][w_lim]
print(dp[N][W])