Problem:


0-1 Knapsack Problem

You have N items that you want to put them into a knapsack. Item i has value vi and weight wi.

You want to find a subset of items to put such that:

The total value of the items is as large as possible.

The items have combined weight at most W, that is capacity of the knapsack.

Find the maximum total value of items in the knapsack.

Input

N W
v1 w1
v2 w2
:
vN wN

The first line consists of the integers N and W. In the following lines, the value and weight of the i-th item are given.

Output

Print the maximum total values of the items in a line.

Constraints

 1 ≤ N ≤ 100
	

 1 ≤ vi ≤ 1000
	

 1 ≤ wi ≤ 1000
	

 1 ≤ W ≤ 10000
	

Sample Input 1

4 5
4 2
5 2
2 1
8 3

Sample Output 1

13

Sample Input 2

2 20
5 9
4 10

Sample Output 2

9



Sample input:
4 5
4 2
5 2
2 1
8 3


Sample output:
13

Submission status: Runtime Error

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

weight = [0]*N
value = [0]*N
dp = np.zeros((N+1,W+1))

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

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

Submission status: Runtime Error

Solution code:
import numpy

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
n,w = map(int,input().split())
v = [0] * (n+1)
w = [0] * (n+1)

for j in range(1, n+1):
    v[j], w[j] = map(int,input().split())

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

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

print(max(dp))

Submission status: Runtime Error

Solution code:
l=[]
while(item=input().split()):
	l.append([item[1],item[0]])

# n=4
# l=[[2,3],[1,2],[3,4],[2,2]] #w,v
# W=5

def solve(i,w):
	if i==n or w<0:
		return(0)
	elif w-l[i][0]<0:
		return(0)
	else:
		return(max(solve(i+1,w),l[i][1]+solve(i+1,w-l[i][0])))

print(solve(0,W))

Submission status: Runtime Error

Solution code:
l=[]
N,W=list(map(int,(input().split())))
while(N):
	item=list(map(int,input().split))
	l.append([item[1],item[0]])
	N-=1
# n=4
# l=[[2,3],[1,2],[3,4],[2,2]] #w,v
# W=5

def solve(i,w):
	if i==n or w<0:
		return(0)
	elif w-l[i][0]<0:
		return(0)
	else:
		return(max(solve(i+1,w),l[i][1]+solve(i+1,w-l[i][0])))

print(solve(0,W))

Submission status: Runtime Error

Solution code:
l=[]
N,W=list(map(int,(input().split())))
for i in range(N):
	item=list(map(int,input().split))
	l.append([item[1],item[0]])
	N-=1
# n=4
# l=[[2,3],[1,2],[3,4],[2,2]] #w,v
# W=5

def solve(i,w):
	if i==n or w<0:
		return(0)
	elif w-l[i][0]<0:
		return(0)
	else:
		return(max(solve(i+1,w),l[i][1]+solve(i+1,w-l[i][0])))

print(solve(0,W))

Submission status: Runtime Error

Solution code:
l=[]
N,W=list(map(int,input().split()))
for i in range(N):
	item=list(map(int,input().split))
	l.append([item[1],item[0]])

# n=4
# l=[[2,3],[1,2],[3,4],[2,2]] #w,v
# W=5

def solve(i,w):
	if i==n or w<0:
		return(0)
	elif w-l[i][0]<0:
		return(0)
	else:
		return(max(solve(i+1,w),l[i][1]+solve(i+1,w-l[i][0])))

print(solve(0,W))

Submission status: Runtime Error

Solution code:
l=[]
N,W=list(map(int,input().split()))
for i in range(N):
	item=list(map(int,input().split))
	l.append([item[1],item[0]])

# n=4
# l=[[2,3],[1,2],[3,4],[2,2]] #w,v
# W=5

print(l)
def solve(i,w):
	if i==n or w<0:
		return(0)
	elif w-l[i][0]<0:
		return(0)
	else:
		return(max(solve(i+1,w),l[i][1]+solve(i+1,w-l[i][0])))

print(solve(0,W))

Submission status: Runtime Error

Solution code:
l=[]
n,W=list(map(int,input().split()))
for i in range(n):
	item=list(map(int,input().split))
	l.append([item[1],item[0]])

