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:
def solve():
  I=lambda:map(int,input().split())
  N,W=I()
  g={}
  for _ in[0]*N:
    a,b=I()
    g[a]=g.get(a,[])+[b]
  *w,=g.keys()
  v=[]
  for i in range(len(w)):
    s=[0]+sorted(g[w[i]])[::-1]
    for i in range(1,len(s)):
      s[i]+=s[i-1]
    v.append(s)
  for _ in[0]*(4-len(w)):
    w.append(10**18)
    v.append([0])
  ans=0
  for i in range(len(v[0])):
    s0=w[0]*i
    for j in range(len(v[1])):
      s1=s0+w[1]*j
      if s1>W:break
      for k in range(len(v[2])):
        s2=s1+w[2]*k
        if s2>W:break
        l=min((W-s2)//w[3],len(v[3])-1)
        ans=max(ans,v[0][i]+v[1][j]+v[2][k]+v[3][l])
  print(ans)
if __name__=='__main__':
  solve()

Submission status: Wrong Answer

Solution code:
import numpy as np
INF = 10 ** 12

N, W = map(int, input().split(" "))
wv = np.array([[int(i) for i in input().split(" ")] for _ in range(N)])

sumv = np.sum(wv[:,1])

dp = np.zeros((N + 1, sumv + 1), dtype=np.int64)
dp[0][1:] = INF

for i in range(N):
    dp[i+1][:wv[i][1]] = dp[i][:wv[i][1]]
    dp[i+1][wv[i][1]:] = np.minimum(dp[i][wv[i][1]:], dp[i][:-wv[i][1]]+wv[i][0])
    print(dp)

ans = 0
for v, w in enumerate(dp[N]):
    if w <= W:
        ans = max(v, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from sys import stdin
from collections import defaultdict
input = stdin.readline
N, W = list(map(int, input().split()))
wvList = [list(map(int, input().split())) for _ in range(N)]

v_sum = sum([wv[1] for wv in wvList])
V_list = np.ones(v_sum)*np.inf


v_dict = defaultdict(int)
v_dict[0]=0

for wv in wvList:
    w,v = wv
    for v_key in list(v_dict.keys()):
        val  = min( v_dict[v_key]+w if v_dict[v_key]+w <=W else np.inf,
                   v_dict[v_key+v] if (v_key+v) in v_dict.keys() and v_dict[v_key+v] != 0 else np.inf)
        if not np.isinf(val) and val != 0:
            v_dict[v_key+v] = val

print(max(v_dict.keys()))

Submission status: Wrong Answer

Solution code:
import numpy as np
from sys import stdin
from collections import defaultdict
input = stdin.readline
N, W = list(map(int, input().split()))
wvList = [list(map(int, input().split())) for _ in range(N)]
v_sum = sum([wv[1] for wv in wvList])
V_list = np.ones(v_sum)*np.inf
v_dict = defaultdict(int)
v_dict[0]=0
for wv in wvList:
    w,v = wv
    for v_key in list(v_dict.keys()):
        val  = min( v_dict[v_key]+w if v_dict[v_key]+w <=W else np.inf,
                   v_dict[v_key+v] if (v_key+v) in v_dict.keys() and v_dict[v_key+v] != 0 else np.inf)
        if not np.isinf(val) and val != 0:
            print(v_key+v,val)
            v_dict[v_key+v] = val

Submission status: Wrong Answer

Solution code:
import numpy as np

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

dp = np.ones([2, N * 10 ** 3 + 1], dtype=int) * float("inf")
dp[0][0], dp[1][0] = 0, 0
ans = 0
for i in range(N):
    index = i % 2
    w, v = map(int, input().split())
    for j in range(1, len(dp[0])):
        if j <= v:
            dp[index][j] = min(w, dp[index-1][j])
        else:
            dp[index][j] = min(w + dp[index-1][j-v], dp[index-1][j])

        if dp[index][j] > W:
            ans = j - 1
            break

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

dp = np.ones([2, 3 * 10 ** 3 + 1], dtype=int) * float("inf")
dp[0][0], dp[1][0] = 0, 0
for i in range(N):
    index = i % 2
    w, v = map(int, input().split())
    for j in range(1, len(dp[0])):
        if j <= v:
            dp[index][j] = min(w, dp[index-1][j])
        else:
            dp[index][j] = min(w + dp[index-1][j-v], dp[index-1][j])

dp = np.minimum(dp[0], dp[1])
ans = 0
for i, w in enumerate(dp):
    if w <= W:
        ans = max(ans, i)
    else:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

dp = np.ones([2, 3 * 10 ** 3 + 1], dtype=int) * float("inf")
for i in range(N):
    index = i % 2
    w, v = map(int, input().split())
    for j in range(1, len(dp[0])):
        if j <= v:
            dp[index][j] = min(w, dp[index-1][j])
        else:
            dp[index][j] = min(w + dp[index-1][j-v], dp[index-1][j])

ans = 0
for element in dp:
    for i, w in enumerate(element):
        if w <= W:
            ans = max(ans, i)

print(ans)

Submission status: Wrong Answer

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

INF = 10**10
dp = [INF for i in range(100001)]
dp[0] = 0

for _ in range(N):
    w,v = map(int,input().split())
    dp1 = [d for d in dp]
    for i,d in enumerate(dp):
        if d == INF:
            continue
        else:
            if i + v <= 1000:
                dp1[i+v] = min(dp[i+v], dp[i]+w)
    dp = [d1 for d1 in dp1]

ans = 0
for i,d in enumerate(dp):
    if d <= W:
        ans = i

print(ans)

Submission status: Wrong Answer

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

INF = 10**10
dp = [INF for i in range(1001)]
dp[0] = 0

for _ in range(N):
    w,v = map(int,input().split())
    dp1 = [d for d in dp]
    for i,d in enumerate(dp):
        if d == INF:
            continue
        else:
            if i + v <= 1000:
                dp1[i+v] = min(dp[i+v], dp[i]+w)
    dp = [d1 for d1 in dp1]

ans = 0
for i,d in enumerate(dp):
    if d <= W:
        ans = i

print(ans)

Submission status: Wrong Answer

Solution code:
MAX_INT = int(10e10)

N,W = list(map(int,input().split()))
w = [0]
v = [0]

for i in range(N):
  a,b = list(map(int,input().split()))
  w.append(a)
  v.append(b)
V_MAX = max(v)

# dp[i][v] = w
dp = [[MAX_INT]*(N*V_MAX+1) for i in range(N+1)]

for i in range(1,N+1):
  dp[i-1][v[i-1]] = w[i-1]
  for j in range(1,N*V_MAX+1):
    if j < v[i]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i]]+w[i])  # max(iの品を使わない時, iの品を使う時)
