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:
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)]
w=[[0 for i in range(maxv+1)] for j in range(n)]

for j in range(maxv+1):
    if j >= e[0][1]:
        dp[0][j]=e[0][1]
        w[0][j]=e[0][0]
        
ans=e[0][1]
#print(w)

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

print(ans)

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)]
w=[[0 for i in range(maxv+1)] for j in range(n)]

for j in range(maxv+1):
    if j >= e[0][0]:
        dp[0][j]=e[0][1]
        w[0][j]=e[0][0]

#print(dp)
#print(w)

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

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)]
w=[[0 for i in range(maxv+1)] for j in range(n)]

for j in range(maxv+1):
    if j >= e[0][0]:
        dp[0][j]=e[0][1]
        w[0][j]=e[0][0]

#print(dp)
#print(w)

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N, W = map(int, raw_input().split())
DP = [0] + [INF] * 10000
for _ in range(N):
    w, v = map(int, raw_input().split())
    for i in range(v, 10001)[::-1]:
        DP[i] = min(DP[i], DP[i - v] + w)

for i in range(10001)[::-1]:
    if DP[i] <= W:
        print i
        break

Submission status: Wrong Answer

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

max_size = 10**3
dp = [float("inf") for i in range(max_size+1)]
dp[0] = 0

for i in range(N) :
    weight,value = map(int,input().split())
    for j in range(max_size, value-1, -1) :
        if dp[j - value] + weight <= W :
            dp[j] = min(dp[j], dp[j-value] + weight)

for i in range(max_size, -1, -1) :
    if dp[i] < float("inf") :
        ans = i
        break

print(ans)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(N)]
dp = {0: 0}
for i in range(N):
    for j in sorted(dp.keys(), reverse=True):
        w, v = wv[i][0], wv[i][1]
        nw = dp[j] + w
        nv = j + v
        if nw <= W:
            if nv in dp:
                if nw < dp[nv]:
                    dp[nv] = nw
        else:
            dp[nv] = nw

print(max(dp.keys()))

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(N)]
dp = {0: 0}
for i in range(N):
    for j in sorted(dp.keys(), reverse=True):
        w, v = wv[i][0], wv[i][1]
        nw = dp[j] + w
        nv = j + v
        if nw <= W:
            if nv in dp:
                dp[nv] = nw
        else:
            dp[nv] = nw

print(max(dp.keys()))

Submission status: Wrong Answer

Solution code:
def main():
  N, W = list(map(int, input().split()))
  Data = []
  su = 0
  for i in range(N):
    t = list(map(int, input().split()))
    su += t[1]
    Data.append(t)
  
  DP = [int(10e6) if i != Data[0][1] else Data[0][0] for i in range(su + 1)]
  DP[0] = 0
  
  for i in range(1, N):
    for j in range(su - Data[i][1], -1, -1):
      k = j + Data[i][1]
      DP[k] = min(DP[j] + Data[i][0], DP[k])
      
  for i in range(su, -1, -1):
    if DP[i] <= W:
      print(i)
      break
  
main()

Submission status: Wrong Answer

Solution code:
def main():
  N, W = list(map(int, input().split()))
  Data = []
  su = 0
  for i in range(N):
    t = list(map(int, input().split()))
    su += t[1]
    Data.append(t)
  
  DP = [int(10e6) if i != Data[0][1] else Data[0][0] for i in range(su + 1)]
  DP[0] = 0
  
  for i in range(1, N):
    for j in range(su - 1 - Data[i][1], -1, -1):
      k = j + Data[i][1]
      DP[k] = min(DP[j] + Data[i][0], DP[k])
      
  for i in range(su, -1, -1):
    if DP[i] <= W:
      print(i)
      break
  
main()

Submission status: Wrong Answer

Solution code:
N, W = map( int, input().split())
dp = [10**9+1]*(10**5+2)
for _ in range(N):
    w, v = map( int, input().split())
    #iを実現しうる最小のwを更新すればよいのでは
    for i in range(10**5,-1,-1):
        if i <= v:
            dp[i] = min( dp[i], w)
        else:
            if dp[i-v] + w <= W:
                dp[i] = min( dp[i-v] + w, dp[i])
    print(dp[:90])
