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:
a=input().split()
N=int(a[0])
W=int(a[1])
wv_list=[]
max_value=0
for i in range(N) :
  b=input().split()
  w=int(b[0])
  v=int(b[1])
  max_value+=v


  wv_list.append([w,v])

n_list=  [[10**9 for i in range(max_value+1)] for j in range(N)]



n_list[0][wv_list[0][1]]=wv_list[0][0]


for i in range(1,N) :

    for j in range(max_value) :

            s=j+wv_list[i][1]

            if s<=max_value :
                n_list[i][s]=min(n_list[i-1][j]+wv_list[i][0],n_list[i][s])
            n_list[i][j] = min(n_list[i - 1][j],n_list[i][j])
            n_list[i][wv_list[i][1]]=wv_list[i][0]



for i in range(1,max_value) :

    if n_list[-1][-i]<=W :
        
        print(max_value-i+1)
        break

Submission status: Wrong Answer

Solution code:
a=input().split()
N=int(a[0])
W=int(a[1])
wv_list=[]
max_value=0
for i in range(N) :
  b=input().split()
  w=int(b[0])
  v=int(b[1])
  max_value+=v


  wv_list.append([w,v])

n_list=  [[10**9 for i in range(max_value+1)] for j in range(N)]



n_list[0][wv_list[0][1]]=wv_list[0][0]

for i in range(1,N) :
    for j in range(max_value) :

            s=j+wv_list[i][1]
            if s<=max_value-1 :
                n_list[i][s]=min(n_list[i-1][j]+wv_list[i][0],n_list[i][s])
            n_list[i][j] = min(n_list[i - 1][j],n_list[i][j])

