Problem p03164 (python)

Fixed submission:
N,Wmax=map(int,input().split(' '))
W=[]
V=[]
for _ in range(N):
	w,v = map(int,input().split(' '))
	W.append(w)
	V.append(v)

Vmax=sum(V)

# dp[i][v]=i番目の品物までだけを選び価値の合計をvとしたときの必要な重量の最小値
# ただしそのような価値の合計が実現不可能なときはNoneを格納

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

dp[0][0] = 0
dp[0][V[0]] = W[0]

for i in range(1,N):
	# 新しく積めるようになる荷物の価値をV[i]とする
	# このとき価値の合計をvにするのに必要な重量の最小値は
	#	  dp[i-1][v-V[i]]+W[i] と
	#   dp[i-1][v] のうち小さいほう
	for v in range(Vmax+1):
		if v-V[i]<0:
			dp[i][v] = dp[i-1][v]
		else:
			if dp[i-1][v] is not None:
				if dp[i-1][v-V[i]] is not None:
					dp[i][v] = min(dp[i-1][v],dp[i-1][v-V[i]]+W[i])
				else:
					dp[i][v] = dp[i-1][v]
			else:
				if dp[i-1][v-V[i]] is not None:
					dp[i][v] = dp[i-1][v-V[i]]+W[i]

ans = 0
for v in range(Vmax+1):
	try:
		ans = v if dp[-1][v]<=Wmax else ans
	except TypeError:
		pass

print(ans)

Buggy submission (verdict: Runtime Error):
N,Wmax=map(int,input().split(' '))
W=[]
V=[]
for _ in range(N):
	w,v = map(int,input().split(' '))
	W.append(w)
	V.append(v)

Vmax=sum(V)

#dp[i][v]=i番目の品物までだけを選び価値の合計をvとしたときの必要な重量の最小値

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

dp[0][V[0]+1] = W[0]

for i in range(1,N):
	#新しく積めるようになる荷物の価値をV[i]とする
	#このとき価値の合計をvにするのに必要な重量の最小値は
	#	dp[i-1][v-V[i]]+W[i] と
	# dp[i-1][v] のうち小さいほう
	for v in range(Vmax+1):
		if v-V[i]<0:
			dp[i][v] = dp[i-1][v]
		else:
			if dp[i-1][v]:
				if dp[i-1][v-V[i]]:
					dp[i][v] = min(dp[i-1][v],dp[i-1][v-V[i]]+W[i])
				else:
					dp[i][v] = dp[i-1][v]
			else:
				if dp[i-1][v-V[i]]:
					dp[i][v] = dp[i-1][v-V[i]]+W[i]

ans = 0
for v in range(Vmax+1):
	try:
		ans = v if dp[-1][v]<=Wmax else ans
	except TypeError:
		pass

print(ans)

Buggy submission (verdict: Runtime Error):
N,Wmax=map(int,input().split(' '))
W=[]
V=[]
for _ in range(N):
	w,v = map(int,input().split(' '))
	W.append(w)
	V.append(v)

Vmax=(10**3)*N

#dp[i][j]=i番目の品物までだけを選び価値の合計をvとしたときの必要な重量の最小値

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

dp[0][V[0]] = W[0]

for i in range(1,N):
	#新しく積めるようになる荷物の価値をV[i]とする
	#このとき価値の合計をvにするのに必要な重量の最小値は
	#	dp[i-1][v-V[i]]+W[i] と
	# dp[i-1][v] のうち小さいほう
	for v in range(Vmax+1):
		if v-V[i]<0:
			dp[i][v] = dp[i-1][v]
		else:
			dp[i][v] = min(dp[i-1][v], dp[i-1][v-V[i]]+W[i])

ans = 0
for v in range(Vmax+1):
	ans = v if dp[-1][v] <= W else ans

print(ans)

Buggy submission (verdict: Runtime Error):
N,Wmax=map(int,input().split(' '))
W=[]
V=[]
for _ in range(N):
	w,v = map(int,input().split(' '))
	W.append(w)
	V.append(v)

big = 5*10**8

#dp[i][j]=i番目の品物までだけを選び重量制限をjとしたときの価値の最大値
dp_small = [0]*(min(Wmax+1,big+1))
for i in range(len(dp_small)):
	if i >= W[0]:
		dp_small[i] = V[0]

#dp_large[0] = dp_small[-1]
dp_large = []
dp_large.append(dp_small[-1])
for i in range(max(0,Wmax-big)):
	if i+big >= W[0]:
		dp_large[i] = V[0]


