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^9

1 \leq w_i \leq W

1 \leq v_i \leq 10^3

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

1 1000000000
1000000000 10

Sample Output 2

10

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: Wrong Answer

Solution code:
INFTY = 10**16

def rec(depth, w, v):
    if WV[depth][v] != INFTY:
        return WV[depth][v]
    if depth+1 >= N+1:
        WV[depth][v] = w
        return WV[depth][v]
    if w + W[depth+1] <= maxW:
        WV[depth][v+V[depth+1]] = rec(depth+1, w+W[depth+1], v+V[depth+1])
        WV[depth][v] = rec(depth+1, w, v)
        return min(WV[depth][v+V[depth+1]], WV[depth][v])
    else:
        WV[depth][v] = rec(depth+1, w, v)
        
        return WV[depth][v]

N, maxW = map(int, input().split())
WV = [[INFTY for i in range(10**5+1)] for j in range(N+1)]
W = [0 for i in range(N+1)]
V = [0 for i in range(N+1)]
for i in range(1, N+1):
    W[i], V[i] = map(int, input().split())

rec(0, 0, 0)

for i in range(10**5, -1, -1):
    if WV[-1][i] != INFTY:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
weight = []
value = []
for _ in range(N):
    w_tmp, v_tmp = map(int, input().split())
    weight.append(w_tmp)
    value.append(v_tmp)

INF = float('inf')