print( dp.index(10**9+1)-1)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, W = map(int, input().split())
ws, vs = zip(*[map(int, input().split()) for _ in range(N)])
maxV = max(vs)
V = sum(vs)
INF = 10**13

def maxvalue_recursive(N, V):
    dp = {}
    def minweight(i, v):
        if (i, v) not in dp:
            if i == 0:
                if v == 0: dp[i, v] = 0
                elif v == vs[i]: dp[i, v] = ws[i]
                else: dp[i, v] = INF
            else:
                if vs[i] <= v:
                    dp[i, v] = min(minweight(i - 1, v - vs[i]) + ws[i], minweight(i - 1, v))
                else:
                    dp[i, v] = minweight(i - 1, v)
        return dp[i, v]

    for v in range(V, -1, -1):
        if minweight(N - 1, v) <= W:
            return v

def maxvalue_dp(N, V):
    dp = np.zeros(V + 1, np.int64)
    dp += INF
    dp[0] = 0
    dp[vs[0]] = ws[0]
    for i, (w, v) in enumerate(zip(ws, vs)):
        dp[v:] = np.minimum(dp[v:], dp[:-v] + w)
    for v in range(V, -1, -1):
        if dp[v] <= W:
            return v

#print(maxvalue_recursive(N, V))
print(maxvalue_dp(N, V))

Submission status: Wrong Answer

Solution code:
import numpy as np
N, W = map(int, input().split())
ws, vs = zip(*[map(int, input().split()) for _ in range(N)])
maxV = max(vs)
V = maxV * N
INF = 10**10

def maxvalue_recursive(N, V):
    dp = {}
    def minweight(i, v):
        if (i, v) not in dp:
            if i == 0:
                if v == 0: dp[i, v] = 0
                elif v == vs[i]: dp[i, v] = ws[i]
                else: dp[i, v] = INF
            else:
                if vs[i] <= v:
                    dp[i, v] = min(minweight(i - 1, v - vs[i]) + ws[i], minweight(i - 1, v))
                else:
                    dp[i, v] = minweight(i - 1, v)
        return dp[i, v]

    for v in range(V, -1, -1):
        if minweight(N - 1, v) <= W:
            return v

def maxvalue_dp(N, V):
    dp = np.zeros(V + 1, np.int64)
    dp += INF
    dp[0] = 0
    dp[vs[0]] = ws[0]
    for i, (w, v) in enumerate(zip(ws, vs)):
        dp[v:] = np.minimum(dp[v:], dp[:-v] + w)
    for v in range(V, -1, -1):
        if dp[v] <= W:
            return v

#print(maxvalue_recursive(N, V))
print(maxvalue_dp(N, V))

Submission status: Wrong Answer

Solution code:
N,W=map(int, raw_input().split())
A=[ map(int, raw_input().split())  for i in range(N) ] 

V=10**3
dp= [ None for i in range(V+1) ]
dp[0]=0


for w,v in A:
	for i in range(V,-1,-1):
		if dp[i] is not None:
			if  0<=i+v<=V:
				if dp[i+v] is None:
					dp[i+v]=dp[i]+w
				else:
					dp[i+v]=min( dp[i+v], dp[i]+w )


for i in range(V,-1,-1):
	if dp[i] is not None:
		if dp[i]<=W:
			print i
			quit()

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
L = [list(map(int, input().split())) for i in range(N)]
V = 0
for i in range(N):
  V += L[i][1]