for j in range(N*V_MAX,0,-1):
  for i in range(1,N+1):
    if dp[i][j] <= W:
      print(j)
      exit()

Submission status: Wrong Answer

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

max_v = 10**3*n
dp = [float("inf")]*(max_v+1)
dp[0] = 0

for i in range(n):
    w, v = map(int, input().split())
    for j in range(max_v+1-v)[::-1]:
        if dp[j] != float("inf"):
            dp[j+v] = min(dp[j+v], dp[j]+w)

for i in range(max_v)[::-1]:
    if dp[i] <= ww:
        print(i)
        exit()

Submission status: Wrong Answer

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

max_v = 10**3*n
dp = [float("inf")]*(max_v+1)
dp[0] = 0

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

for i in range(max_v)[::-1]:
    if dp[i] <= ww:
        print(i)
        exit()

Submission status: Wrong Answer

Solution code:
import sys

n, w = map(int, sys.stdin.readline().split())
weight = []
value = []
sum_value = 0
for i in range(n):
    wi, vi = map(int, sys.stdin.readline().split())
    weight.append(wi)
    value.append(vi)
    sum_value += vi

val = [0] * (sum_value + 1)
wght = [0] * (sum_value + 1)

for i in range(n):
    for j in range(sum_value - value[i], -1, -1):
        if wght[j] + weight[i] <= w:
            val[j + value[i]] = max(val[j + value[i]], val[j] + value[i])
            wght[j + value[i]] = wght[j] + weight[i]