# n=4
# l=[[2,3],[1,2],[3,4],[2,2]] #w,v
# W=5

print(l)
def solve(i,w):
	if i==n or w<0:
		return(0)
	elif w-l[i][0]<0:
		return(0)
	else:
		return(max(solve(i+1,w),l[i][1]+solve(i+1,w-l[i][0])))

print(solve(0,W))

Submission status: Runtime Error

Solution code:
l=[]
n,W=list(map(int,input().split()))
for i in range(n):
	item=list(map(int,input().split))
	l.append([item[1],item[0]])

# n=4
# l=[[2,3],[1,2],[3,4],[2,2]] #w,v
# W=5

print(l)
def solve(i,w):
	if i==n:
		return(0)
	elif w-l[i][0]<0:
		return(0)
	else:
		a=solve(i+1,w)
		b=l[i][1]+solve(i+1,w-l[i][0])
		if b>a:
			print("select",i)
			return(b)
		else:
			return(a)

print(solve(0,W))

Submission status: Runtime Error

Solution code:
l=[]
n,W=input().split()
n=int(n)
W=int(W)
for i in range(n):
	item=list(map(int,input().split))
	l.append([item[1],item[0]])

# n=4
# l=[[2,3],[1,2],[3,4],[2,2]] #w,v
# W=5

print(l)
def solve(i,w):
	if i==n:
		return(0)
	elif w-l[i][0]<0:
		return(0)
	else:
		a=solve(i+1,w)
		b=l[i][1]+solve(i+1,w-l[i][0])
		if b>a:
			print("select",i)
			return(b)
		else:
			return(a)

print(solve(0,W))

Submission status: Runtime Error

Solution code:
l=[]
n,W=input().split()
n=int(n)
W=int(W)
for i in range(n):
	item=list(map(int,input().split))
	l.append([item[1],item[0]])

# n=4
# l=[[2,3],[1,2],[3,4],[2,2]] #w,v
# W=5

def solve(i,w):
	if i==n:
		return(0)
	elif w-l[i][0]<0:
		return(0)
	else:
		a=solve(i+1,w)
		b=l[i][1]+solve(i+1,w-l[i][0])
		if b>a:
			print("select",i)
			return(b)
		else:
			return(a)

print(solve(0,W))

Submission status: Runtime Error

Solution code:
l=[]
n,W=input().split()
n=int(n)
W=int(W)
for i in range(n):
	item=list(map(int,input().split))
	l.append([item[1],item[0]])

# n=4
# l=[[2,3],[1,2],[3,4],[2,2]] #w,v
# W=5

def solve(i,w):
	if i==n:
		return(0)
	elif w-l[i][0]<0:
		return(0)
	else:
		a=solve(i+1,w)
		b=l[i][1]+solve(i+1,w-l[i][0])
		if b>a:
			return(b)
		else:
			return(a)

print(solve(0,W))

Submission status: Runtime Error

Solution code:
l=[]
n,W=input().split()
n=int(n)
W=int(W)
for i in range(n):
	item=list(map(int,input().split()))
	l.append([item[1],item[0]])

dp=[[False for j in range(W)] for i in range(n)]


def solve(i,w):
	if dp[i][w]==False:
		if i==n:
			res=(0)
		elif w-l[i][0]<0:
			res=(solve(i+1,w))
		else:
			a=solve(i+1,w)
			b=l[i][1]+solve(i+1,w-l[i][0])
			if b>a:
				res=(b)
			else:
				res=(a)
		dp[i][w]=res
		return(res)
	else:
		return(dp[i][w])

print(solve(0,W))

Submission status: Runtime Error

Solution code:
l=[]
n,W=input().split()
n=int(n)
W=int(W)
for i in range(n):
	item=list(map(int,input().split()))
	l.append([item[1],item[0]])

dp=[[False for j in range(n)] for i in range(W)]


def solve(i,w):
	if dp[i][w]==False:
		if i==n:
			res=(0)
		elif w-l[i][0]<0:
			res=(solve(i+1,w))
		else:
			a=solve(i+1,w)
			b=l[i][1]+solve(i+1,w-l[i][0])
			if b>a:
				res=(b)
			else:
				res=(a)
		dp[i][w]=res
		return(res)
	else:
		return(dp[i][w])