dp = [[10**7+1] * (V + 1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V+1):
        if j - L[i][1] >= 0:
          dp[i+1][j] = min(dp[i][j], dp[i][j-L[i][1]] + L[i][0])
        else:
          dp[i+1][j] = dp[i][j]
ans = 0
for j in range(V+1):
    if  W >= dp[-1][j]:
        ans = max(ans, j)
print(ans)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
L = [list(map(int, input().split())) for i in range(N)]
V = 0
for i in range(N):
  V += L[i][1]

dp = [[10**7] * (V + 1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V+1):
        if j - L[i][1] >= 0:
          dp[i+1][j] = min(dp[i][j], dp[i][j-L[i][1]] + L[i][0])
        else:
          dp[i+1][j] = dp[i][j]
ans = 0
for j in range(V+1):
    if  W >= dp[-1][j] and ans < j:
        ans = j
print(ans)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
L = [list(map(int, input().split())) for i in range(N)]
#V = 0
#for i in range(N):
#  V += L[i][1]
#print(V)
V = 10**5

dp = [[10**7] * (V + 1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V+1):
        if j - L[i][1] >= 0:
          dp[i+1][j] = min(dp[i][j], dp[i][j-L[i][1]] + L[i][0])
        else:
          dp[i+1][j] = dp[i][j]
ans = 0
for j in range(V+1):
    if  W >= dp[-1][j] and ans < j:
        ans = j
print(ans)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    wi, vi = map(int, input().split())
    w.append(wi)
    v.append(vi)

v_sum = sum(v) + 1
inf = float('inf')
dp = [inf] * v_sum
dp[0] = 0

for i in range(N):
    for j in reversed(range(v_sum)):
        if j + v[i] < v_sum and dp[j] != inf:
            dp[j + v[i]] = min(dp[j + v[i]], dp[j] + w[i])

print(dp)

for i in reversed(range(v_sum)):
    if dp[i] <= W:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
def main():
    N, W = map(int, input().split())
    VMAX = int(1e5)+1
    dp = [[float("inf")] * (VMAX) for _ in range(2)]
    dp[0][0] = 0
    for i in range(N):
        w, v = map(int, input().split())
        for j in range(VMAX):
            dp[(i+1) % 2][j] = min(dp[i % 2][j], dp[i % 2][max(j-v, 0)]+w)
    left = 0
    right = VMAX-1
    while left < right:
        center = (left + right) // 2
        if dp[N % 2][center] <= W:
            left = center + 1
        else:
            right = center
    print(left-1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]
sum_v = sum([item[1] for item in items])
inf = float("inf")
dp = [[inf for _ in range(sum_v+1)] for _ in range(N+1)]


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

for v in range(sum_v, -1, -1):
    if dp[N][v] <= W:
        print(v)
        exit()

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
L = [list(map(int, input().split())) for i in range(N)]
V = 0
for i in range(N):
  V += L[i][1]

dp = [[10**7] * (V + 1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V+1):
        if j - L[i][1] >= 0:
          dp[i+1][j] = min(dp[i][j], dp[i][j-L[i][1]] + L[i][0])
        else:
          dp[i+1][j] = dp[i][j]
ans = 0
for i in range(N+1):
    for j in range(V+1):
        if  W >= dp[i][j] and ans < j:
            ans = j
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

dp = np.full(N*1000, W+1, dtype=np.int64)
dp[0] = 0

for _ in range(N):
  w,v = map(int,input().split())
  np.minimum(dp[:-v]+w, dp[v:], out=dp[v:])

print(((dp <= W)*np.arange(N*1000)).max())

Submission status: Wrong Answer

Solution code:
N,W=[int(x) for x in raw_input().split()]
A=[]
maxval=0
for i in range(N):
    w,v=[int(x) for x in raw_input().split()]
    A.append([w,v])
    maxval+=v
B=[[ 1e10  for i in range(maxval+1)] for j in range(N)]
B[0][A[0][1]]=A[0][0]
for x in range(N):
    B[x][0]=0

for i in range(1,N):
    w,v=A[i]
    for j in range(v, maxval+1):
        if (B[i-1][j-v]+w <=W):
            B[i][j]=min(B[i-1][j-v]+w, B[i-1][j])
        else:
            B[i][j]=B[i-1][j]
for j in range(maxval,-1,-1):
    if B[-1][j]!=1e10:
        print j
        break

Submission status: Wrong Answer

Solution code:
N,W=[int(x) for x in raw_input().split()]
A=[]
maxval=0
for i in range(N):
    w,v=[int(x) for x in raw_input().split()]
    A.append([w,v])
    maxval+=v
B=[[ 1e10  for i in range(maxval+1)] for j in range(N)]
B[0][A[0][1]]=A[0][0]

for i in range(1,N):
    w,v=A[i]
    B[i][v]=w
    for j in range(v+1, maxval+1):
        if (B[i-1][j-v]+w <=W):
            B[i][j]=B[i-1][j-v]+w
        else:
            B[i][j]=B[i-1][j]
for j in range(maxval,-1,-1):
    if B[-1][j]!=1e10:
        print j
        break

Submission status: Wrong Answer

Solution code:
N,W=[int(x) for x in raw_input().split()]
A=[]
maxval=0
for i in range(N):
    w,v=[int(x) for x in raw_input().split()]
    A.append([w,v])
    maxval+=v
B=[[ 1e10  for i in range(maxval+1)] for j in range(N)]
B[0][A[0][1]]=A[0][0]

for i in range(1,N):
    w,v=A[i]
    B[i][v]=w
    for j in range(v+1, maxval+1):
        if (B[i-1][j-v]+w <=W):
            B[i][j]=min(B[i-1][j-v]+w, B[i-1][j])
        else:
            B[i][j]=B[i-1][j]
for j in range(maxval,-1,-1):
    if B[-1][j]!=1e10:
        print j
        break

Submission status: Wrong Answer

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

NIL = int(1e18)
MAX = int(1e3)

dp = [NIL]*(MAX+1)
dp[0]= 0

for i in range(1, N+1):
    w, v = wl[i], vl[i]
    for k in reversed(range(MAX+1)):
        if k + v <= MAX and dp[k] != NIL:
            dp[k+v] = min(dp[k+v], dp[k] + w)

ans = 0
for i in reversed(range(MAX+1)):
    if dp[i] <= W:
        ans = i
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def 解():
    input = sys.stdin.readline

    N,W=[int(_) for _ in input().split()]
    dp={0:0}
    for _ in range(N):
        w,v=[int(_) for _ in input().split()]
        #for j in dp.copy():
        for j in sorted(dp.keys(),reverse=True):
            nw = dp[j]+w
            nv = j+v
            if nw <= W :
                if nv in dp:
                    if nw < dp[nv]:
                        dp[nv] = nw
                else:
                    dp[nv] = nw

    print(max(dp.keys()))

Submission status: Wrong Answer

Solution code:
n, W = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(n)]
dp = [float("inf") for _ in range(1000*n+1)]
dp[0] = 0
#dp[j]: 価値jにするのに必要な重さ(Wを超えないように記録) (i回遷移)
for i in range(n):
	for v in range(t[i][1], 1000*n+1):
		if dp[v - t[i][1]] + t[i][0] <= W:
			dp[v] = min(dp[v], dp[v - t[i][1]] + t[i][0])
		
ans = 0
for v in range(1000*n+1):
	if dp[v] <= W:
		ans = v

print(ans)

Submission status: Wrong Answer

Solution code:
n, W = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(n)]
dp = [[float("inf") for _ in range(1000*n+1)] for _ in range(n+1)]
dp[0][0] = 0
#dp[i][j]: i個目まで選んで価値jにするのに必要な重さ(Wを超えないように記録)
for i in range(n):
	for v in range(1000*n+1):
		if dp[i][v] <= W:
			dp[i+1][v] = dp[i][v]
		#dp[i+1][v] = dp[i][v]
		if dp[i][v] + t[i][0] <= W:
			dp[i+1][v + t[i][1]] = min(dp[i+1][v + t[i][1]], dp[i][v] + t[i][0])

		

#print(dp[1][30], dp[2][30])
#print(dp)

ans = 0
for v in range(1000*n+1):
	if dp[-1][v] <= W:
		ans = v

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def 解():
    input = sys.stdin.readline

    N,W=[int(_) for _ in input().split()]
    dp={0:0}
    for i in range(N):
        w,v=[int(_) for _ in input().split()]
        for j in sorted(dp.keys()):
            if dp[j]+w <= W:
                if j+v in dp:
                    dp[j+v] = min(dp[j+v],dp[j]+w)
                else:
                    dp[j+v] = dp[j]+w
    print(max(dp.keys()))
解()

Submission status: Wrong Answer

Solution code:
import sys
def 解():
    input = sys.stdin.readline

    N,W=[int(_) for _ in input().split()]
    dp={0:0}
    for i in range(N):
        w,v=[int(_) for _ in input().split()]
        for j in dp.copy():
            if dp[j]+w <= W:
                if j+v in dp:
                    dp[j+v] = min(dp[j+v],dp[j]+w)
                else:
                    dp[j+v] = dp[j]+w

    print(max(dp.keys()))
解()

Submission status: Wrong Answer

Solution code:
# D knap sack 2
from math import isinf

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())
    
inf = float('inf')
# dp tabel -> dp list
dp = [inf]*(1000+1) 
dp[0]  = 0
for i in range(N):
    for j in reversed(range(1000+1)):
        if j-v[i]<0 or dp[j-v[i]] + w[i] > W:
            dp[j] = dp[j]
        else:
            dp[j] = min(dp[j],
                        dp[j-v[i]] + w[i])
    # print(dp[:100])

ans = 0
for value,dpi in enumerate(dp):
    if dpi<=W:
        ans = max(ans, value)
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect
def inpl(): return list(map(int, input().split()))

N, L = inpl()
DP = [1e9]*(10**5 + 2)
DP[0] = 0
for i in range(N):
    DP2 = [1e9]*(10**5 + 2)
    w, v = inpl()

    for i in range(10**5, v-1, -1):
        DP2[i] = min(DP[i-v] + w, DP[i], DP2[i+1])
    for i in range(v-1, -1, -1):
        DP2[i] = min(DP[i], DP2[i+1])
    DP = DP2
print(bisect(DP, L)-1)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
dp = [[1000000001 for i in range(N*10000+1)] for j in range(N+1)]
dp[0][0] = 0
for j in range(N):
    w, v = map(int, input().split())
    for k in range(N*100+1):
        dp[j+1][k] = min(dp[j][k-v] + w, dp[j][k])
ans = 0
for i in range(N*10000+1):
    if dp[N][i] <= W:
        ans = max(ans, i)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,w = li()
wv = []
for _ in range(n):
    wv.append(tuple(li()))
    
MAX = 10**15
SIZE = 10**2+1
UPPER = 10**12
    
dp = [[MAX]*SIZE for _ in range(n+1)]
for item in range(n):
    dp[item][0] = 0

for item in range(n):
    wi, vi = wv[item]
    for value in range(1, SIZE):
        if value - vi >= 0:
            if 0 <= dp[item][value-vi] + wi <= w:
                dp[item+1][value] = min(dp[item][value],
                                        dp[item][value-vi] + wi)
                
            else:
                dp[item+1][value] = dp[item][value]
            
        else:
            dp[item+1][value] = dp[item][value]
        

ans = 0
for value in range(SIZE):
    if dp[n][value] <= UPPER:
        ans = max(ans, value)
        
print(ans)

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(N)]
V=10**3