max_val = 0

for i in range(sum_value, -1, -1):
    if wght[i] <= w:
        max_val = max(max_val, val[i])

print(max_val)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

import numpy as np

def main():
    N, W = map(int, input().split())

    dp = np.zeros((N+1, 10**3+1), dtype='uint64')
    dp = dp + np.inf
    dp[0][0] = 0


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

        dp[i+1][:value] = dp[i][:value]
        dp[i+1][value:] = np.minimum(dp[i][value:], dp[i][:-value] + weight)


    res = 0
    for i, weight in enumerate(dp[N]):
        if weight <= W: res = i

    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

import numpy as np
from sys import maxsize

def main():
    N, W = map(int, input().split())

    dp = np.zeros((N+1, 10**3+1), dtype='uint64')
    dp = dp + maxsize
    dp[0][0] = 0


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

        dp[i+1][:value] = dp[i][:value]
        dp[i+1][value:] = np.minimum(dp[i][value:], dp[i][:-value] + weight)


    res = 0
    for i, weight in enumerate(dp[N]):
        if weight <= W: res = i

    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

import numpy as np

def main():
    N, W = map(int, input().split())

    dp = np.zeros((N+1, 10**3+1), dtype='uint64')
    dp = dp + 10 ** 9 + 1
    dp[0][0] = 0


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

        dp[i+1][:value] = dp[i][:value]
        dp[i+1][value:] = np.minimum(dp[i][value:], dp[i][:-value] + weight)


    res = 0
    for i, weight in enumerate(dp[N]):
        if weight <= W: res = i

    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

# input処理を高速化する
input = sys.stdin.readline

# 入力
N, W = map(int, input().split())
# print(N, W)
MAX_V = 10**3+1

# 最小値を求めるので無限大の値
f_inf = float('inf')

def chmin(a, b):
    if a <= b:
        return a
    else:
        return b

def knapsack(n, w):
    # dpの初期化　dp[i][sum_v]は重さの総和の最小値
    dp = [[f_inf for i in range(10**3+1)] for j in range(N+1)]
    # 初期条件
    dp[0][0] = 0
    # forは全て関数の中で回す。
    # 入力
    for i in range(N):
        w, v = map(int, input().split())
        for sum_v in range(MAX_V):
            # i番目の品物を選ぶ場合
            if (sum_v -v >= 0):
                dp[i + 1][sum_v] = chmin(dp[i + 1][sum_v], dp[i][sum_v - v] + w)
            # i番目の品物を選ばない場合
            dp[i + 1][sum_v] = chmin(dp[i + 1][sum_v], dp[i][sum_v])
    #dp[N][sum_v]の値が、W以下であるsum_vの値の最大値
    ans = 0
    for sum_v in range(MAX_V):
        if dp[N][sum_v] <= W:
            ans = sum_v
    print(ans)


knapsack(N, W)

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
w,v = [],[]
dp = [[10**10]*100100 for _ in range(101)]
dp[0][0] = 0
for i in range(N):
    wi,vi = map(int,input().split())
    w.append(wi)
    v.append(vi)
for i in range(N):
    for sum_v in range(101):
        if(sum_v - v[i]) >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v],dp[i][sum_v-v[i]]+w[i])
        dp[i+1][sum_v] = min(dp[i+1][sum_v],dp[i][sum_v])
ans = 0
for i in range(100100):
    if dp[N][i] <= W:
        ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as f