for i in range(1,max_value) :
    if n_list[-1][-i]<=W :
        print(max_value-i+1)
        break

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
goods = [list(map(int, input().split())) for _ in range(n)]
dp = [[10 ** 11] * (10 ** 5 + 1) for _ in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    weight, value = goods[i]
    for sum_value in range(10 ** 5 + 1):
        if (sum_value - value) >= 0:
            dp[i + 1][sum_value] = min(dp[i + 1][sum_value], dp[i][sum_value - value] + weight)
        dp[i + 1][sum_value] = min(dp[i + 1][sum_value], dp[i][sum_value])

ans = 0
for sum_value in range(10 ** 3):
    if dp[n][sum_value] <= w:
        ans = sum_value

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
 
N,W = map(int, input().split())
 
dp = [10 ** 10] * N * (10 ** 3)
dp[0] = 0
dp = np.array(dp)
 
 
for i in range(N):
    w,v = map(int, input().split())
    dp[v:] = np.minimum(dp[v:] , dp[:-v] + w)
  
for i,count in enumerate(dp):
    if dp[i] <= W:
        ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
 
N,W = map(int, input().split())
 
dp = [10 ** 10] * N * (10 ** 3)
dp[0] = 0
dp = np.array(dp)
 
 
for i in range(N):
    w,v = map(int, input().split())
    dp[v:] = np.minimum(dp[v:] , dp[:-v] + w)
    dp[:v] = np.minimum(dp[:v] , w)
  
for i,count in enumerate(dp):
    if dp[i] <= W:
        ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
 
N,W = map(int, input().split())
 
dp = [10 ** 10] * N * (10 ** 3)
dp[0] = 0
dp = np.array(dp)
 
 
for i in range(N):
    w,v = map(int, input().split())
    dp[v:] = np.minimum(dp[v:] , dp[:-v] + w)
    dp[:v] = np.minimum(dp[:v] , w)
  
for i,count in enumerate(dp):
    if count >= W+1:
        print(i-1)
        exit()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
 
N,W = map(int, input().split())
 
dp = [10 ** 10] * N * (10 ** 3)
dp[0] = 0
dp = np.array(dp)
 
 
for i in range(N):
    w,v = map(int, input().split())
    dp[v:] = np.minimum(dp[v:] , dp[:-v] + w)
    dp[:v] = np.minimum(dp[:v] , dp[0] + w)
  
for i,count in enumerate(dp):
    if count >= W+1:
        print(i-1)
        exit()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
 
N,W = map(int, input().split())
 
dp = [10 ** 9 + 1] * N * (10 ** 3)
dp[0] = 0
dp = np.array(dp)
 
 
for i in range(N):
    w,v = map(int, input().split())
    dp[v:] = np.minimum(dp[v:] , dp[:-v] + w)
    dp[:v] = np.minimum(dp[:v] , dp[0] + w)
  
for i,count in enumerate(dp):
    if count >= W+1:
        print(i-1)
        exit()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
 
N,W = map(int, input().split())
 
dp = [10 ** 9 + 1] * N * (10 ** 3)
dp[0] = 0
dp = np.array(dp)
 
 
for i in range(N):
    w,v = map(int, input().split())
    dp[v:] = np.minimum(dp[v:] , dp[:-v] + w)
    dp[:v] = np.minimum(dp[:v] , dp[0] + w)
  
print(dp)
for i,count in enumerate(dp):
    if count >= W+1:
        print(i-1)
        exit()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
 
N,W = map(int, input().split())
 
dp = [10 ** 9] * N * (10 ** 3)
dp[0] = 0
dp = np.array(dp)
 
 
for i in range(N):
    w,v = map(int, input().split())
    dp[v:] = np.minimum(dp[v:] , dp[:-v] + w)
    dp[:v] = np.minimum(dp[:v] , dp[0] + w)
  

for i,count in enumerate(dp):
    if count >= W+1:
        print(i-1)
        exit()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
from functools import lru_cache
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
def inpl_str():
    '''
    一行に複数の文字
    '''
    return list(input().split())

n, k = inpl()
dp = [[INF] * (10 ** 5 + 1) for i in range(n + 1)]
dp[0][0]=k
for i in range(n):
    w, v = inpl()
    for j in range(10**5+1):
        include = dp[i][j - v] - w if j-v>=0 and dp[i][j - v] - w >=0 else INF
        not_include = dp[i][j]
        dp[i + 1][j] = min(include, not_include)
tmp=dp[n][:]
for i in range(10 ** 5, -1, -1):
    if tmp[i] != INF:
        print(i)
        break
# for i in dp:
#     print(i)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, W = map(int, input().split())
WV = np.array([input().split() for _ in range(N)], np.int64)
V = sum(WV[:, 1])
INF = 1 << 60
dp = np.full(V + 1, INF)
dp[0] = 0
for w, v in WV:
    np.minimum(dp[v:], dp[:-v] + w, out=dp[v:])
for v in range(V):
    if dp[v] <= W:
        ans = v
print(ans)

Submission status: Wrong Answer

Solution code:
"""
dp[i][V] represents the minimum weight subset of the subarray arr[i…N-1]
required to get a value of at least V. The recurrence relation will be:

dp[i][V] = min(dp[i][V], w[i] + dp[i + 1][V – val[i]])

So, for each V from 0 to the maximum value of V possible, try to find if the
given V can be represented with the given array. The largest such V that can
be represented becomes the required answer.
"""

V_SUM_MAX = 1000
N_MAX = 100
W_MAX = 10000000

dp = [[ 0 for i in range(N_MAX)] for i in range(V_SUM_MAX + 1)]
v = [[ 0 for i in range(N_MAX)] for i in range(V_SUM_MAX + 1)]

def solveDp(r, i, w, val, n):
    if (r <= 0):
        return 0
    if (i == n):
        return W_MAX
    if (v[r][i]):
        return dp[r][i]

    v[r][i] = 1
    dp[r][i] = min(
        solveDp(r, i + 1, w, val, n),
        w[i] + solveDp(r - val[i], i + 1, w, val, n)
    )
    return dp[r][i]

def maxWeight( w, val, n, c):
    for i in range(V_SUM_MAX, -1, -1):
        if (solveDp(i, 0, w, val, n) <= c):
            return i

    return 0

if __name__ == '__main__':
    n, C = [int(x) for x in input().split()]
    w, val = [], []
    for _ in range(n):
        s, v1 = [int(x) for x in input().split()]
        w.append(s)
        val.append(v1)

    print(maxWeight(w, val, n, C))

Submission status: Wrong Answer

Solution code:
n, max_weight = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(n)]
W, V = zip(*WV)
#M = sum(V) + 1
M = 100100
INF = 1 << 60
dp = list([INF] * M for _ in range(n + 1))
dp[0][0] = 0
for i in range(n):
    for v in range(M):
        if v >= V[i]:
            dp[i + 1][v] = min(dp[i][v], dp[i][v - V[i]] + W[i])
        else:
            dp[i + 1][v] = dp[i][v]