DP_V=[float("inf")]*(V*N+1)
DP_V[0]=0
for i in range(N):
    for j in range(V*N,-1,-1):
        if j+WV[i][1]<V*N-1:
            DP_V[j+WV[i][1]]=min(DP_V[j+WV[i][1]],DP_V[j]+WV[i][0])

for i in range(V*N,-1,-1):
    if DP_V[i]<=W:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
V = 10**5
INF = 10**18
dp = [INF]*(V+1)

dp[0] = 0
for i in range(N):
    w, v = map(int, input().split())
    for j in range(V, v-1, -1):
        if dp[j-v] + w <= W:
            dp[j] = min(dp[j], dp[j-v] + w)
for i in range(V-1, -1, -1):
    if dp[i] < INF:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
V = 10**5
INF = 10**18
dp = [INF]*(V+1)

dp[0] = 0
for i in range(N):
    w, v = map(int, input().split())
    for j in range(V-1, v-1, -1):
        if dp[j-v] + w <= W:
            dp[j] = min(dp[j], dp[j-v] + w)
for i in range(V-1, -1, -1):
    if dp[i] < INF:
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:
weights, values = [], []

n, w = list(map(int, input().split()))
for _ in range(n):
    w_c, v_c = list(map(int, input().split()))
    weights.append(w_c)
    values.append(v_c)