n,s=map(int,input().split())
k=f(int)
k[0]=0
g=0
for i in range(n):
    w,v=map(int,input().split())
    c=list(k)
    for i in range(len(c)-1,-1,-1):
        if k[c[i]+v]!=0:
            k[c[i]+v]=min(k[c[i]]+w,k[c[i]+v])
        else:
            k[c[i]+v]=k[c[i]]+w
        if k[c[i]+v]<=s:
            g=max(g,c[i]+v)
print(g)

Submission status: Wrong Answer

Solution code:
def main():
    N, W = [int(n) for n in input().split()]
    
    baggages = [[int(n) for n in input().split()] for i in range(N)]# 荷物1, 荷物2, ...と数え、荷物0は数合わせの(0, 0)
    baggages.insert(0, [0, 0])

    VALUE, WEIGHT = 1, 0
    VALUE_LIMIT = int(1e4)
    INF = int(1e15)

    
    dp = [[-1] * (VALUE_LIMIT+1) for n in range(N+1)]# 荷物は0~N, 価値は0~VALUE_LIMIT
    # dp[baggage][value] := baggage番目までの荷物を使ってvalueだけとる最小重量
    dp[0] = [INF] * (VALUE_LIMIT+1)
    dp[0][0] = 0
    
    for baggage in range(1, N+1):
        for value in range(VALUE_LIMIT+1):
            if dp[baggage][value] != -1:
                continue
            bag_w = baggages[baggage][WEIGHT]
            bag_v = baggages[baggage][VALUE]
            val1 = dp[baggage-1][value]
            val2 = (dp[baggage-1][value-bag_v] + bag_w) if value >= bag_v else INF
            dp[baggage][value] = min(val1, val2)
    
    max_val = 0
    for index, w in enumerate(dp[N]):
        if w <= W:
            max_val = index
    print(max_val)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

M = sum(v)

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

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_e

import sys
input = sys.stdin.readline

N, W = [int(x) for x in input().split()]
MAX_V = N * 1000

