Problem p03164 (python)

Fixed submission:
N,W=map(int,input().split())
w=[]
v=[]
maxV=0
for i in range(N):
    a,b=map(int,input().split())
    if maxV<b:
        maxV=b
    w.append(a)
    v.append(b)
#dp[n個目のアイテムまでで][V以上を達成する]=最小のw
#dp[0][v]=inf ゼロ個でｖは無理なので
#dp[0][0]=0と初期化する
#だからiの時dp[i][v]=min(dp[i-1][v],dp[i-1][V-v[i-1]]+w[i])である<-i-1なのはvとかにはゼロ個とかないので
#V-v[i]<0ならば、とれないので前者になるね！！
#これをi=0(は初期化でする)->nまでおこない、各iについてはとりうる最大のValueを考えるが
#これは最大で各アイテムについて最大のVがあってこれにアイテム数Nを掛けたものである
#つまりdpのサイズはdp[0->N][0->maxV*N]をとればよい

dp=[[float("inf") for i in range(maxV*(N+1))] for j in range(N+1)]
dp[0][0]=0

for i in range(1,N+1):
    for val in range(maxV*N+1):
        tmp1=dp[i-1][val]#とらない
        if val-v[i-1]<0:#この時、iこめの価値がおおきいので、これをとるだけで達成してしまう
            tmp2=w[i-1]#i=1の時、dp[0][val]=inf
        else:#i=1の時val-v[0]>0で無限になるので
            tmp2=dp[i-1][val-v[i-1]]+w[i-1]#
        res=min(tmp1,tmp2)
        dp[i][val]=res
#ここでW以下となるvalの最大値をたんさくする
max=0
for value in range(len(dp[N])):
    if dp[N][value]<=W:
        if value>max:
            max=value
print(max)

Buggy submission (verdict: Runtime Error):
import numpy as np
N,W=map(int,input().split())
w=[]
v=[]
maxV=0
for i in range(N):
    a,b=map(int,input().split())
    if maxV<b:
        maxV=b
    w.append(a)
    v.append(b)
w=np.array(w)
v=np.array(v)
#dp[n個目のアイテムまでで][V以上を達成する]=最小のw
#dp[0][v]=inf ゼロ個でｖは無理なので
#dp[0][0]=0と初期化する
#だからiの時dp[i][v]=min(dp[i-1][v],dp[i-1][V-v[i-1]]+w[i])である<-i-1なのはvとかにはゼロ個とかないので
#V-v[i]<0ならば、とれないので前者になるね！！
#これをi=0(は初期化でする)->nまでおこない、各iについてはとりうる最大のValueを考えるが
#これは最大で各アイテムについて最大のVがあってこれにアイテム数Nを掛けたものである
#つまりdpのサイズはdp[0->N][0->maxV*N]をとればよい

dp=[[float("inf") for i in range(maxV*(N+1))] for j in range(N+1)]
dp[0][0]=0

for i in range(1,N+1):
    for val in range(maxV*N+1):
        tmp1=dp[i-1][val]#とらない
        if val-v[i-1]<0:#この時、iこめの価値がおおきいので、これをとるだけで達成してしまう
            tmp2=w[i-1]#i=1の時、dp[0][val]=inf
        else:#i=1の時val-v[0]>0で無限になるので
            tmp2=dp[i-1][val-v[i-1]]+w[i-1]#
        res=min(tmp1,tmp2)
        dp[i][val]=res
#ここでW以下となるvalの最大値をたんさくする
max=0
for value in range(len(dp[N])):
    if dp[N][value]<=W:
        if value>max:
            max=value
print(max)

Buggy submission (verdict: Runtime Error):
import numpy as np
N,W=map(int,input().split())
w=[]
v=[]
maxV=0
for i in range(N):
    a,b=map(int,input().split())
    if maxV<b:
        maxV=b
    w.append(a)
    v.append(b)