dp = [[0 for i in range(w + 1)] for i in range(n + 1)]
for i in range(len(values) + 1):
    for j in range(w + 1):
        if i == 0 or j == 0: 
            dp[i][j] = 0
        elif weights[i - 1] <= j:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
        else:
            dp[i][j] = dp[i - 1][j]
    
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(n)]
sum_v = sum(wv[i][1] for i in range(n))
sum_w = sum(wv[i][0] for i in range(n))

dp = [[sum_w + 1] * (sum_v + 1) for i in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    for j in range(sum_v + 1):
        if j - wv[i][1] >= 0:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - wv[i][1]] + wv[i][0])
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    MAX_V = 100100
    MAX_N = 110
    INF = 10 ** 9 + 1
    n, w = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(n)]

    dp = [[INF] * 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 - wv[i][1]) >= 0:
                dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v - wv[i][1]] + wv[i][0])
            dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v])

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

    print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    MAX_N = 100
    INF = 10 ** 9 + 1
    n, w = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(n)]
    MAX_V = sum([_[1] for _ in wv]) + 10

    dp = [[INF] * 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 - wv[i][1]) >= 0:
                dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v - wv[i][1]] + wv[i][0])
            dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v])

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

    print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_e
import sys
N, W = map(int, input().split())
ws = []
vs = []
totalV = 0
for _ in range(N):
    w, v = map(int, input().split())
    ws.append(w)
    vs.append(v)
    totalV += v