dp = [[float('inf')] * MAX_V for _ in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    w, v = [int(x) for x in input().split()]
    dp[i][:v] = dp[i - 1][:v]
    for sum_v in range(v, MAX_V):
        if sum_v - v >= 0:
            dp[i][sum_v] = min(dp[i - 1][sum_v],
                               dp[i - 1][sum_v - v] + w)
        else:
            dp[i][sum_v] = dp[i - 1][sum_v]

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

Submission status: Wrong Answer

Solution code:
def e_knapsack2(N, W, Goods):
    """
    Dと同じ設定だが、制約が違う(1 <= v_i <= 10^3 と価値の制約がゆるめ)
    """
    import numpy as np
    # dp[v]: 価値vを達成するのに必要な重量の最小値
    # dpの長さは、すべての荷物を入れたときの価値+1で十分
    # 各要素の初期値は、Wを超える値ならよい(np.infだとうまく動作しないが)
    max_value = np.sum(np.array(Goods), axis=0)[1]
    dp = np.full(max_value + 1, W + 1, dtype='int64')
    dp[0] = 0  # 価値0を達成する荷物の重量は0とする
    for w, v in Goods:
        # 価値i(0<=i<=max_value-v)のときの重さの最小値に対し
        # 注目している荷物を入れて、価値i+vのときの重さの最小値を更新
        np.minimum(dp[:-v] + w, dp[v:], out=dp[v:])
    return np.max(np.where(dp <= W))

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
dct={}
weight=[]
value=[]
for i in range(n):
  x,y=map(int,input().split())
  weight.append(x)
  value.append(y)
def fun(i,val,wgt):
  global n,w,dct,weight,value
  if(wgt>w):
    return 0
  if(i>=n):
    return val
  s=str([i,val])
  if s in dct:
    return dct[s]
  x=fun(i+1,val+value[i],wgt+weight[i])
  y=fun(i+1,val,wgt)
  dct[s]=max(x,y)
  return dct[s]
print(fun(0,0,0))

Submission status: Wrong Answer

Solution code:
N, W = list(map(int,raw_input().split()))
dp = [float("inf") for i in range(100001)]
dp[0] = 0
for i in xrange(N):
  wi, vi = list(map(int,raw_input().split()))
  for v in xrange(1000-vi, -1, -1):
    dp[v+vi] = min(dp[v+vi],dp[v]+wi)
print(max([v for v in xrange(100001) if dp[v]<=W]))

Submission status: Wrong Answer

Solution code:
import numpy as np
n, W = map(int, input().split())
dp = np.full(n*10**3, W+1, 'i8')
dp[0] = 0

for i in range(n):
  w, v = map(int, input().split())
  dp[v:] = np.minimum(dp[v:], dp[:-v]+w)
print(np.max(np.where(dp<=W)))

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
w = []
v = []
for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
VM = sum(v)
dp = [[float('inf') for _ in range(VM)] for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for j in range(VM):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        if j - w[i] >= 0:
            if dp[i][j - v[i]] + w[i] <= W:
                dp[i + 1][j] = min(dp[i][j - v[i]] + w[i], dp[i + 1][j])
ans = 0
for i in range(VM):
    if dp[N][i] < float('inf'):
        ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
total_v=sum(v)
INF=100000000
dp=[INF for i in range(total_v+1)]
dp[0]=0
dp=np.array(dp)
for i in range(N):
    dp[v[i]:]=np.minimum(dp[v[i]:],dp[:-v[i]]+w[i])
for i in reversed(range(1,total_v+1)):
    if dp[i]<=W:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
import numpy as np
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
total_v=sum(v)
INF=100000000
dp=[INF for i in range(total_v+1)]
dp[0]=0
dp=np.array(dp)
for i in range(N):
    dp[v[i]:]=np.minimum(dp[v[i]:],dp[:-v[i]]+w[i])
for i in reversed(range(1,sum(v))):
    if dp[i]<=W:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
import numpy as np
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
total_v=sum(v)
INF=100000000
dp=[INF for i in range(total_v+1)]
dp[0]=0
dp=np.array(dp)
for i in range(N):
    dp[v[i]:]=np.minimum(dp[v[i]:],dp[:-v[i]]+w[i])
for i in reversed(range(1,sum(v)+1)):
    if dp[i]<=W:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
import numpy as np
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
total_v=sum(v)
INF=100000000
dp=[INF for i in range(total_v+1)]
dp[0]=0
dp=np.array(dp)
for i in range(N):
    dp[v[i]:]=np.minimum(dp[v[i]:],dp[:-v[i]]+w[i])
for i in range(sum(v)):
    if dp[i]<=W and dp[i+1]>W and dp[i+1]!=INF:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
import numpy as np
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
total_v=sum(v)
INF=100000000
dp=[INF for i in range(total_v+1)]
dp[0]=0
dp=np.array(dp)
for i in range(N):
    dp[v[i]:]=np.minimum(dp[v[i]:],dp[:-v[i]]+w[i])
for i in reversed(range(sum(v)+1)):
    if dp[i]<=W:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
import numpy as np
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
total_v=sum(v)
INF=100000000
dp=[INF for i in range(total_v+1)]
dp[0]=0
dp=np.array(dp)
for i in range(N):
    dp[v[i]:]=np.minimum(dp[v[i]:],dp[:total_v-v[i]+1]+w[i])
for i in range(sum(v)+1,-1):
    if dp[i]<=W:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
import numpy as np
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
total_v=sum(v)
INF=100000000
dp=[INF for i in range(total_v+1)]
dp[0]=0
dp=np.array(dp)
for i in range(N):
    dp[v[i]:]=np.minimum(dp[v[i]:],dp[:total_v-v[i]+1]+w[i])
for i in reversed(range(sum(v)+1)):
    if dp[i]<=W:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
import numpy as np
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
total_v=sum(v)
INF=100000000
dp=[INF for i in range(total_v+1)]
dp[0]=0
dp=np.array(dp)
for i in range(N):
    dp[v[i]:]=np.minimum(dp[v[i]:],dp[:total_v-v[i]+1]+w[i])
for i in reversed(range(sum(v))):
    if dp[i]<=W:
        print(i+1)
        break

Submission status: Wrong Answer

Solution code:
import numpy as np
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
total_v=sum(v)
INF=100000000
dp=[INF for i in range(total_v+1)]
dp[0]=0
dp=np.array(dp)
for i in range(N):
    dp[v[i]:]=np.minimum(dp[v[i]:],dp[:total_v-v[i]+1]+w[i])
for i in range(sum(v)+1):
    if dp[i]<=W:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
import numpy as np
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
total_v=sum(v)
INF=100000000
dp=[INF for i in range(total_v+1)]
dp[0]=0
dp=np.array(dp)
for i in range(N):
    dp[v[i]:]=np.minimum(dp[v[i]:],dp[:total_v-v[i]+1]+w[i])
for i in reversed(range(sum(v))):
    if dp[i]<=W:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
import numpy as np
n,w = [int(x) for x in input().split()]
wv = np.array([[int(y) for y in input().split()] for z in range(n)],dtype=int)
sum_wv = np.sum(wv,axis=0)
sum_v = sum_wv[1]
dp = np.full(sum_v+1,100001,dtype="int")
dp[0] = 0
for wei,val in wv:
    dp[val:] = np.minimum(dp[val:],dp[:-val]+wei)
for p in range(sum_v,1,-1):
    if(dp[p] <= w):
        print(p)
        break

Submission status: Wrong Answer

Solution code:
MAX_V = 1001
MAX_N = 101
INF = pow(2, 70)

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

dp = [[INF for _ in range(MAX_V)] for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for sum_v in range(MAX_V):
        # print(i, sum_v, sum_v - v[i] >= 0)
        if sum_v - v[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - v[i]] + w[i])
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])
        # print(dp[i + 1][sum_v])