dp = [[INF for i in range(sum(value)+1)] for j in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for j in range(sum(value)+1):
        if j - value[i] >= 0:
            dp[i+1][j] = min(dp[i][j - value[i]] + weight[i], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

for j in range(sum(value)+1):
    if dp[N][j] <= W:
        res = j

Submission status: Wrong Answer

Solution code:
n, weightMax = map(int, input().split())
itemList = [[0 for _ in range(100**3+1)] for _ in range(n+1)]

for i in range(n):
    w,v = list(map(int, input().split()))
    for j in range(100**3+1):
        if j-v >= 0:
            itemList[i+1][j] = max([itemList[i][j],itemList[i][j-v] + w])
        else:
            itemList[i+1][j] = itemList[i][j]
for i in range(100**3+1):
    if itemList[n][i]==weightMax+1:
        print(i-1)
        break

Submission status: Wrong Answer

Solution code:
n, weightMax = map(int, input().split())
itemList = [[0 for _ in range(100**3+1)] for _ in range(n+1)]

for i in range(n):
    w,v = list(map(int, input().split()))
    for j in range(100**3+1):
        if j-v >= 0:
            itemList[i+1][j] = max([itemList[i][j],itemList[i][j-v] + w])
        else:
            itemList[i+1][j] = itemList[i][j]
for i in range(100**3+1):
    if itemList[n][i]==weightMax:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
WS = []
VS = []
for _ in range(0,N):
    w,v = map(int, input().split())
    WS.append(w)
    VS.append(v)

NAN = 1000000000000 
V_MAX = 10000
dp = [NAN] * (V_MAX+1)
dp[0] = 0

for i in range(0,N):
    w = WS[i]
    v = VS[i]
    for j in reversed(range(0,V_MAX+1)):
        if dp[j] != NAN and j+v < V_MAX+1:
            dp[j+v] = min(dp[j+v], dp[j]+w)

for v in reversed(range(0,V_MAX+1)):
    w = dp[v]
    if w <= W:
        print(v)
        exit(0)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
WS = []
VS = []
for _ in range(0,N):
    w,v = map(int, input().split())
    WS.append(w)
    VS.append(v)

NAN = float('inf')
V_MAX = 10000
dp = [NAN] * (V_MAX+1)
dp[0] = 0

for i in range(0,N):
    w = WS[i]
    v = VS[i]
    for j in reversed(range(0,V_MAX+1)):
        if dp[j] != NAN and j+v < V_MAX+1:
            dp[j+v] = min(dp[j+v], dp[j]+w)

for v in reversed(range(0,V_MAX+1)):
    w = dp[v]
    if w <= W:
        print(v)
        exit(0)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
WS = []
VS = []
for _ in range(0,N):
    w,v = map(int, input().split())
    WS.append(w)
    VS.append(v)

NAN = 1000000000000000 # >10^12
V_MAX = 10000
dp = [NAN] * (V_MAX+1)
dp[0] = 0

for i in range(0,N):
    w = WS[i]
    v = VS[i]
    for j in reversed(range(0,V_MAX+1)):
        if dp[j] != NAN and j+v < (V_MAX+1):
            dp[j+v] = min(dp[j+v], dp[j]+w)

for v in reversed(range(0,V_MAX+1)):
    w = dp[v]
    if w != NAN and w <= W:
        print(v)
        exit(0)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
w = [list(map(int,input().split())) for i in range(n)]
#print(n,k,w)
#w[i][0]は重さ、w[i][1]が価値

l = [[0]*100100 for i in range(n)]
#print(l)

l[0][w[0][1]] = w[0][0]
for i in range(1,n):
  weight = w[i][0]
  value = w[i][1]
  #print(weight,value)
  for j in range(100100):
    new_w = l[i-1][j - value] + weight
    if l[i-1][j - value] == 0:
      if l[i-1][j] == 0 and j - value == 0:
        l[i][j] = new_w
      else:
        l[i][j] = l[i-1][j]
    else:
      if l[i-1][j] != 0:
        l[i][j] = min(new_w,l[i-1][j])
      else:
        l[i][j] = new_w
#print(l[2][140])

ans = 0
for i in range(100100):
  if l[n-1][i] <= k and 0 < l[n-1][i]:
    if ans < i:
      ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
N, W = [int(i) for i in input().split()]
w, v = [0]*N, [0]*N
 
for i in range(N):
  w[i], v[i] = [int(_) for _ in input().split()]
V = sum(v)
 
dp = [[float('inf')] * (V+1) for _ in range(N+1)]
# dp[i][j] i番目までの荷物で価値がj以上になるように選んだときの重さの最小値
dp[0][0] = 0
for i in range(N):
  for j in range(V+1):
    if v[i] <= j:# 荷物v[i]の価値がjに足りてないのでi番目の荷物を入れる可能性がある
      dp[i+1][j] = min(dp[i+1][j], dp[i][j-v[i]] + w[i])
    else:      
      dp[i+1][j] = dp[i][j]
 
ans = 0
for j in range(V + 1):
  if dp[N][j] <= W:
    ans = j    
      
print(ans)

Submission status: Wrong Answer

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

vals = []
for i in range(n):
  vals.append(list(map(int , input().split())))
  
dp = [[0]*2 for i in range(W+1)]
print(W)

Submission status: Wrong Answer

Solution code:
n, W = map(int, input().split(' '))
ws = [0] * (n+1)
vs = [0] * (n+1)
for i in range(1, n+1):
	ws[i], vs[i] = map(int, input().split(' '))

# dp[合計価値] = 合計重さ
sumVs = sum(vs)
dp = [W+1] * (sumVs + 1)	# 存在しない価値には重さのペナルティをつける
dp[0] = 0

maxV = 0	# 有効価値範囲
tmpV = 0 # 一時計算範囲

# 品物で回す
for w, v in zip(ws, vs):
	tmpV = maxV + v
	if(maxV < v):
		maxV = v

	# 価値で回す
	for i in range(tmpV+1):
		dp[i] = min(dp[i], dp[i-v] + w)
		# 価値範囲を広げるか判定
		if(dp[i] <= W):
			maxV = max(maxV, i)

# 制限荷重内の最大合計価値を求める
for i in range(sumVs, 0, -1):
	if(dp[i] <= W):
		print(i)
		break

Submission status: Wrong Answer

Solution code:
n, W = map(int, input().split(' '))
ws = [0] * (n+1)
vs = [0] * (n+1)
for i in range(1, n+1):
	ws[i], vs[i] = map(int, input().split(' '))

# dp[合計価値] = 合計重さ
sumVs = sum(vs)
dp = [W+1] * (sumVs + 1)	# 存在しない価値には重さのペナルティをつける
dp[0] = 0

maxV = 0	# 有効価値範囲
tmpV = 0 # 一時計算範囲

# 品物で回す
for w, v in zip(ws, vs):
	tmpV = maxV + v
	if(maxV < v):
		maxV = v

	# 価値で回す
	for i in range(tmpV+1):
		dp[i] = min(dp[i], dp[i-v] + w)
		# 価値範囲を広げるか判定
		if(dp[i] <= W):
			maxV = i

# 制限荷重内の最大合計価値を求める
for i in range(sumVs, 0, -1):
	if(dp[i] <= W):
		print(i)
		break

Submission status: Wrong Answer

Solution code:
import sys
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())

n = N*max(v)
inf = 10**14

dp = [[inf]*n for i in range(N+1)]
dp[0][0] = 0

for i in range(N):
    dp[i+1][0] = 0
    for j in range(n-2,0,-1):
        dp[i+1][j] = min(dp[i+1][j+1], dp[i][j])
        if v[i] <= j:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j-v[i]]+w[i])