dp = [[0 for _ in range(totalV + 1)] for _ in range(N + 1)]

for i in range(1, totalV + 1):
    dp[0][i] = sys.maxsize

for i in range(1, N + 1):
    for j in range(1, totalV + 1):
        dp[i][j] = dp[i - 1][j]
        if j - vs[i - 1] >= 0:
            # dp[i][j] := min weight to achive vs[i - 1] using ws[0] ~ ws[j - 2]
            dp[i][j] = min(dp[i][j], dp[i - 1][j - vs[i - 1]] + ws[i - 1])
ans = 0
for i in range(1, totalV + 1):
    if dp[N][i] <= W:
        ans = max(ans, i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys  import stdin,stdout

st=lambda:list(stdin.readline().strip())
li=lambda:list(map(int,stdin.readline().split()))
mp=lambda:map(int,stdin.readline().split())
inp=lambda:int(stdin.readline())
pr=lambda n: stdout.write(str(n)+"\n")

mod=1000000007
INF=float('inf')

def knapSack(W, wt, val, n): 
    K = [[0 for x in range(W + 1)] for x in range(n + 1)] 
  
    # Build table K[][] in bottom up manner 
    for i in range(n + 1): 
        for w in range(W + 1): 
            if i == 0 or w == 0: 
                K[i][w] = 0
            elif wt[i-1] <= w: 
                K[i][w] = max(val[i-1]  + K[i-1][w-wt[i-1]],  K[i-1][w]) 
            else: 
                K[i][w] = K[i-1][w] 
  
    return K[n][W] 
    

x=[]
y=[]
n,w=mp()
for i in range(n):
    a,b=mp()
    x.append(a)
    y.append(b)

print(knapSack(w,x,y,n))

Submission status: Time Limit Exceeded

Solution code:
def li():
    return [int(x) for x in input().split()]


INF = 10 ** 60

N, W = li()
L = [li() for i in range(N)]
V = 10 ** 5
# W <= 10**9 なので、
# dp[i][w]: i番目の選択で重さwだった時の価値の最大値、は計算量厳しい
# dp[i][v]: i番目の選択で価値vだった時の重さの最小値、で考えて重さの最小値がW以下のものから最大価値を算出する

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

# 初期条件
# 選ばない
dp[0][0] = 0
# 選ぶ
w0, v0 = L[0]
dp[0][v0] = w0

for i in range(1, N):
    for v in range(V+1):
        cw, cv = L[i]
        # 選ばない
        dp[i][v] = min(dp[i][v], dp[i-1][v])
        # 選ぶ
        if v + cv > V:
            continue
        dp[i][v+cv] = min(dp[i][v+cv], dp[i-1][v] + cw)

# 重さの最小値がW以下で達成できるvの最大値
v_max = 0
for v in range(V+1):
    if dp[N-1][v] <= W:
        v_max = v
print(v_max)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def main():
    import numpy as np

    np.set_printoptions(linewidth=200)

    N, W = map(int, input().split())
    lst = [list(map(int, input().split())) for _ in range(N)]
    v_max = 10 ** 3 * 100 * 10
    w_max = 10 ** 9 * v_max
    # v_max = 150
    # v_max = 30

    # i以上の価値を持つときの最小重量
    dp = np.full((N + 1, v_max), w_max, dtype=np.int64)
    # initialize
    # w, v = lst[0]
    # dp[0][v:] = w
    dp[0][0] = 0
    for n in range(N):
        w, v = lst[n]
        dp[n + 1, v:] = np.minimum(dp[n + 1, v:], dp[n, :-v] + w)
        dp[n + 1, :] = np.minimum(dp[n + 1, :], dp[n, :])

    ans = 0
    for i, w in enumerate(dp[-1]):
        if w <= W:
            ans = i
    print(ans)
    # print(dp)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

import sys
input = sys.stdin.readline

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

nap = []
sum_values = 0
for i in range(N):
    w1,v1  = map(int,input().split())
    nap.append([w1,v1])
    sum_values += v1

INF = 10**15
dp = list([INF for _ in range(sum_values+1)] for _ in range(N+1))
dp[0][0] = 0

for i in range(N):
    w1, v1 = nap[i]
    for j in range(sum_values+1):
        if j - v1 >= 0:
            dp[i+1][j] = min (dp[i][j] , dp[i][j-v1] + w1 )
        else:
            dp[i+1][j] = min(dp[i][j],dp[i+1][j])
ans = 0

for j in range(sum_values+1):
    if dp[N][j] <= W:
        ans = j

print(ans)

Submission status: Time Limit Exceeded

Solution code:


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

nap = []
sum_values = 0
for i in range(N):
    w1,v1  = map(int,input().split())
    nap.append([w1,v1])
    sum_values += v1

INF = 10**15
dp = list([INF for _ in range(sum_values+1)] for _ in range(N+1))
dp[0][0] = 0

for i in range(N):
    w1, v1 = nap[i]
    for j in range(sum_values+1):
        if j - v1 >= 0:
            dp[i+1][j] = min (dp[i][j] , dp[i][j-v1] + w1 )
        else:
            dp[i+1][j] = min(dp[i][j],dp[i+1][j])
ans = 0

for j in range(sum_values+1):
    if dp[N][j] <= W:
        ans = j

print(ans)

Submission status: Time Limit Exceeded

Solution code:


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

INF = 10**15
dp = list([INF for _ in range(100010)] for _ in range(N+1))
dp[0][0] = 0

nap = []
for i in range(N):
    w1,v1  = map(int,input().split())
    nap.append([w1,v1])

for i in range(N):
    w1, v1 = nap[i]
    for j in range(100010):
        if j - v1 >= 0:
            dp[i+1][j] = min (dp[i][j] , dp[i][j-v1] + w1 )
        else:
            dp[i+1][j] = min(dp[i][j],dp[i+1][j])
ans = 0
for j in range(100001):
    if dp[N][j] <= W:
        ans = j

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

DP = [[math.inf] * 100001 for _ in range(N+1)]
DP[0][0] = 0
for i in range(1, N+1):
    w, v = map(int, input().split())
    for j in range(100001):
        if j >= v:
            DP[i][j] = min(DP[i-1][j], DP[i-1][j-v]+w)
        else:
            DP[i][j] = DP[i-1][j]

ans = 100000
while DP[N][ans] > W:
    ans -= 1
print(ans)