w=np.array(w)
v=np.array(v)
#dp[n個目のアイテムまでで][V以上を達成する]=最小のw
#dp[0][v]=inf ゼロ個でｖは無理なので
#dp[0][0]=0と初期化する
#だからiの時dp[i][v]=min(dp[i-1][v],dp[i-1][V-v[i-1]]+w[i])である<-i-1なのはvとかにはゼロ個とかないので
#V-v[i]<0ならば、とれないので前者になるね！！
#これをi=0(は初期化でする)->nまでおこない、各iについてはとりうる最大のValueを考えるが
#これは最大で各アイテムについて最大のVがあってこれにアイテム数Nを掛けたものである
#つまりdpのサイズはdp[0->N][0->maxV*N]をとればよい

dp=[[float("inf") for i in range(maxV*(N+1))] for j in range(N+1)]
dp[0][0]=0

for i in range(1,N+1):
    for val in range(maxV*N+1):
        tmp1=dp[i-1][val]#とらない
        if val-v[i-1]<0:#この時、iこめの価値がおおきいので、これをとるだけで達成してしまう
            tmp2=w[i-1]#i=1の時、dp[0][val]=inf
        else:#i=1の時val-v[0]>0で無限になるので
            tmp2=dp[i-1][val-v[i-1]]+w[i-1]#
        res=min(tmp1,tmp2)
        dp[i][val]=res
#ここでW以下となるvalの最大値をたんさくする
max=0
for value in range(len(dp[N])):
    if dp[N][value]<=W:
        if value>max:
            max=value
print(max)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(900000000)
def knap(n,w,weight,value,dp):
    #print(n,":",w,":",len(dp),":",len(dp[n]))
    x=dp[n][w]
    if x!=-1:
        return x
    if n==0:
        dp[n][w]=0
        return 0
    if w==0:
        dp[n][w]=0
        return 0
    if w-weight[n-1]<0:
        tmp2=knap(n-1,w,weight,value,dp)
        dp[n][w]=tmp2
        return tmp2
    tmp1=knap(n-1,w-weight[n-1],weight,value,dp)+value[n-1]
    tmp2=knap(n-1,w,weight,value,dp)
    if tmp1>=tmp2:
        dp[n][w]=tmp1
        return tmp1
    else:
        dp[n][w]=tmp2
        return tmp2  
def main():
    n,W=map(int,input().split())
    weight=[]
    value=[]
    for i in range(n):
        a,b=map(int,input().split())
        weight.append(a)
        value.append(b)
    dp=[[-1]*(W+1)]*(n+1)
    print(knap(n,W,weight,value,dp))
    return 0
main()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(900000000)
def knap(n,w,weight,value,dp):
  #  print(n,":",w,":",len(dp),":",len(dp[n]))
    if dp[n][w]!=-1:
        return dp[n][w]
    if n==0:
        dp[n][w]=0
        return 0
    if w==0:
        dp[n][w]=0
        return 0
    if w-weight[n]<0:
        tmp2=knap(n-1,w,weight,value,dp)
        dp[n][w]=tmp2
        return tmp2
    tmp1=knap(n-1,w-weight[n],weight,value,dp)+value[n]
    tmp2=knap(n-1,w,weight,value,dp)
    if tmp1>=tmp2:
        dp[n][w]=tmp1
        return tmp1
    else:
        dp[n][w]=tmp2
        return tmp2
        

n,W=map(int,input().split())
weight=[0]
value=[0]
for i in range(n):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
dp=[[-1]*(W+1)]*(n+1)
print(knap(n,W,weight,value,dp))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(900000000)
def knap(n,w,weight,value,dp):
  #  print(n,":",w,":",len(dp),":",len(dp[n]))
    if dp[n][w]!=-1:
        return dp[n][w]
    if n==0:
        dp[n][w]=0
        return 0
    if w==0:
        dp[n][w]=0
        return 0
    if w-weight[n]<0:
        tmp2=knap(n-1,w,weight,value,dp)
        dp[n][w]=tmp2
        return tmp2
    tmp1=knap(n-1,w-weight[n],weight,value,dp)+value[n]
    tmp2=knap(n-1,w,weight,value,dp)
    if tmp1>=tmp2:
        dp[n][w]=tmp1
        return tmp1
    else:
        dp[n][w]=tmp2
        return tmp2
        