ans = 0
for i in range(n):
    if dp[N][i] <= W:
        ans = i
    else:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
# dp[i][w_sum]: i番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値

N,W=map(int,input().split())
items=[tuple(map(int,input().split())) for i in range(N)]
items.insert(0, (0,0))

v_max=sum([x[1] for x in items])

dp=[[10**13 for _ in range(v_max+1)] for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(v_max+1):
        # take item
        if j-items[i][1]>=0:
            dp[i][j]=dp[i-1][j-items[i][1]]+items[i][0]
        
        dp[i][j]=min(dp[i][j],dp[i-1][j])

ans=0
for i in range(v_max+1):
    if dp[N][i]<=W:
        ans=i

print(ans)

Submission status: Wrong Answer

Solution code:
n,W=map(int,input().split())
MAX_V=10**5

weight=[]
value=[]

for i in range(n):
    w,v=map(int,input().split())
    weight.append(w)
    value.append(v)

dp=[[float('inf') for i in range(MAX_V)] for j in range(n+1)]
dp[0][0]=0
for i in range(n):
    sum_v=0
    while sum_v<MAX_V:
        if sum_v-value[i]>=0:
            dp[i+1][sum_v]=min(dp[i+1][sum_v],dp[i][sum_v-value[i]]+weight[i])
        dp[i+1][sum_v]=min(dp[i+1][sum_v],dp[i][sum_v])
        sum_v+=1
sum_v=0
while sum_v<MAX_V:
    if dp[n][sum_v]<=W:res=sum_v
    sum_v+=1

print(res)

# copy

Submission status: Wrong Answer

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

V = sum(v)
dp = [[float("inf")] * (V + 1) for _ in range(N + 1)]
"""
for j in range(V + 1):
	dp[0][j] = 0
"""
dp[0][0] = 0
# dp[i][j]:i番目までの品物から価値がj以上になるよう選んだときの重さの総和の最小値
for i in range(N):
	for j in range(V + 1):
		# i+1番目を選ぶ場合
		if j - v[i] >= 0:
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v[i]] + w[i])
		# i+1番目を選ばない場合
		dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

# print(dp)

# dp[N][j]がW以下であるようなjの最大値が答えになる
ans = 0
for j in range(V):
	if dp[N][j] <= W:
		ans = j

print(ans)

Submission status: Wrong Answer

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

V = sum(v)
dp = [[0] * (V + 1) for _ in range(N + 1)]
# dp[i][j]:i番目までの品物から価値がV以上になるよう選んだときの重さの総和の最小値
for i in range(N):
	for j in range(V + 1):
		# i+1番目を選ぶ場合
		if j - v[i] >= 0:
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v[i]] - w[i])
		# i+1番目を選ばない場合
		dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

# dp[N][V]がW以下であるようなVの最大値が答えになる
ans = 0
for k in range(V + 1):
	if dp[N][k] <= W:
		ans = max(ans, k)