print(solve(0,W))

Submission status: Runtime Error

Solution code:
l=[]
n,W=input().split()
n=int(n)
W=int(W)
for i in range(n):
	item=list(map(int,input().split()))
	l.append([item[1],item[0]])

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

print(dp)
def solve(i,w):
	if dp[i][w]==False:
		if i==n:
			res=(0)
		elif w-l[i][0]<0:
			res=(solve(i+1,w))
		else:
			a=solve(i+1,w)
			b=l[i][1]+solve(i+1,w-l[i][0])
			if b>a:
				res=(b)
			else:
				res=(a)
		dp[i][w]=res
		return(res)
	else:
		return(dp[i][w])

print(solve(0,W))

Submission status: Runtime Error

Solution code:
import numpy as np

N, W = list(map(int, input().split()))
v_list = list()
w_list = list()

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

sum_v_table = np.zeros([N+1, W+1], int)

for i in range(1, N+1):
    item = v_list[i-1], w_list[i-1]
    for w in range(1, W+1):
        if item[1] > w:
            sum_v_table[i, w] = sum_v_table[i-1, w]
            continue
        sum_v_table[i, w] = max(sum_v_table[i-1, w], sum_v_table[i-1, w-item[1]] + item[0])

max_sum_v = sum_v_table[N, W]

print(max_sum_v)

Submission status: Runtime Error

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

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

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

print(value[W])

Submission status: Runtime Error

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

v = [0] * N
w = [0] * N

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

def rec(i, j):
if i == N:
res = 0
elif j < w[i]: res = rec(i + 1, j) else: res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]) return res print(rec(0, W)) [/sourcecode]

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split(" "))
???
v = [0] * N
w = [0] * N
dp = [[-1 for i in range(W + 1)] for j in range(N + 1)]
???
for i in range(N):
    v[i], w[i] = map(int, input().split(" "))
???
def rec(i, j):
    if dp[i][j] != -1:
        return dp[i][j]
???
    if i == N:
        res = 0
    elif j < w[i]: 
        res = rec(i + 1, j) 
    else: 
        res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]) 
        dp[i][j] = res 
    return res 
print(rec(0, W))

Submission status: Runtime Error

Solution code:
# 0-1 Knapsack Problem
N, W = [int(x) for x in input().split()]
items = []
for i in range(N):
    items.append(tuple(int(x) for x in input().split()))

DP = [0] * (W+1)
for i in range(N):
    v, w = items[i]
    for j in range(W, w-1, -1):
        DP[j] = max(DP[j], v + DP[j-w])

print(DP[-1][-1])

Submission status: Runtime Error

Solution code:
import copy
def main():
    [N,W]=input().split(" ")'''read from keyboard and put all the item to box'''
    N=int(N)
    W=int(W)
    box=[]
    for i in range(N):
        [vi,wi]=input().split(" ")
        box.append([float(vi),float(wi)])
        
    assemblebox=[]'''creat a set of full permutation of input. using recursion'''
    assemblebox=permutations(N,box,assemblebox,[])

    maximum=0'''optimization'''
    for i in range(len(assemblebox)):
        weight=0
        value=0
        for j in range(N):
            weight=weight+assemblebox[i][j][1]
            if(weight>W):
                break
            value=value+assemblebox[i][j][0]
        if(maximum<value):
            maximum=value
            
    print(maximum)'''output'''
        

    return 0

def permutations(N,box,assemblebox,record):
    for i in range(N):
        Np=N
        boxp=copy.deepcopy(box)
        recordp=copy.deepcopy(record)
        recordp.append(box[i])
        boxp.pop(i)
        Np=Np-1
        if(Np==0):
            assemblebox.append(recordp)
        else:
            result=permutations(Np,boxp,assemblebox,recordp)
    return assemblebox

main()

Submission status: Runtime Error