for v in range(M):
    if dp[n][v] <= max_weight:
        print(v, dp[n][v])
        ans = v
print(ans)

Submission status: Wrong Answer

Solution code:
n, max_weight = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(n)]
W, V = zip(*WV)
#M = sum(V) + 1
M = 100100
INF = 1 << 20
dp = list([INF] * M for _ in range(n + 1))
dp[0][0] = 0
for i in range(n):
    for v in range(M):
        if v >= V[i]:
            dp[i + 1][v] = min(dp[i][v], dp[i][v - V[i]] + W[i])
        else:
            dp[i + 1][v] = dp[i][v]
for v in range(M):
    if dp[n][v] <= max_weight:
        ans = v
print(ans)

Submission status: Wrong Answer

Solution code:
n, max_weight = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(n)]
W, V = zip(*WV)
M = sum(V) + 1
INF = 1 << 20
dp = list([INF] * M for _ in range(n + 1))
for i in range(n):
    dp[i][0] = 0
for i in range(n):
    for v in range(M):
        if v >= V[i]:
            dp[i + 1][v] = min(dp[i][v], dp[i][v - V[i]] + W[i])
        else:
            dp[i + 1][v] = dp[i][v]
for v in range(M):
    if dp[n][v] <= max_weight:
        ans = v
print(ans)

Submission status: Wrong Answer

Solution code:
n, max_weight = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(n)]
W, V = zip(*WV)
M = sum(V) + 1
INF = 10 ** 6
dp = list([INF] * M for _ in range(n + 1))
for i in range(n):
    dp[i][0] = 0
for i in range(n):
    for v in range(M):
        if v >= V[i]:
            dp[i + 1][v] = min(dp[i][v], dp[i][v - V[i]] + W[i])
        else:
            dp[i + 1][v] = dp[i][v]
for v in range(M):
    if dp[n][v] <= max_weight:
        ans = v
print(ans)

Submission status: Wrong Answer

Solution code:
n, max_weight = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(n)]
W, V = zip(*WV)
M = sum(V) + 1
INF = 10 ** 6
dp = list([INF] * M for _ in range(n + 1))
dp[0][0] = 0
for i in range(n):
    for v in range(M):
        if v >= V[i]:
            dp[i + 1][v] = min(dp[i][v], dp[i][v - V[i]] + W[i])
        else:
            dp[i + 1][v] = dp[i][v]
ans = 0
for v in range(1, M):
    if dp[n][v] > max_weight:
        continue
    ans = v
print(ans)

Submission status: Wrong Answer