ans = max([i for i in range(len(dp[N])) if dp[N][i] <= W])
# for l in dp:
#     print([n for n in l if not n == INF])

print(ans)

Submission status: Wrong Answer

Solution code:
MAX_V = 1001
MAX_N = 101
INF = pow(2, 64)

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

dp = [[INF for _ in range(MAX_V)] for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for sum_v in range(MAX_V):
        # print(i, sum_v, sum_v - v[i] >= 0)
        if sum_v - v[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - v[i]] + w[i])
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])
        # print(dp[i + 1][sum_v])

ans = max([i for i in range(len(dp[N])) if dp[N][i] <= W])
# for l in dp:
#     print([n for n in l if not n == INF])

print(ans)

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]


def solve():
    MaxV = 10**3*N+1
    dp = [[float('inf')]*MaxV for _ in range(N+1)]
    dp[0][0] = 0

    for i in range(1, N+1):
        for v in range(MaxV):
            if items[i-1][1] <= v:
                dp[i][v] = min(dp[i-1][v], dp[i-1]
                               [v-items[i-1][1]]+items[i-1][0])
            else:
                dp[i][v] = dp[i-1][v]
    print(dp[N].index(max(list(filter(lambda x: x <= W, dp[N])))))


solve()

Submission status: Wrong Answer

Solution code:
from sys import stdin

INF = float('inf')

MAX = 100003
n, W = map(int, raw_input().strip().split())
inp = stdin.readlines()

dp = [[INF for i in xrange(MAX + 1)] for j in xrange(n)]

# dp[i][j] is total value if using only the first i elements, weight j can be taken
# and 0 otherwise