Solution code:
import copy
def main():
    [N,W]=input().split(" ")'''read from keyboard and put all the item to box'''
    N=int(N)
    W=int(W)
    box=[]
    for i in range(N):
        [vi,wi]=input().split(" ")
        box.append([float(vi),float(wi)])
        
    assemblebox=[]'''creat a set of full permutation of input. using recursion'''
    assemblebox=permutations(N,box,assemblebox,[])

    maximum=0'''optimization'''
    for i in range(len(assemblebox)):
        weight=0
        value=0
        for j in range(N):
            weight=weight+assemblebox[i][j][1]
            if(weight>W):
                break
            value=value+assemblebox[i][j][0]
        if(maximum<value):
            maximum=value
            
    print(int(maximum))'''output'''
        

    return 0

def permutations(N,box,assemblebox,record):
    for i in range(N):
        Np=N
        boxp=copy.deepcopy(box)
        recordp=copy.deepcopy(record)
        recordp.append(box[i])
        boxp.pop(i)
        Np=Np-1
        if(Np==0):
            assemblebox.append(recordp)
        else:
            result=permutations(Np,boxp,assemblebox,recordp)
    return assemblebox

main()

Submission status: Runtime Error

Solution code:
import copy
def main():
    [N,W]=input().split(" ")
    '''read from keyboard and put all the item to box'''
    N=int(N)
    W=int(W)
    box=[]
    for i in range(N):
        [vi,wi]=input().split(" ")
        box.append([float(vi),float(wi)])
        
    assemblebox=[]
    '''creat a set of full permutation of input. using recursion'''
    assemblebox=permutations(N,box,assemblebox,[])

    maximum=0
    '''optimization'''
    for i in range(len(assemblebox)):
        weight=0
        value=0
        for j in range(N):
            weight=weight+assemblebox[i][j][1]
            if(weight>W):
                break
            value=value+assemblebox[i][j][0]
        if(maximum<value):
            maximum=value
            
    print(maximum)
    '''output'''
        

    return 0

def permutations(N,box,assemblebox,record):
    for i in range(N):
        Np=N
        boxp=copy.deepcopy(box)
        recordp=copy.deepcopy(record)
        recordp.append(box[i])
        boxp.pop(i)
        Np=Np-1
        if(Np==0):
            assemblebox.append(recordp)
        else:
            result=permutations(Np,boxp,assemblebox,recordp)
    return assemblebox

main()

Submission status: Runtime Error

Solution code:
import copy
def main():
    [N,W]=input().split(" ")
    N=int(N)
    W=int(W)
    box=[]
    for i in range(N):
        [vi,wi]=input().split(" ")
        box.append([float(vi),float(wi)])
        
    assemblebox=[]
    assemblebox=permutations(N,box,assemblebox,[])

    maximum=0
    for i in range(len(assemblebox)):
        weight=0
        value=0
        for j in range(N):
            weight=weight+assemblebox[i][j][1]
            if(weight>W):
                break
            value=value+assemblebox[i][j][0]
        if(maximum<value):
            maximum=value
            
    print(maximum)
        

    return 0

def permutations(N,box,assemblebox,record):
    for i in range(N):
        Np=N
        boxp=copy.deepcopy(box)
        recordp=copy.deepcopy(record)
        recordp.append(box[i])
        boxp.pop(i)
        Np=Np-1
        if(Np==0):
            assemblebox.append(recordp)
        else:
            result=permutations(Np,boxp,assemblebox,recordp)
    return assemblebox

main()

Submission status: Runtime Error

Solution code:
def main():
    [N,W]=input().split(" ")
    N=int(N)
    W=int(W)
    box=[]
    for i in range(N):
        [vi,wi]=input().split(" ")
        box.append([float(vi),float(wi)])
        
    assemblebox=[]
    assemblebox=permutations(N,box,assemblebox,[])

    maximum=0
    for i in range(len(assemblebox)):
        weight=0
        value=0
        for j in range(N):
            weight=weight+assemblebox[i][j][1]
            if(weight>W):
                break
            value=value+assemblebox[i][j][0]
        if(maximum<value):
            maximum=value
            
    print(maximum)
        

    return 0