Solution code:
#DP-E
def main():
    import sys, copy
    N, W = map(int, sys.stdin.readline().split())
    L = tuple([tuple(map(int, sys.stdin.readline().split())) for _ in range(N)])
    #print(L)
    #価値テーブルを作成
    dp =[[10**11+1 for _ in range(10**5+1)] for _ in range(N)]
    dp[0][L[0][1]] = L[0][0] #初期設定
    #print(dp)
    for i in range(1, N):
        #1. 前回のコピー
        dp[i] = copy.copy(dp[i-1]) 
        w, v = L[i][0], L[i][1]
        #print(w, v)
        #2. 今回の荷物の更新
        dp[i][v] = min(w, dp[i][v])
        #3. 前回の荷物 + 今回の荷物の更新
        for j in range(10**5+1-v):
            if dp[i-1][j] !=0:
                dp[i][v+j] = min(dp[i][v+j], w + dp[i-1][j])
    
    
    
    ans = 0
    for v1,w1 in enumerate(dp[-1]):
        if w1 <= W:
            if ans < v1:
                ans = v1
            #print(v1, w1)
    print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n, w= map(int, input().split())
    v = 10**3
    w_item = []
    v_item = []
    dp = [[float('inf') for _ in range(v+1)] for _ in range(n+1)]
    dp[0][0] = 0
    for _ in range(n):
        tmp_w, tmp_v = map(int, input().split())
        w_item.append(tmp_w)
        v_item.append(tmp_v)

    for i in range(n):
        for j in range(v + 1):
            if j - v_item[i] >= 0:
                dp[i+1][j] = min(dp[i][j], dp[i][j-v_item[i]] + w_item[i])
            else:
                dp[i+1][j] = dp[i][j]
    
    res = 0
    for value, weight in enumerate(dp[-1]):
        if weight <= w:
            res = value
    print(res)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, w= map(int, input().split())
    v = 10**3
    w_item = []
    v_item = []
    dp = [[float('inf') for _ in range(v+1)] for _ in range(n+1)]
    dp[0][0] = 0
    for _ in range(n):
        tmp_w, tmp_v = map(int, input().split())
        w_item.append(tmp_w)
        v_item.append(tmp_v)

    for i in range(n):
        for j in range(v + 1):
            if v_item[i] <= v:
                dp[i+1][j] = min(dp[i][j], dp[i][j-v_item[i]] + w_item[i])
            else:
                dp[i+1][j] = dp[i][j]
    
    res = 0
    for value, weight in enumerate(dp[-1]):
        if weight <= w:
            res = value
    print(res)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, w= map(int, input().split())
    v = 10**3
    w_item = []
    v_item = []
    dp = [[10**9 for _ in range(v+1)] for _ in range(n+1)]
    dp[0][0] = 0
    for _ in range(n):
        tmp_w, tmp_v = map(int, input().split())
        w_item.append(tmp_w)
        v_item.append(tmp_v)

    for i in range(n):
        for j in range(v + 1):
            if v_item[i] <= v:
                dp[i+1][j] = min(dp[i][j], dp[i][j-v_item[i]] + w_item[i])
            else:
                dp[i+1][j] = dp[i][j]
    
    res = 0
    for value, weight in enumerate(dp[-1]):
        if weight <= w:
            res = value
    print(res)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import maxint

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

mxValue = 1000

weights, values = [], []
dp = [[None for n in range(N)] for i in range(mxValue+1)] 

for n in range(N) :
  w, v = map(int,raw_input().split())
  weights.append(w)
  values.append(v)

def solve(curValue, curItem) :
  if curValue <= 0 : return 0
  if curItem == N : return maxint
  if dp[curValue][curItem] is not None : return dp[curValue][curItem]

  dp[curValue][curItem] = min(
    solve(curValue, curItem+1), 
    solve(curValue - values[curItem], curItem+1) + weights[curItem]
  )

  return dp[curValue][curItem]

ans = 0
for val in range(mxValue, -1, -1) :
  if solve(val, 0) <= W :
    ans = val
    break

print ans

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, W = map(int, input().split())
    wv = [tuple(map(int, input().split())) for i in range(N)]

    dp = [-1]*(10**3 * N + 1)
    dp[0] = 0
    ans = 0
    for w, v in wv:
        for j in range(10**3 * N - v, -1, -1):
            if dp[j] >= 0 and dp[j] + w <= W:
                if dp[j+v] < dp[j] + w:
                    dp[j+v] = dp[j] + w
                    if ans < j+v:
                        ans = j+v
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, W = map(int, input().split())
    wv = [tuple(map(int, input().split())) for i in range(N)]

    dp = [-1]*(10**3 * N + 1)
    dp[0] = 0
    ans = 0
    for w, v in wv:
        for j in range(10**3 * N - v, -1, -1):
            if dp[j] >= 0 and dp[j] + w <= W:
                if dp[j+v] < dp[j] + w:
                    dp[j+v] = dp[j] + w
                    if ans < j+w:
                        ans = j+v
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
w, v = [0] * (N + 1), [0] * (N + 1)
INF = 10 ** 9
for i in range(1, N + 1):
    w[i], v[i] = map(int, input().split())