for i in range(1,N):
	#今回の重量制限をwとする
	#今回は荷物を積む場合: dp[i][w] = dp[i-1][w-w[i]]+v[i] 
	#今回は荷物を積まない場合: dp[i][w] = dp[i-1][w]
	#よってこの2つのうち大きいほうをdp[i][w]に採用する
	dp_small_new = []
	dp_large_new = []
	for j in range(Wmax+1):
		if j<=big:
			if j<W[i]:
				dp_small_new.append(dp_small[j])
			else:
				dp_small_new.append(max(dp_small[j], dp_small[j-W[i]]+V[i]))
			if j==big:
				dp_large_new.append(dp_small_new[-1])
		else:
			if j<W[i]:
				dp_large_new.append(dp_large[j])
			elif j-W[i]<=big:
				dp_large_new.append(max(dp_large[j], dp_small[j-W[i]]+V[i]))
			else:
				dp_large_new.append(max(dp_large[j], dp_large[j-W[i]-big]+V[i]))
	dp_small = dp_small_new
	dp_large = dp_large_new
print(dp_small[Wmax]) if Wmax<=big else print(dp_large[Wmax-big])

Buggy submission (verdict: Runtime Error):
N,Wmax=map(int,input().split(' '))
W=[]
V=[]
for _ in range(N):
	w,v = map(int,input().split(' '))
	W.append(w)
	V.append(v)

#dp[i][j]=i番目の品物までだけを選び重量制限をjとしたときの価値の最大値
dp_last = [0]*(Wmax+1)
for i in range(Wmax+1):
	if i >= W[0]:
		dp_last[i] = V[0]

for i in range(1,N):
	#今回の重量制限をwとする
	#今回は荷物を積む場合: dp[i][w] = dp[i-1][w-w[i]]+v[i] 
	#今回は荷物を積まない場合: dp[i][w] = dp[i-1][w]
	#よってこの2つのうち大きいほうをdp[i][w]に採用する
	dp = []
	for j in range(Wmax+1):
		if j<W[i]:
			dp.append(dp_last[j])
		else:
			dp.append(max(dp_last[j], dp_last[j-W[i]]+V[i]))
	dp_last = dp
print(dp[Wmax])

Buggy submission (verdict: Runtime Error):
N,Wmax=map(int,input().split(' '))
W=[]
V=[]
for _ in range(N):
	w,v = map(int,input().split(' '))
	W.append(w)
	V.append(v)

#dp[i][j]=i番目の品物までだけを選び重量制限をjとしたときの価値の最大値
dp_last = []
dp_last.append([0]*min(W[0],Wmax+1)+ [V[0]]*max(0, Wmax+1-W[0]))


for i in range(1,N):
	#今回の重量制限をwとする
	#今回は荷物を積む場合: dp[i][w] = dp[i-1][w-w[i]]+v[i] 
	#今回は荷物を積まない場合: dp[i][w] = dp[i-1][w]
	#よってこの2つのうち大きいほうをdp[i][w]に採用する
	dp = []
	for j in range(Wmax+1):
		if j<W[i]:
			dp.append(dp_last[j])
		else:
			dp.append(max(dp_last[j], dp_last[j-W[i]]+V[i]))
	dp_last = dp
print(dp[Wmax])

Buggy submission (verdict: Runtime Error):
N,Wmax=map(int,input().split(' '))
W=[]
V=[]
for _ in range(N):
	w,v = map(int,input().split(' '))
	W.append(w)
	V.append(v)

#dp[i][j]=i番目の品物までだけを選び重量制限をjとしたときの価値の最大値
dp = []
dp.append([0]*min(W[0],Wmax+1)+ [V[0]]*max(0, Wmax+1-W[0]))


for i in range(1,N):
	#今回の重量制限をwとする
	#今回は荷物を積む場合: dp[i][w] = dp[i-1][w-w[i]]+v[i] 
	#今回は荷物を積まない場合: dp[i][w] = dp[i-1][w]
	#よってこの2つのうち大きいほうをdp[i][w]に採用する
	dpi = []
	for j in range(Wmax+1):
		if j<W[i]:
			dpi.append(dp[i-1][j])
		else:
			dpi.append(max(dp[i-1][j], dp[i-1][j-W[i]]+V[i]))
	dp.append(dpi)
print(dp[N-1][Wmax])