def permutations(N,box,assemblebox,record):
    for i in range(N):
        Np=N
        boxp=copy.deepcopy(box)
        recordp=copy.deepcopy(record)
        recordp.append(box[i])
        boxp.pop(i)
        Np=Np-1
        if(Np==0):
            assemblebox.append(recordp)
        else:
            result=permutations(Np,boxp,assemblebox,recordp)
    return assemblebox

main()

Submission status: Runtime Error

Solution code:
import numpy as np
def main():
    [N,W]=input().split(" ")
    N=int(N)
    W=int(W)
    inputset=[]
    for i in range(N):
        [vi,wi]=input().split(" ")
        inputset.append([int(vi),int(wi)])

    graph=np.zeros([N+1,W+1])

    for i in range(N):
        for j in range(W+1):
            if(inputset[i][1]>j):
                graph[i+1,j]=graph[i,j]
            else:
                rest=j-inputset[i][1]
                choosevalue=graph[i,rest]+inputset[i][0]
                nonchoosevalue=graph[i,j]
                if(choosevalue>nonchoosevalue):
                    graph[i+1,j]=choosevalue
                else:
                    graph[i+1,j]=nonchoosevalue

    print(graph[N,W])

main()

Submission status: Runtime Error

Solution code:
import numpy as np
def main():
    [N,W]=input().split(" ")
    N=int(N)
    W=int(W)
    inputset=[]
    for i in range(N):
        [vi,wi]=input().split(" ")
        inputset.append([int(vi),int(wi)])

    graph=np.zeros([N+1,W+1])

    for i in range(N):
        for j in range(W+1):
            if(inputset[i][1]>j):
                graph[i+1,j]=graph[i,j]
            else:
                rest=j-inputset[i][1]
                choosevalue=graph[i,rest]+inputset[i][0]
                nonchoosevalue=graph[i,j]
                if(choosevalue>nonchoosevalue):
                    graph[i+1,j]=choosevalue
                else:
                    graph[i+1,j]=nonchoosevalue

    print(13)

main()

Submission status: Runtime Error

Solution code:
import numpy as np
def main():
    [N,W]=input().split(" ")
    N=int(N)
    W=int(W)
    inputset=[]
    for i in range(N):
        [vi,wi]=input().split(" ")
        inputset.append([int(vi),int(wi)])

    graph=np.zeros([N+1,W+1])

    '''for i in range(N):
        for j in range(W+1):
            if(inputset[i][1]>j):
                graph[i+1,j]=graph[i,j]
            else:
                rest=j-inputset[i][1]
                choosevalue=graph[i,rest]+inputset[i][0]
                nonchoosevalue=graph[i,j]
                if(choosevalue>nonchoosevalue):
                    graph[i+1,j]=choosevalue
                else:
                    graph[i+1,j]=nonchoosevalue'''

    print(13)

main()

Submission status: Runtime Error

Solution code:
import numpy as np
def main():
    [N,W]=input().split(" ")
    N=int(N)
    W=int(W)
    inputset=[]
    for i in range(N):
        [vi,wi]=input().split(" ")
        inputset.append([int(vi),int(wi)])


    print(13)

main()

Submission status: Runtime Error

Solution code:
import numpy as np
def main():



    print(13)

main()

Submission status: Runtime Error

Solution code:

def main():
    [N,W]=input().split(" ")
    N=int(N)
    W=int(W)
    inputset=[]
    for i in range(N):
        [vi,wi]=input().split(" ")
        inputset.append([int(vi),int(wi)])

    graph=np.zeros([N+1,W+1])

    for i in range(N):
        for j in range(W+1):
            if(inputset[i][1]>j):
                graph[i+1,j]=graph[i,j]
            else:
                rest=j-inputset[i][1]
                choosevalue=graph[i,rest]+inputset[i][0]
                nonchoosevalue=graph[i,j]
                if(choosevalue>nonchoosevalue):
                    graph[i+1,j]=choosevalue
                else:
                    graph[i+1,j]=nonchoosevalue

    print(graph[N,W])

main()

Submission status: Runtime Error

Solution code:
import numpy as np
def main():


    print(13)

main()

Submission status: Runtime Error

Solution code:
import numpy
def main():


    print(13)

main()

Submission status: Runtime Error

Solution code:
import scipy
def main():


    print(13)

main()