dp = [[INF] * ((10 ** 5) + 2) for i in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):
    for j in range(0, 10 **5+1):
        dp[i][j] = dp[i - 1][j]
        if j - v[i] >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])

ans = 0
for i in range(0, 10 ** 5+1):
    if dp[N][i] <= W:
        ans = i
#print(dp[N])
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import maxsize


def solve(ls, n, w):
	sm_value = 0
	for i in range(n):
		sm_value += ls[i][1]
	dp = [maxsize] * (sm_value + 1)
	dp[0] = 0
	for item in range(n):
		for value in range(sm_value, ls[item][1] - 1, -1):
			dp[value] = min(dp[value], dp[value - ls[item][1]] + ls[item][0])
	ans = -maxsize
	for i in range(sm_value + 1):
		if dp[i] < w:
			ans = max(ans, i)
	return ans


n, w = map(int, input().split())
ls = []
for i in range(n):
	ls.append(list(map(int, input().split())))

print(solve(ls, n, w))

Submission status: Wrong Answer

Solution code:
def solve():
    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)

    maxvalue = max(value)
    dp = [[float('inf')]*(maxvalue+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][0] = 0

    for i in range(N):
        for v in range(maxvalue+1):
            if v - value[i] < 0:
                dp[i+1][v] = min(dp[i+1][v], dp[i][v])
            else:
                dp[i+1][v] = min(dp[i+1][v], dp[i][v-value[i]]+weight[i])
                dp[i+1][v] = min(dp[i+1][v], dp[i][v])
    
    ans = 0
    for i in range(N+1):
        for j in range(maxvalue+1):
            if dp[i][j] <= W:
                ans = max(ans, j)
    
    print(ans)
            
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(10e9)


def knapSack(i,w):
    if i<0 or s[i]<w:
        return 0
    elif dp[i].get(w)!=None:
        return dp[i][w]
    elif wt[i]>w:
        dp[i][w]=knapSack(i-1,w)
    else:
        dp[i][w]=max(val[i]+knapSack(i-1,w-wt[i]),knapSack(i-1,w))
    return dp[i][w]

n,w=mdata()
val=[0]*(n)
wt=[0]*(n)
s=[0]*(n)
for i in range(n):
    wt[i],val[i]=mdata()
    s[i]=s[i-1]+wt[i]
dp=[{} for i in range(n)]
print(knapSack(n-1,w))

Submission status: Wrong Answer

Solution code:
N, W = [int(i) for i in input().split()]
noValue = [[W+1 for j in range(10001)] for i in range(N)]
w,v = [int(i) for i in input().split()]
maxValue = v
noValue[0][v] = w

for i in range(1,N) :
	noValue[i][0] = 0
	w, v = [int(i) for i in input().split()]
	for j in range(1,min(maxValue+v+1, 10001)) :
		if j < v  :
			noValue[i][j] = noValue[i-1][j]
		else :
			if noValue[i-1][j - v] == W + 1 :
				if j == v :
					noValue[i][j] = w
					maxValue = max(maxValue, j)
				else :
					noValue[i][j] = noValue[i-1][j]
			elif noValue[i-1][j-v] + w > W :
				noValue[i][j] = noValue[i-1][j]
			else :
				noValue[i][j] = min(noValue[i-1][j - v] + w, noValue[i-1][j])
				maxValue = max(maxValue, j)
print(maxValue)

Submission status: Wrong Answer

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

w_list = list()
v_list = list()

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

#print(w_list,v_list)

MAX_N = N+10
MAX_V = 100100
INF=100000000000

dp = [ [INF for _ in range(MAX_V)] for _ in range(MAX_N) ]
dp[0][0] = 0

for i in range(N):
    for sum_v in range(MAX_V):
        if sum_v-v_list[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v-v_list[i]]+w_list[i])
        else:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])

#print(dp)

res = 0
for sum_v in range(MAX_V):
    if dp[N][sum_v] <= W: res = sum_v

#print(dp[N-1])
print(res)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
w, v = [], []
for _ in range(N):
    w_, v_ = map(int, input().split())
    w.append(w_)
    v.append(v_)