i = 0
for line in inp:
    wi, vi = map(int, line.strip().split())

    if i == 0:
        dp[0][vi] = wi
    else:
        for V in xrange(vi):
            dp[i][V] = dp[i - 1][V]
        
        dp[i][vi] = wi
        
        for V in xrange(vi, MAX + 1):
            if dp[i - 1][V] != INF: dp[i][V] = dp[i - 1][V]
            if dp[i - 1][V - vi] != INF: dp[i][V] = min(dp[i][V], dp[i - 1][V - vi] + wi)

    i += 1

ans = 0
for v in xrange(MAX + 1):
    if dp[n - 1][v] >= 0 and dp[n - 1][v] <= W: ans = max(ans, v)

assert ans != INF
print ans

Submission status: Wrong Answer

Solution code:
from sys import stdin

INF = float('inf')

MAX = 100003
n, W = map(int, raw_input().strip().split())
inp = stdin.readlines()

dp = [[INF for i in xrange(MAX + 1)] for j in xrange(n)]

# dp[i][j] is total value if using only the first i elements, weight j can be taken
# and 0 otherwise

i = 0
for line in inp:
    wi, vi = map(int, line.strip().split())

    if i == 0:
        dp[0][vi] = wi
    else:
        for V in xrange(vi):
            dp[i][V] = dp[i - 1][V]
        
        dp[i][vi] = wi
        
        for V in xrange(vi, MAX + 1):
            if dp[i - 1][V] != INF: dp[i][V] = dp[i - 1][V]
            if dp[i - 1][V - vi] != INF: dp[i][V] = min(dp[i][V], dp[i - 1][V - vi] + wi)

    i += 1

ans = 0
for v in xrange(MAX + 1):
    if dp[n - 1][v] >= 0 and dp[n - 1][v] <= W: ans = max(ans, v)

print ans

Submission status: Wrong Answer

Solution code:
from sys import stdin

INF = float('inf')

MAX = 100003
n, W = map(int, raw_input().strip().split())
inp = stdin.readlines()

dp = [[INF for i in xrange(MAX + 1)] for j in xrange(n)]

# dp[i][j] is total value if using only the first i elements, weight j can be taken
# and 0 otherwise

i = 0
for line in inp:
    wi, vi = map(int, line.strip().split())

    if i == 0:
        dp[0][vi] = wi
    else:
        for V in xrange(vi):
            dp[i][V] = dp[i - 1][V]
            
        dp[i][vi] = wi
        
        for V in xrange(vi, MAX + 1):
            if dp[i - 1][V] != INF: dp[i][V] = dp[i - 1][V]
            if dp[i - 1][V - vi] != INF: dp[i][V] = min(dp[i][V], dp[i - 1][V - vi] + wi)

    i += 1

ans = 0
for v in xrange(MAX + 1):
    if dp[n - 1][v] > 0 and dp[n - 1][v] <= W: ans = max(ans, v)

print ans

Submission status: Wrong Answer

Solution code:
from sys import stdin

INF = float('inf')

MAX = 100000
n, W = map(int, raw_input().strip().split())
inp = stdin.readlines()

dp = [[INF for i in xrange(MAX + 1)] for j in xrange(n)]

# dp[i][j] is total value if using only the first i elements, weight j can be taken
# and 0 otherwise

i = 0
for line in inp:
    wi, vi = map(int, line.strip().split())

    if i == 0:
        dp[0][vi] = wi
    else:
        for V in xrange(vi):
            dp[i][V] = dp[i - 1][V]
            
        dp[i][vi] = wi
        
        for V in xrange(vi, MAX + 1):
            if dp[i - 1][V] != INF: dp[i][V] = dp[i - 1][V]
            if dp[i - 1][V - vi] != INF: dp[i][V] = min(dp[i][V], dp[i - 1][V - vi] + wi)

    i += 1

ans = 0
for v in xrange(MAX + 1):
    if dp[n - 1][v] > 0 and dp[n - 1][v] <= W: ans = max(ans, v)

print ans

Submission status: Wrong Answer

Solution code:
from sys import stdin