Submission status: Runtime Error

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

import numpy as np
#DPテーブル
dp = np.zeros((N+1,W+1))

#初期化
for j in range(W+1):
    dp[0][j] = 0

#DP計算
for i in range(N):
    for w in range(W+1):
        if(w >= wei[i]):
            dp[i+1][w] = max(dp[i][w - wei[i]] + val[i],dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]

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

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
dp = [[0] * W for _ in range(N+1)]
weights = list()
values = list()
for _ in range(N):
    w, v = map(int, input().split())
    weights.append(w)
    values.append(v)

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

print(dp[n][W])

Submission status: Runtime Error

Solution code:
import numpy as np
MAX_N = 100
MAX_W = 10000
dp = np.ones((MAX_N+1, MAX_W+1)) * (-1)

def rec(i, j):
    if dp[i][j] >= 0:
        return dp[i][j]
    if i == n:
        res = 0
    elif  j < vw[i][1]:
        res = rec(i+1, j)
    else:
        res = max(rec(i+1, j), rec(i+1, j-vw[i][1])+vw[i][0])
    dp[i][j] = res
    return res

n, w = (int(s) for s in input().split())
vw = [tuple(int(s) for s in input().split()) for i in range(n)]

print(str(rec(0, w)))

Submission status: Runtime Error

Solution code:
import numpy as np
MAX_N = 100
MAX_W = 10000
dp = np.ones((MAX_N+1, MAX_W+1)) * (-1)

def rec(i, j):
    if dp[i][j] >= 0:
        return dp[i][j]
    if i == n:
        res = 0
    elif  j < vw[i][1]:
        res = rec(i+1, j)
    else:
        res = max(rec(i+1, j), rec(i+1, j-vw[i][1])+vw[i][0])
    dp[i][j] = res
    return res

def solve():
    n, w = (int(s) for s in input().split())
    vw = [tuple(int(s) for s in input().split()) for i in range(n)]
    print(str(rec(0, w)))
    
solve()

Submission status: Runtime Error

Solution code:
MAX_N = 100
MAX_W = 10000
dp =  [[-1 for j in range(MAX_W+1)] for i in range(MAX_N+1)]

def rec(i, j):
    if dp[i][j] >= 0:
        return dp[i][j]
    if i == n:
        res = 0
    elif  j < vw[i][1]:
        res = rec(i+1, j)
    else:
        res = max(rec(i+1, j), rec(i+1, j-vw[i][1])+vw[i][0])
    dp[i][j] = res
    return res

def solve():
    n, w = (int(s) for s in input().split())
    vw = [tuple(int(s) for s in input().split()) for i in range(n)]
    print(str(rec(0, w)))
    
solve()

Submission status: Runtime Error

Solution code:
def rec(i, j):
    if dp[i][j] >= 0:
        return dp[i][j]
    if i == n:
        res = 0
    elif  j < vw[i][1]:
        res = rec(i+1, j)
    else:
        res = max(rec(i+1, j), rec(i+1, j-vw[i][1])+vw[i][0])
    dp[i][j] = res
    return res

def solve():
    n, w = (int(s) for s in input().split())
    vw = list(tuple(int(s) for s in input().split()) for i in range(n))
    print(str(rec(0, w)))

if __name__ == '__main__':
    MAX_N = 100
    MAX_W = 10000
    dp =  list(list(-1 for j in range(MAX_W+1)) for i in range(MAX_N+1))    
    solve()

Submission status: Runtime Error

Solution code:
def rec(i, j):
    if dp[i][j] >= 0:
        return dp[i][j]
    if i == n:
        res = 0
    elif  j < vw[i][1]:
        res = rec(i+1, j)
    else:
        res = max(rec(i+1, j), rec(i+1, j-vw[i][1])+vw[i][0])
    dp[i][j] = res
    return res

def solve():
    n, w = tuple(int(s) for s in input().split())
    vw = list(tuple(int(s) for s in input().split()) for i in range(n))
    print(str(rec(0, w)))

if __name__ == '__main__':
    MAX_N = 100
    MAX_W = 10000
    dp =  list(list(-1 for j in range(MAX_W+1)) for i in range(MAX_N+1))    
    solve()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