V = sum(v)
dp = [[float("INF")]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V+1):
        if j >= v[i]: dp[i+1][j] = dp[i][j-v[i]]+w[i]
        else: dp[i+1][j] = dp[i][j]
ans = 0
for i in range(V+1):
    if dp[N][i]<=W: ans=i
print(ans)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_e
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N, W = MAP()
w, v = [], []

for _ in range(N):
    wi, vi = MAP()
    w.append(wi)
    v.append(vi)
max_v = N*max(v)
DP = [[float("INF")] * (N+1) for _ in range(max_v+1)]
DP[0][0] = 0

for i in range(1, max_v+1):
    for j in range(1, N+1):
        if v[j-1] > i:
            DP[i][j] = DP[i][j-1]
        else:
            DP[i][j] = min(
                DP[i][j-1],
                DP[i-v[j-1]][j-1] + w[j-1]
            )

ans = 0
for i in range(1, max_v+1):
    if DP[i][N] <= W:
        ans = i

print(ans)

Submission status: Wrong Answer

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

dp = [[0 for _ in range(10**5 + 1)] for _ in range(N+1)]
for i in range(1, 10**5):
    dp[0][i] = float('inf')

for i in range(1, N+1):
    for j in range(10**5):
        dp[i][j] = dp[i-1][j]
        if j - v[i] >= 0:
            dp[i][j] = min(dp[i][j], dp[i-1][j-v[i]] + w[i])

ans = 0
for k in range(10**5):
    if dp[N][k] <= W:
        ans = max(ans, k)

# print(*dp, sep='\n')
print(ans)

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)

dp = [[0 for _ in range(10**5 + 1)] for _ in range(N+1)]
for i in range(1, 10**5):
    dp[0][i] = float('inf')

for i in range(1, N+1):
    for j in range(10**5):
        dp[i][j] = dp[i-1][j]
        if j - v[i-1] >= 0:
            dp[i][j] = min(dp[i][j], dp[i-1][j-v[i-1]] + w[i-1])

ans = 0
for k in range(10**5):
    if dp[N][k] <= W:
        ans = max(ans, k)

# print(*dp, sep='\n')
print(ans)

Submission status: Wrong Answer

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

for i in range(1, N+1):
    for j in range(10**5 + 1):
        dp[i][j] = dp[i-1][j]
        if j - v[i-1] >= 0:
            dp[i][j] = min(dp[i][j], dp[i-1][j-v[i]] + w[i])

ans = 0
for k in range(10**5 + 1):
    if dp[N][k] <= W:
        ans = max(ans, k)

# print(*dp, sep='\n')
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

N, W = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]
# print(WV)
max_v = 0
for i in range(N):
    max_v += WV[i][1]
# print(max_v)
dp = [[INF]*(max_v+1) for _ in range(N+1)]
dp[0][0] = 0
# print(dp)
for n in range(N):
    for sum_v in range(max_v+1):
        weight = WV[n][0]
        value = WV[n][1]
        #print('weight', weight, 'value', value)
        if sum_v-value >= 0:
            dp[n+1][sum_v] = min(dp[n+1][sum_v], dp[n][sum_v-value]+weight)
        else:
            dp[n+1][sum_v] = min(dp[n+1][sum_v], dp[n][sum_v])
ans = 0
# print(dp)
for sum_v in range(max_v+1):
    if dp[N][sum_v] <= W:
        ans = sum_v
print(ans)

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
w=[0 for _ in range(110)]
v=[0 for _ in range(110)]
for i in range(1,N+1):
    w[i],v[i]=map(int,input().split())
dp=[[0 for i in range(110000)] for j in range(110)]
for i in range(1,110000):
    dp[0][i]=10**6

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

ans=0
for V in range(110000):
    if dp[N][V]<=W:
        ans=max(ans,V)

print(ans)

Submission status: Wrong Answer

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

wv = []
for _ in range(N):
    wv.append(tuple(map(int, input().split())))

INF = 10**11+1
V_MAX = 10**5
dp = [[INF]*(V_MAX+1) for _ in range(N+1)]