n,W=map(int,input().split())
weight=[0]
value=[0]
for i in range(n):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
dp=[[-1]*(W+1)]*(n+1)
print(knap(n,W,weight,value,dp))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(4000000000000)
def knap(n,w,weight,value,dp):
  #  print(n,":",w,":",len(dp),":",len(dp[n]))
    if dp[n][w]!=-1:
        return dp[n][w]
    if n==0:
        dp[n][w]=0
        return 0
    if w==0:
        dp[n][w]=0
        return 0
    if w-weight[n]<0:
        tmp2=knap(n-1,w,weight,value,dp)
        dp[n][w]=tmp2
        return tmp2
    tmp1=knap(n-1,w-weight[n],weight,value,dp)+value[n]
    tmp2=knap(n-1,w,weight,value,dp)
    if tmp1>tmp2:
        dp[n][w]=tmp1
        return tmp1
    else:
        dp[n][w]=tmp2
        return tmp2
        

n,W=map(int,input().split())
weight=[0]
value=[0]
for i in range(n):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
dp=[[-1]*(W+1)]*(n+1)
print(knap(n,W,weight,value,dp))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(40000000)
def knap(n,w,weight,value,dp):
  #  print(n,":",w,":",len(dp),":",len(dp[n]))
    if dp[n][w]!=-1:
        return dp[n][w]
    if n==0:
        dp[n][w]=0
        return 0
    if w==0:
        dp[n][w]=0
        return 0
    if w-weight[n]<0:
        tmp2=knap(n-1,w,weight,value,dp)
        dp[n][w]=tmp2
        return tmp2
    tmp1=knap(n-1,w-weight[n],weight,value,dp)+value[n]
    tmp2=knap(n-1,w,weight,value,dp)
    if tmp1>tmp2:
        dp[n][w]=tmp1
        return tmp1
    else:
        dp[n][w]=tmp2
        return tmp2
        

n,W=map(int,input().split())
weight=[0]
value=[0]
for i in range(n):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
dp=[[-1]*(W+1)]*(n+1)
print(knap(n,W,weight,value,dp))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit("4000000")
def knap(n,w,weight,value,dp):
  #  print(n,":",w,":",len(dp),":",len(dp[n]))
    if dp[n][w]!=-1:
        return dp[n][w]
    if n==0:
        dp[n][w]=0
        return 0
    if w==0:
        dp[n][w]=0
        return 0
    if w-weight[n]<0:
        tmp2=knap(n-1,w,weight,value,dp)
        dp[n][w]=tmp2
        return tmp2
    tmp1=knap(n-1,w-weight[n],weight,value,dp)+value[n]
    tmp2=knap(n-1,w,weight,value,dp)
    if tmp1>tmp2:
        dp[n][w]=tmp1
        return tmp1
    else:
        dp[n][w]=tmp2
        return tmp2
        

n,W=map(int,input().split())
weight=[0]
value=[0]
for i in range(n):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
dp=[[-1]*(W+1)]*(n+1)
print(knap(n,W,weight,value,dp))

Buggy submission (verdict: Runtime Error):
def knap(n,w,weight,value,dp):
  #  print(n,":",w,":",len(dp),":",len(dp[n]))
    if dp[n][w]!=-1:
        return dp[n][w]
    if n==0:
        dp[n][w]=0
        return 0
    if w==0:
        dp[n][w]=0
        return 0
    if w-weight[n]<0:
        tmp2=knap(n-1,w,weight,value,dp)
        dp[n][w]=tmp2
        return tmp2
    tmp1=knap(n-1,w-weight[n],weight,value,dp)+value[n]
    tmp2=knap(n-1,w,weight,value,dp)
    if tmp1>tmp2:
        dp[n][w]=tmp1
        return tmp1
    else:
        dp[n][w]=tmp2
        return tmp2
        

n,W=map(int,input().split())
weight=[0]
value=[0]
for i in range(n):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
dp=[[-1]*(W+1)]*(n+1)
print(knap(n,W,weight,value,dp))