print(ans)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
wv = [[int(_) for _ in input().split()] for _ in range(N)]
dp = [[float('inf')]*(10**5+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(1, N+1):
    weight = wv[i-1][0]
    value = wv[i-1][1]
    for j in range(10**5+1):
        if j < value:
            dp[i][j] = min(dp[i-1][j], weight)
        else:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-value] + weight)

for i in range(10**5+1):
    if dp[N][i] > W:
        break

print(i-1)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
items = []
for _ in range(N):
    items.append(tuple(map(int, input().split())))
MAX_V = sum([v for _, v in items])
dp = [[0 for j in range(MAX_V+1)] for i in range(N+1)]
for i in range(1, N+1):
    w, v = items[i-1]
    for j in range(MAX_V+1):
        if j - v >= 0:
            dp[i][j] = min(dp[i-1][j-v] + w, dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
for v in range(MAX_V, -1, -1):
    if dp[N][v] <= W:
        break
print(v)

Submission status: Wrong Answer

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

import math
INF = 10 ** 6 # math.inf
V = 10 ** 5 + 10

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

for i, (w, v) in enumerate(WV):
	for n in range(V):
		if v <= n:
			dp[i + 1][n] = min(dp[i + 1][n], dp[i][n - v] + w)
		dp[i + 1][n] = min(dp[i + 1][n], dp[i][n])
"""
for line in dp:
	for cell in line:
		if cell == INF:
			print("  INF", end="")
		else:
			print("{:5d}".format(cell), end="")
	print()
"""
r = 0
for i in range(V):
	if dp[-1][i] <= W:
		r = i
print(r)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
n, max_w = map(int, input().split())

w = []
v = []
for i in range(n):
    _w, _v = map(int, input().split())
    w.append(_w)
    v.append(_v)

total_v = sum(v)


INF = 10 ** 9 + 1
dp = [[INF] * (total_v + 1) for i in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    for j in range(total_v):
        if j >= v[i]:
            dp[i + 1][j] = min(dp[i][j - v[i]] + w[i], dp[i + 1][j])
        dp[i + 1][j] = min(dp[i][j], dp[i + 1][j])

for j in range(total_v, -1, -1):
    if dp[n][j] <= max_w:
        ans = j
        break

print(ans)

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
w=[]
v=[]
for i in range(N):
    w_,v_=map(int,input().split())
    w.append(w_)
    v.append(v_)
INF=10**9
dp=[[10**9]*(10**5+1) for i in range(N+1)]#dp[i+1][j] i個目までで価値jのときの最小の価値
#dp[i+1][v]:=min(dp[i][v-vi]+wi,dp[i][v])加えるか加えないか
dp[0][0]=0
for i in range(N):
    for j in range(10**5+1):
        if j-v[i]>=0:
            dp[i+1][j]=min(dp[i][j-v[i]]+w[i],dp[i+1][j])
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])
for j in range(10**5,-1,-1):
    if dp[N][j]<=W:
        ans=j
        break
print(ans)

Submission status: Wrong Answer

Solution code:
N, W = map(int,input().split())
wl = [0]*N
vl = [0]*N
for i in range(N):
    wl[i], vl[i] = map(int,input().split())

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

for i in range(N):
    w = wl[i]
    v = vl[i]
    for j in range(len(dp[i])):
        if j - v >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j-v]+w)

        dp[i+1][j] = min(dp[i+1][j], dp[i][j])


ans = 0
for i in range(len(dp[i])):
    if dp[N][i] <= W:
        ans = i

print(ans)

Submission status: Wrong Answer

Solution code:
N, W = map(int,input().split())
wl = [0]*N
vl = [0]*N
for i in range(N):
    wl[i], vl[i] = map(int,input().split())

INF = 10**14
dp = [[INF]*(N*max(vl)) for i in range(N+1)]
dp[0][0] = 0