INF = float('inf')

MAX = 100000
n, W = map(int, raw_input().strip().split())
inp = stdin.readlines()

dp = [[INF for i in xrange(MAX + 1)] for j in xrange(n)]

# dp[i][j] is total value if using only the first i elements, weight j can be taken
# and 0 otherwise

i = 0
for line in inp:
    wi, vi = map(int, line.strip().split())

    if i == 0:
        dp[0][vi] = wi
    else:
        for V in xrange(vi):
            dp[i][V] = dp[i - 1][V]
            
        dp[i][vi] = wi
        
        for V in xrange(vi + 1, MAX + 1):
            if dp[i - 1][V] != INF: dp[i][V] = dp[i - 1][V]
            if dp[i - 1][V - vi] != INF: dp[i][V] = min(dp[i][V], dp[i - 1][V - vi] + wi)

    i += 1

ans = 0
for v in xrange(MAX + 1):
    if dp[n - 1][v] > 0 and dp[n - 1][v] <= W: ans = max(ans, v)

print ans

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
L = 100000
dp = [[1000000001 for _ in range(L+1)] for _ in range(N+1)]
W, V = [], []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
dp[0][0] = 0
for i in range(N):
    for j in range(L+1):
        if j + V[i] <= L:
            dp[i+1][j] = min(dp[i][j], dp[i][j-V[i]] + W[i])
        else:
            dp[i+1][j] = dp[i][j]
for i, d in enumerate(dp[N]):
    if d <= M:
        maxv = i
print(maxv)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
L = 100000
dp = [[1000000001 for _ in range(L+1)] for _ in range(N+1)]
W, V = [], []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
dp[0][0] = 0
for i in range(N):
    for j in range(L):
        if j + V[i] <= L:
            dp[i+1][j] = min(dp[i][j], dp[i][j-V[i]] + W[i])
        else:
            dp[i+1][j] = dp[i][j]
for i, d in enumerate(dp[N]):
    if d <= M:
        maxv = i
print(maxv)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
L = 1000
dp = [[1000000001 for _ in range(L+1)] for _ in range(N+1)]
W, V = [], []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
dp[0][0] = 0
for i in range(N):
    for j in range(L):
        if j + V[i] <= L:
            dp[i+1][j] = min(dp[i][j], dp[i][j-V[i]] + W[i])
        else:
            dp[i+1][j] = dp[i][j]
for i, d in enumerate(dp[N]):
    if d <= M:
        maxv = i
print(maxv)

Submission status: Wrong Answer

Solution code:
from sys import stdin
N, W = map(int, input().split())
s = list(list(map(int, line.split())) for line in stdin.read().splitlines())

sumv = sum(s[i][1] for i in range(N))

INF = 10e12
dp = [INF] * (sumv + 1)  # minimum w required to achieve  value V. dp[v] = w

dp[0] = 0

for n in range(N):
    w0, v0 = s[n]
    for v in range(sumv, v0 - 1, -1):
        if dp[v - v0] + w0 <= W:
            dp[v] = min(dp[v], dp[v - v0] + w0)

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

Submission status: Wrong Answer

Solution code:
n,k=(int(i) for i in input().split())
e = [[int(i) for i in input().split()] for j in range(n)]
#print(n,k,e)
maxv=0
for i in range(n):
    maxv+=e[i][1]
#print(maxv)

dp = [[0 for i in range(maxv+1)] for j in range(n+1)]
#print(dp)

for i in range(1, maxv+1):
    dp[0][i] = float('inf')
#print(dp)

for j in range(n):
    for i in range(1, maxv+1):
        if i < e[j][1] :
            dp[j + 1][i] = dp[j][i]
        else:
            dp[j + 1][i] = min(dp[j][i], dp[j][i - e[j][1]] +e[j][0])
#print(dp)
ans = 0
for i in range(maxv):
    if dp[n][i] <= k and ans < i:
        ans = i
        
print(ans)