def rec(i, j):
    if dp[i][j] >= 0:
        return dp[i][j]
    if i == n:
        res = 0
    elif  j < vw[i][1]:
        res = rec(i+1, j)
    else:
        res = max(rec(i+1, j), rec(i+1, j-vw[i][1])+vw[i][0])
    dp[i][j] = res
    return res

def solve():
    n, w = tuple(int(s) for s in input().split())
    vw = list(tuple(int(s) for s in input().split()) for i in range(n))
    print(str(rec(0, w)))

if __name__ == '__main__':
    MAX_N = 100
    MAX_W = 10000
    dp =  list(list(-1 for j in range(MAX_W+1)) for i in range(MAX_N+1))    
    solve()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

def rec(i, j):
    if dp[i][j] >= 0:
        return dp[i][j]
    if i == n:
        res = 0
    elif  j < vw[i][1]:
        res = rec(i+1, j)
    else:
        res = max(rec(i+1, j), rec(i+1, j-vw[i][1])+vw[i][0])
    dp[i][j] = res
    return res

def solve():
    n, w = tuple(int(s) for s in input().split())
    vw = list(tuple(int(s) for s in input().split()) for i in range(n))
    print(str(rec(0, w)))

if __name__ == '__main__':
    MAX_N = 100
    MAX_W = 10000
    dp =  list(list(-1 for j in range(MAX_W+1)) for i in range(MAX_N+1))    
    solve()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

def rec(i, j):
    if dp[i][j] >= 0:
        return dp[i][j]
    if i == n:
        res = 0
    elif  j < vw[i][1]:
        res = rec(i+1, j)
    else:
        res = max(rec(i+1, j), rec(i+1, j-vw[i][1])+vw[i][0])
    dp[i][j] = res
    return res

def solve():
    n, w = tuple(int(s) for s in input().split())
    vw = list(tuple(int(s) for s in input().split()) for i in range(n))
    print("{}", rec(0, w))

if __name__ == '__main__':
    MAX_N = 100
    MAX_W = 10000
    dp =  list(list(-1 for j in range(MAX_W+1)) for i in range(MAX_N+1))    
    solve()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

MAX_N = 100
MAX_W = 10000
dp =  list(list(-1 for j in range(MAX_W+1)) for i in range(MAX_N+1))    

def rec(i, j):
    if dp[i][j] >= 0:
        return dp[i][j]
    if i == n:
        res = 0
    elif  j < vw[i][1]:
        res = rec(i+1, j)
    else:
        res = max(rec(i+1, j), rec(i+1, j-vw[i][1])+vw[i][0])
    dp[i][j] = res
    return res

def solve():
    n, w = tuple(int(s) for s in input().split())
    vw = list(tuple(int(s) for s in input().split()) for i in range(n))
    print("{}", rec(0, w))

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys
def cv(w, p, vi, wi):
    global value

    w0 = 0
    v0 = 0
    for i in range(len(vi)):
        w0 += wi[i]
        if w0 >= w:def cv(w, p, vi, wi):
    global value
#   print(value)
#   print("{} {} {} {}".format(w, p, vi, wi))

    w0 = 0
    v0 = 0
    for i in range(len(vi)):
        w0 += wi[i]
        if w0 > w:
            if i == len(vi) -1 or v0 + vi[i + 1] <= value - p:
                return max(p + v0, value)
            value = max(value, p + v0)
            break
        v0 += vi[i]
        
    if len(vi) == 1:
        value = max(value, p + vi[0] if wi[0] <= w else p)
        return value
    elif wi[0] <= w:
        value = max(value, p + vi[0])
        return max(cv(w - wi[0], p + vi[0], vi[1:], wi[1:]), cv(w, p, vi[1:], wi[1:]))
    else:
        return cv(w, p, vi[1:], wi[1:])

n, w = map(int, input().split())
c = []
for _ in range(n):
    c.append(tuple(map(int, input().split())))