for i in range(N):
    w = wl[i]
    v = vl[i]
    for j in range(len(dp[i])):
        if j - v >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j-v]+w)

        dp[i+1][j] = min(dp[i+1][j], dp[i][j])


ans = 0
for i in range(len(dp[i])):
    if dp[N][i] <= W:
        ans = i

print(ans)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]
dp = [10**12]*(1+10**5)
dp[0] = 0
for i in range(N):
    w,v = WV[i]
    for j in range(len(dp)-1, 0, -1):
        if j-v<=0:
            tmp = w
        else:
            tmp = dp[j-v] + w
        dp[j] = min(dp[j], tmp)
for v,w in enumerate(dp):
    if w>W:
        break
print(v-1)

Submission status: Wrong Answer

Solution code:
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]] = 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]

print(dp)

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

print(ans)

Submission status: Wrong Answer

Solution code:
def e():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(N)]
    v = [wv[i][1] for i in range(len(wv))]
    V = sum(v)
    dp = [[0] * (V + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(V + 1):
            if j <= W:
                if j - wv[i][0] >= 0:
                    dp[i + 1][j] = max(dp[i + 1][j],
                                       dp[i][j - wv[i][0]] + wv[i][1])
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
    return max(dp[i+1][:])


if __name__ == '__main__':
    ans = e()
    print(ans)

Submission status: Wrong Answer

Solution code:
def e():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(N)]
    v = [wv[i][1] for i in range(len(wv))]
    V = sum(v)
    dp = [[0] * (V + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(V + 1):
            if j <= W:
                if j - wv[i][0] >= 0:
                    dp[i + 1][j] = max(dp[i + 1][j],
                                       dp[i][j - wv[i][0]] + wv[i][1])
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
    return dp[-1][-1]


if __name__ == '__main__':
    ans = e()
    print(ans)

Submission status: Wrong Answer

Solution code:
def e():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(N)]
    v = [wv[i][1] for i in range(len(wv))]
    V = sum(v)
    dp = [[0] * (V + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(V + 1):
            if j <= W:
                if j - wv[i][0] >= 0:
                    dp[i + 1][j] = max(dp[i + 1][j],
                                       dp[i][j - wv[i][0]] + wv[i][1])
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
    return dp


if __name__ == '__main__':
    ans = e()
    print(ans)

Submission status: Wrong Answer

Solution code:
dp1=[None]*100001
dp2=[None]*100001
dp2[0]=0
n,W=map(int,input().split())
for i in range(n):
    w,v=map(int,input().split())
    for i in range(v,100001):
        if(dp2[i-v]!=None):
            if(dp2[i]==None):
                dp1[i]=dp2[i-v]+w
            else:
                dp1[i]=min(dp2[i],dp2[i-v]+w)
    dp2=list(dp1)
for i in range(100000,-1,-1):
    if(dp2[i]!=None and dp2[i]<=W):
        print(i)
        break
# 3 8
# 3 3
# 4 5
# 5 6

Submission status: Wrong Answer

Solution code:
def sub():
    N, W = [int(e) for e in input().split()]
    ww = []
    vv = []
    for _ in range(N):
        w, v = [int(e) for e in input().split()]
        ww.append(w)
        vv.append(v)
    
    V = sum(vv)
    INF = v * 10
    dp_table = [[INF for _ in range(V+1)] for _ in range(N+1)]
    dp_table[0][0] = 0
    for i in range(N):
        for j in range(V):
            v_next = vv[i] + j
            w_next = ww[i]
            d = dp_table[i][j]
            if v_next <= V:
                dp_table[i+1][v_next] = min(dp_table[i+1][v_next], d + w_next)
            dp_table[i+1][j] = min(dp_table[i+1][j], d)
    
    # for r in dp_table:
    #     print(r)
    idxx = [i for i, w in enumerate(dp_table[-1]) if w <= W]
    print(idxx[-1])
sub()

Submission status: Wrong Answer

Solution code:
import sys
rr = lambda: sys.stdin.readline().strip()
ri = lambda: int(rr())
rs = lambda: [int(_) for _ in rr().split()]

N, W = rs()
d = [rs() for _ in range(N)]

V = 10**3 + 1
dp = [[W+1 for _ in range(N)] for __ in range(V)]

dp[0][0] = 0
dp[d[0][1]][0] = d[0][0]

for i in range(1, N):
    for v in range(V):
        if v-d[i][1] >= 0:
            dp[v][i] = min(dp[v][i-1], dp[v-d[i][1]][i-1]+d[i][0])
        else:
            dp[v][i] = dp[v][i-1]
        
for v in range(V-1, -1, -1):
    if [d for d in dp[v] if d <= W]:
        print(v)
        sys.exit()
print(0)

Submission status: Wrong Answer

Solution code:
import sys
rr = lambda: sys.stdin.readline().strip()
ri = lambda: int(rr())
rs = lambda: [int(_) for _ in rr().split()]

N, W = rs()
d = [rs() for _ in range(N)]

V = 10**3 + 1
dp = [[W+1 for _ in range(N)] for __ in range(V)]

for i in range(N):
    dp[0][i] = 0

for i in range(N):
    for v in range(V):
        if v-d[i][1] >= 0:
            dp[v][i] = min(dp[v][i-1], dp[v-d[i][1]][i-1]+d[i][0])
        else:
            dp[v][i] = dp[v][i-1]
        
for v in range(V-1, -1, -1):
    if [d for d in dp[v] if d <= W]:
        print(v)
        sys.exit()
print(0)

Submission status: Wrong Answer

Solution code:
import sys
rr = lambda: sys.stdin.readline().strip()
ri = lambda: int(rr())
rs = lambda: [int(_) for _ in rr().split()]

N, W = rs()
d = [rs() for _ in range(N)]

V = 10**3 + 1
dp = [[W+1 for _ in range(N)] for __ in range(V)]

for i in range(N):
    dp[0][i] = 0

for i in range(N):
    for v in range(V):
        if v-d[i][1] >= 0:
            dp[v][i] = min(dp[v][i-1], dp[v-d[i][1]][i-1]+d[i][0])
        else:
            dp[v][i] = dp[v][i-1]
        
for v in range(V-1, -1, -1):
    if [d for d in dp[v] if d <= W]:
        print(v)
        exit()
print(0)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def mi(): return map(int, input().split())


def li(): return list(mi())


def li_(): return [int(x) - 1 for x in input().split()]


def lin(n: int): return [input() for _ in range(n)]


def llin(n: int): return [li() for _ in range(n)]


def llin_(n: int): return [li_() for _ in range(n)]


def lli(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def f(): return float(input())


def s(): return input().replace('\n', '')


def main():
    N, W = mi()
    WV = llin(N)
    max_val = 0
    for i in range(N):
        max_val += WV[i][1]
    max_val += 1
    # dp[i][j]:=i番目の品で、価値がj以上になるように選んだときの最小重量
    dp = [[inf] * max_val for i in range(N)]
    for v in range(max_val):
        if v <= WV[0][1]:
            dp[0][v] = WV[0][0]
        else:
            break
    for i in range(1, N):
        for v in range(max_val):
            if v >= WV[i][1]:
                # print(dp[i - 1][v], dp[i - 1]
                #               [v - WV[i][1]] + WV[i][0])
                dp[i][v] = min(dp[i - 1][v], dp[i - 1]
                               [v - WV[i][1]] + WV[i][0])
            else:
                dp[i][v] = dp[i - 1][v]
            if v <= WV[i][1]:
                dp[i][v] = min(dp[i][v], WV[0][0])
    for v in reversed(range(max_val)):
        if dp[N-1][v] <= W:
            print(v)
            exit()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def mi(): return map(int, input().split())


def li(): return list(mi())


def li_(): return [int(x) - 1 for x in input().split()]


def lin(n: int): return [input() for _ in range(n)]


def llin(n: int): return [li() for _ in range(n)]


def llin_(n: int): return [li_() for _ in range(n)]


def lli(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def f(): return float(input())


def s(): return input().replace('\n', '')


def main():
    N, W = mi()
    WV = llin(N)
    max_val = 0
    for i in range(N):
        max_val += WV[i][1]
    max_val += 1
    # dp[i][j]:=i番目の品で、価値がj以上になるように選んだときの最小重量
    dp = [[inf] * max_val for i in range(N)]
    for v in range(max_val):
        if v <= WV[0][1]:
            dp[0][v] = WV[0][0]
        else:
            break
    for i in range(1, N):
        for v in range(max_val):
            if v >= WV[i][1]:
                # print(dp[i - 1][v], dp[i - 1]
                #               [v - WV[i][1]] + WV[i][0])
                dp[i][v] = min(dp[i - 1][v], dp[i - 1]
                               [v - WV[i][1]] + WV[i][0])
            else:
                dp[i][v] = dp[i - 1][v]
    for v in reversed(range(max_val)):
        if dp[N-1][v] <= W:
            print(v)
            exit()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def mi(): return map(int, input().split())


def li(): return list(mi())


def li_(): return [int(x) - 1 for x in input().split()]


def lin(n: int): return [input() for _ in range(n)]


def llin(n: int): return [li() for _ in range(n)]


def llin_(n: int): return [li_() for _ in range(n)]


def lli(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def f(): return float(input())


def s(): return input().replace('\n', '')


def main():
    N, W = mi()
    WV = llin(N)
    max_val = 0
    for i in range(N):
        max_val += WV[i][1]
    max_val += 1
    # dp[i][j]:=i番目の品で、価値がj以上になるように選んだときの最小重量
    dp = [[inf] * max_val for i in range(N)]
    for v in range(max_val):
        if v <= WV[0][1]:
            dp[0][v] = WV[0][0]
        else:
            break
    for i in range(1, N):
        for v in range(max_val):
            if v >= WV[i][1]:
                # print(dp[i - 1][v], dp[i - 1]
                #               [v - WV[i][1]] + WV[i][0])
                dp[i][v] = min(dp[i - 1][v], dp[i - 1]
                               [v - WV[i][1]] + WV[i][0])
            else:
                dp[i][v] = min(dp[i - 1][v], WV[i][0])
    for v in reversed(range(max_val)):
        if dp[N-1][v] <= W:
            print(v)
            exit()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
w = []
v = []
for _ in range(N):
    x, y = map(int, input().split())
    w.append(x)
    v.append(y)
    
V = N * max(v)

inf = float('inf')
dp = [[inf] * (V + 1) for i in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V + 1):
        if v[i] > j:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i])
            
ans = 0
for i in range(V):
    if dp[N][i] <= W:
        ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def mi(): return map(int, input().split())


def li(): return list(mi())


def li_(): return [int(x) - 1 for x in input().split()]


def lin(n: int): return [input() for _ in range(n)]


def llin(n: int): return [li() for _ in range(n)]


def llin_(n: int): return [li_() for _ in range(n)]


def lli(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def f(): return float(input())


def s(): return input().replace('\n', '')


def main():
    N, W = mi()
    WV = llin(N)
    max_val = 0
    for i in range(N):
        max_val += WV[i][1]
    max_val += 1
    # dp[i][j]:=i番目の品で、価値がj以上になるように選んだときの最小重量
    dp = [[inf] * max_val for i in range(N)]
    for v in range(max_val):
        if v <= WV[0][1]:
            dp[0][v] = WV[0][0]
        else:
            break
    for i in range(1, N):
        for v in range(max_val):
            if v > WV[i][1]:
                print(dp[i - 1][v], dp[i - 1]
                               [v - WV[i][1]] + WV[i][0])
                dp[i][v] = min(dp[i - 1][v], dp[i - 1]
                               [v - WV[i][1]] + WV[i][0])
            else:
                dp[i][v] = min(dp[i - 1][v], WV[i][0])
    for v in reversed(range(max_val)):
        if dp[N-1][v] <= W:
            print(v)
            exit()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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


dp = [[float('inf')] * (10000) for i in range(N)]


for i in range(N):
    for j in range(10000):
        if j == 0:
            dp[i][j] = 0

for i in range(N):
    for sum_v in range(0,10000):
        if sum_v - cost[i][1] >= 0:
            dp[i][sum_v] = min(dp[i-1][sum_v], dp[i-1][sum_v - cost[i][1]] + cost[i][0])
        dp[i][sum_v] = min(dp[i][sum_v], dp[i-1][sum_v])

ans = float('inf')

for j in range(0,10000):
    if dp[N-1][j] <= W:
        ans = j
print(ans)

Submission status: Wrong Answer

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

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


dp = [[float('inf')] * (1000) for i in range(N)]


for i in range(N):
    for j in range(1000):
        if j == 0:
            dp[i][j] = 0

for i in range(N):
    for sum_v in range(0,1000):
        if sum_v - cost[i][1] >= 0:
            dp[i][sum_v] = min(dp[i-1][sum_v], dp[i-1][sum_v - cost[i][1]] + cost[i][0])
        dp[i][sum_v] = min(dp[i][sum_v], dp[i-1][sum_v])

ans = float('inf')

for j in range(0,1000):
    if dp[N-1][j] <= W:
        ans = j
print(ans)

Submission status: Wrong Answer

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

n, W = [int(i) for i in input().split()]
dp = [W + 1] * (1010 * (n + 1))

dp[0] = 0
v_max = 0
for i in range(n):
    w, v = [int(i) for i in input().split()]
    v_max += v
    for j in range(v_max, v - 1, -1):
        dp[j] = min(dp[j - v] + w, dp[j])

ans = 0
for i in range(v_max, -1, -1):
    if dp[i] <= W:
        ans = i
print(ans)

Submission status: Wrong Answer

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

n, W = map(int, input().split())
dp = [[W] * (1010 * (n + 1)) for _ in range(n + 1)]

dp[0][0] = 0
v_max = 0
for i in range(n):
    w, v = map(int, input().split())
    for j in range(i, -1, -1):
        for k in range(v_max + 1):
            dp[j + 1][k + v] = min(dp[j][k] + w, dp[j + 1][k + v])
    v_max += v

ans = 0
for i in range(n + 1):
    for j in range(v_max + 1):
        if dp[i][j] <= W:
            ans = max(ans, j)
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
n,w_max=map(int,input().split())
W,V=[],[]
for i in range(n):
  w,v=map(int,input().split())
  W.append(w)
  V.append(v)
DP=[[float("inf") for i in range(10**5+1)] for j in range(n+1)]
DP[0][0]=1
for i in range(1,n+1):
  for j in range(i*(10**3)+1):
    if j>V[i-1]:
      DP[i][j]=min(DP[i-1][j],DP[i-1][j-V[i-1]]+W[i-1])
    else:
      DP[i][j]=min(DP[i-1][j],W[i-1])
  print(DP[i][:20])
ans=bisect.bisect_right(DP[n],w_max)-1
print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split())
wv = [[int(i) for i in input().split()] for j in range(N)]
maxV = 10 ** 5
dp = [float('inf')]*(maxV+1)
dp[0] = 0

for w, v in wv:
    for i in range(maxV, -1, -1):
        dp[i] = min(dp[i], dp[i-v] + w)

print(dp)

for i in range(maxV, -1, -1):
    if dp[i] <= W:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split())
w = [0]*N
v = [0]*N
for n in range(N):
    w[n],v[n] = map(int, input().split())
V = sum(v)
dp = [[float('inf')]*(V+1) for i in range(N+1)] 
dp[0][0] = 0

for i in range(1,N+1):
    for val in range(V):
        if val >= v[i-1]:
            dp[i][val] = min(dp[i][val],dp[i-1][val-v[i-1]] + w[i-1])
        dp[i][val] = min(dp[i][val],dp[i-1][val])

for val in reversed(range(V+1)):
    if dp[N][val] <= W:
        print(val)
        break