for i in range(N):
    wi, vi = wv[i]

    for j in range(vi):
        dp[i+1][j] = dp[i][j]

    for j in range(vi, V_MAX+1):
        dp[i+1][j] = min(dp[i][j], dp[i][j-vi] + wi)


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=list(map(int,input().split()))
N=N_W[0]
W=N_W[1]
items=[]
for i in range(N):
	sets=list(map(int,input().split()))
	items.append(sets)
V=0
for i in range(N):
	V=max(V,items[i][1])

f_inf=float('inf')

knapsack=[[f_inf for v in range(N*V+1)] for i in range(N+1)]
knapsack[0][0]=0

for i in range(N):
	for v in range(1,N*V+1):
		if v-items[i][1]>=0:
			knapsack[i+1][v]=min(knapsack[i+1][v],knapsack[i][v],knapsack[i][v-items[i][1]]+items[i][0])
		else:
			knapsack[i+1][v]=min(knapsack[i+1][v],knapsack[i][v])
value=0
for i in range(len(knapsack)):
	for j in range(len(knapsack[0])):
		if knapsack[i][j]<=W:
			value = max(value,j)
print(value)

Submission status: Wrong Answer

Solution code:
import sys

# import numpy as np

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

INF = 10 ** 18


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

    """    
    dp[ i ] : 価値 i における重さの最小値
    　
    品物一つ w,v を見ていくたびに、
    dp[ i ] = (その品物を使うパターン) or (その品物を使わないパターン)
    = min( dp[i -v] + w , dp[ i ] ) 
    を更新していけばよい。
    """

    dp = [0] + [INF] * 10 ** 5

    for i in range(N):
        for j in range(10 ** 5, w[i] - 1, -1):
            dp[j] = min(dp[j - v[i]] + w[i], dp[j])

    # print(dp[:30])

    ans = 0

    for i, j in enumerate(dp):
        if j <= W:
            ans = i
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

# import numpy as np

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

INF = 10 ** 18


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

    """    
    dp[ i ] : 価値 i における重さの最小値
    　
    品物一つ w,v を見ていくたびに、
    dp[ i ] = (その品物を使うパターン) or (その品物を使わないパターン)
    = min( dp[i -v] + w , dp[ i ] ) 
    を更新していけばよい。
    """

    dp = [0] + [INF] * 10 ** 5

    for i in range(N):
        for j in range(10 ** 5, w[i] - 1, -1):
            dp[j] = min(dp[j - v[i]] + w[i], dp[j])

    # print(dp[:30])

    ans = 0

    for i, j in enumerate(dp):
        if j <= W:
            ans = i
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

# import numpy as np

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

INF = 10 ** 18


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

    """    
    dp[ i ] : 価値 i における重さの最小値
    　
    品物一つ w,v を見ていくたびに、
    dp[ i ] = (その品物を使うパターン) or (その品物を使わないパターン)
    = min( dp[i -v] + w , dp[ i ] ) 
    を更新していけばよい。
    """

    dp = [0] + [INF] * 10 ** 5

    for i in range(N + 1):
        for j in range(10 ** 5, w[i] - 1, -1):
            dp[j] = min(dp[j - v[i]] + w[i], dp[j])

    # print(dp[:30])

    ans = 0

    for i, j in enumerate(dp):
        if j <= W:
            ans = i
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    N, W = map(int, input().split())
    inf = float('inf')
    dp = [inf] * (10**5+1)
    dp[0] = 0
    for n in range(1, N+1):
        w, v = map(int, input().split())
        for i in range(v, 10**5+1)[::-1]:
            if dp[i-v] + w <= W:
                dp[i] = min(dp[i], dp[i-v] + w)
    for i in range(10**5)[::-1]:
        if dp[i] < inf:
            print(i)
            break
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[float("inf")] * 1001 for _ in range(N + 1)]
    dp[0][0] = 0

    for n in range(N):
        for kati in range(1001):
            if kati - v[n] >= 0:
                dp[n+1][kati] = min(dp[n+1][kati], dp[n][kati-v[n]] + w[n])
            dp[n+1][kati] = min(dp[n+1][kati], dp[n][kati])

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

    print(ans)


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)


if __name__ == '__main__':
    main()