c.sort(key = lambda x: x[1])
c.sort(key = lambda x: x[0] / x[1], reverse = True)
vi, wi = zip(*c)
value = 0
print(cv(w, 0, vi, wi))
            if i == len(vi) -1 or v0 + vi[i + 1] <= value - p:
                return value
            value = max(value, p + v0)
            break
        v0 += vi[i]
        
    if len(vi) == 1:
        value = max(value, p + vi[0] if wi[0] <= w else p)
        return value
    elif wi[0] <= w:
        value = max(value, p + vi[0])
        return max(cv(w - wi[0], p + vi[0], vi[1:], wi[1:]), cv(w, p, vi[1:], wi[1:]))
    else:
        return cv(w, p, vi[1:], wi[1:])

n, w = map(int, input().split())
c = []
for _ in range(n):
    c.append(tuple(map(int, input().split())))
c.sort(key = lambda x: x[1])
c.sort(key = lambda x: x[0] / x[1], reverse = True)
vi, wi = zip(*c)
value = 0
print(cv(w, 0, vi, wi))

Submission status: Runtime Error

Solution code:
N,W=map(int,input().split())
C=[0]*-~W
for _ in[0]*N:
 v,w=mpa(int,input().split())
 for i in range(W,w-1,-1):
  t=v+C[i-w]
  if t>C[i]:C[j]=t
print(C[W])

Submission status: Runtime Error

Solution code:
N,W=map(int,input().split())
C=[0]*-~W
for _ in[0]*N:
 v,w=map(int,input().split())
 for i in range(W,w-1,-1):
  t=v+C[i-w]
  if t>C[i]:C[j]=t
print(C[W])

Submission status: Runtime Error

Solution code:
import numpy as np

num_line,max_weight = map(int,input().split())
dp = np.zeros([num_line+1,max_weight+1])
fac = []
for i in range(num_line):
    v,w = map(int,input().split())
    fac.append([v,w])

for i in range(1,num_line + 1):
    for j in range(1,max_weight+1):
        if(j >= fac[i-1][1]):
            dp[i][j] = max(dp[i-1][j-fac[i-1][1]]+fac[i-1][0],dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
print(int(dp[num_line][max_weight]))

Submission status: Runtime Error

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

items=[]

for i in range(N):
    items.append(list(map(int,input().split())))
    
dp = [[0 for i in range(100)] for j in range(100)]

for i in range(N):
    dp[i][0]=0
    
for i in range(N):
    for w in range(W+1):
        if w>=items[i][1]:
            dp[i+1][w]=max(dp[i][w-items[i][1]]+items[i][0],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().split())

items=[]

for i in range(N):
    items.append(list(map(int,input().split())))
    
dp = [[0 for i in range(10000)] for j in range(100)]

for i in range(N):
    dp[i][0]=0
    
for i in range(N):
    for w in range(W+1):
        if w>=items[i][1]:
            dp[i+1][w]=max(dp[i][w-items[i][1]]+items[i][0],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().split())

items=[]

for i in range(N):
    items.append(list(map(int,input().split())))
    
dp = [[0 for i in range(10001)] for j in range(100)]

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


print(dp[N][W])

Submission status: Runtime Error

Solution code:
#問題2
#https://qiita.com/drken/items/a5e6fe22863b7992efdb
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=jp
n, w = map(int,input().split())
value = []
weight = []

for i in range(n):
    val,wei = map(int,input().split())
    value.append(val)
    weight.append(wei)
    
#dp i <= 110, w <= 1010
dp = []
for i in range(110):
    o = [0 for i in range(1010)]
    dp.append(o)

#i = 0 何も入れない状態を初期化する

for ww in range(w):
    dp[0][ww] = 0

for i in range(0,n):
    for ww in range(w+1):
        #dp[i+1]に最終状態が格納される
        if ww >= weight[i] :
            dp[i+1][ww] = max(dp[i][ww-weight[i]] + value[i], dp[i][ww])
        else:
            dp[i+1][ww] = dp[i][ww]
print(dp[n][w])

Submission status: Runtime Error

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

dp = [[0]*(N+10) for _ in range(W+10)]
#dp[k][w]はk番目までの荷物を使ってw以内に抑えた時の最大値
#dp[0][_] = dp[_][w] = 0と定義する（荷物は1番目、2番目、・・・、N番目と定義する）

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

Submission status: Runtime Error

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

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

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