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 .

Solution (Python):
N, W = map(int, input().split())
wv = [[0 for i in range(2)] for j in range(N)]

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

dp = [[10**10 for i in range(10**5+100)] for j in range(150)]
dp[0][0] = 0

for i in range(N):
    for j in range(10**5+100):
        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 i in range(10**5+100):
    if dp[N][i] <= W: 
        ans = i
print(ans)

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    N, W = tuple(map(int, input().rstrip().split()))
    A = tuple(tuple(map(int, input().rstrip().split())) for _ in range(N))
    lim = 10 ** 5
    dp = [0] + [float("inf")] * lim
    for i in range(N):
        for j in range(lim, A[i][1] - 1, -1):
            dp[j] = min(dp[j], dp[j - A[i][1]] + A[i][0])
    ans = [i for i, j in enumerate(dp) if j <= W]
    print(max(ans))


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    N, W = tuple(map(int, input().rstrip().split()))
    A = tuple(tuple(map(int, input().rstrip().split())) for _ in range(N))
    _, V = zip(*A)
    lim = 10 ** 5
    dp = [0] + [float("inf")] * lim
    for i in range(N):
        for j in range(lim, A[i][1] - 1, -1):
            dp[j] = min(dp[j], dp[j - A[i][1]] + A[i][0])
    ans = [i for i, j in enumerate(dp) if j <= W]
    print(max(ans))


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    N, W = tuple(map(int, input().rstrip().split()))
    A = tuple(tuple(map(int, input().rstrip().split())) for _ in range(N))
    _, V = zip(*A)
    lim = sum(V)  
    dp = [0] + [float("inf")] * lim
    for i in range(N):
        for j in range(lim, A[i][1] - 1, -1):
            dp[j] = min(dp[j], dp[j - A[i][1]] + A[i][0])
    ans = [i for i, j in enumerate(dp) if j <= W]
    print(max(ans))


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    n, W = tuple(map(int, input().rstrip().split()))
    A = tuple(tuple(map(int, input().rstrip().split())) for _ in range(n))
    _, v = zip(*A)
    lim = sum(v)
    dp = [0] + [float("inf")] * lim
    for i in range(n):
        for j in range(lim, A[i][1] - 1, -1):
            dp[j] = min(dp[j], dp[j - A[i][1]] + A[i][0])
    ans = max(v for v, w in enumerate(dp) if w <= W)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

n,w = map(int,input().split())
wv = [tuple(map(int,input().split())) for i in range(n)]

dp = [0] + [float("inf")]*(10**5)
for i in range(n):
    for j in range(10**5,wv[i][1]-1,-1):
        dp[j] = min(dp[j],dp[j-wv[i][1]]+wv[i][0])

res = 0
for v,e in enumerate(dp):
    if e <= w:
        res = v
print(res)

Solution (Python):
def main():
  n, w = [int(e) for e in input().split()]
  maxv = 10 ** 3 * n + 1
  t = [-1 for i in range(maxv)]
  t[0] = w
  cmaxv = 0
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(cmaxv, -1, -1):
      if t[i] == -1:
        continue
      if t[i + nv] < t[i] - nw:
        t[i + nv] = t[i] - nw
        if cmaxv < i + nv:
          cmaxv = i + nv
  print(cmaxv)
main()

Solution (Python):
def main():
  n, w = [int(e) for e in input().split()]
  maxv = 10 ** 3 * n + 1
  t = [-1 for i in range(maxv)]
  t[0] = w
  cmaxv = 0
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(cmaxv, -1, -1):
      if t[i] == -1:
        continue
      if t[i + nv] < t[i] - nw:
        t[i + nv] = t[i] - nw
        if cmaxv < i + nv:
          cmaxv = i + nv
  print(cmaxv)
main()

Solution (Python):
def main():
  n, w = [int(e) for e in input().split()]
  maxv = 10 ** 3 * n + 1
  t = [-1 for i in range(maxv)]
  t[0] = w
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(maxv - 1, -1, -1):
      if t[i] == -1:
        continue
      if t[i + nv] < t[i] - nw:
        t[i + nv] = t[i] - nw
  for i in range(maxv - 1, 0, -1):
    if t[i] == -1:
      continue
    print(i)
    break
main()

Solution (Python):
def main():
  n, w = [int(e) for e in input().split()]
  maxv = 10 ** 3 * n + 1
  t = [-1 for i in range(maxv)]
  t[0] = w
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(maxv - 1, -1, -1):
      if t[i] == -1:
        continue
      if t[i + nv] < t[i] - nw:
        t[i + nv] = t[i] - nw
  for i in range(maxv - 1, 0, -1):
    if t[i] == -1:
      continue
    print(i)
    break
main()

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



dp = [{} for i in range(N+1)]
dp[0][0] = 0


for i, (w,v) in enumerate(wv):
    for v0, w0 in dp[i].items(): 
        if v0 in dp[i+1]: 
            dp[i+1][v0] = min(dp[i+1][v0], w0) 
        else:
            dp[i+1][v0] = w0 
        
        if w0+w > W: 
            continue 
        if v0+v in dp[i+1]: 
            dp[i+1][v0+v] = min(dp[i+1][v0+v], w0+w)
        else:
            dp[i+1][v0+v] = w0+w


print(max(dp[-1].keys()))

Solution (Python):
import numpy as np

n, ww = map(int, input().split())

s = np.full(1000*100+1, 10**11, dtype=np.int64)
s[0] = 0
for i in range(n):
    w, v = map(int, input().split())
    s[v:] = np.minimum(s[v:], s[:-v] + w)

print(np.max(np.where(s<=ww)))

Solution (Python):
n, w = map(int, input().split())
item = [list(map(int, input().split())) for i in range(n)]

max_v = 100005

dp = [[float('inf')] * max_v for j in range(n + 1)]
dp[0][0] = 0

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

for sum_v in reversed(range(max_v)):
    if dp[-1][sum_v] <= w:
        print(sum_v)
        break

Solution (Python):
def solve():
    max_weight, list_of_weight_and_value = read()
    result = think(max_weight, list_of_weight_and_value)
    write(result)


def read():
    n, max_weight = read_int(2)
    list_of_weight_and_value = []
    for i in range(n):
        list_of_weight_and_value.append(read_int(2))
    return max_weight, list_of_weight_and_value


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(max_weight, list_of_weight_and_value):
    MAX_WEIGHT = 10 ** 9
    MAX_VALUE = 10 ** 3
    MAX_N = 100
    INVALID_VALUE = MAX_WEIGHT * MAX_N + 1

    
    dp = [INVALID_VALUE for x in range(MAX_VALUE * len(list_of_weight_and_value) + 1)]
    dp[0] = 0

    for weight, value in list_of_weight_and_value:
        for i in range(len(dp) - 1, -1, -1):
            if dp[i] != INVALID_VALUE and i + value < len(dp):
                if dp[i + value] == INVALID_VALUE:
                    dp[i + value] = dp[i] + weight
                else:
                    dp[i + value] = min(dp[i + value], dp[i] + weight)
    for i in range(len(dp) - 1, -1, -1):
        if dp[i] != INVALID_VALUE and dp[i] <= max_weight:
            return i


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Solution (Python):
def number():
    return int(input())


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


def seq_space(n):
    return [list(map(int, input().split())) for _ in range(n)]


N, W = space()
WV = seq_space(N)

V = N*1000+1
DP = [float('inf')] * V
DP[0] = 0

for i in range(N):
    w, v = WV[i]
    for j in range(V-1, v-1, -1):
        DP[j] = min(DP[j-v]+w, DP[j])

for i in range(V-1, -1, -1):
    if DP[i] <= W:
        print(i)
        exit()

Solution (Python):
N,W = map(int,input().split())
wv = list(list(map(int,input().split()))for i in range(N))

DP = [[float("inf")]*(N*(10**3)+1)for i in range(N+1)]
DP[0][0] = 0
for i in range(N):
    w,v = wv[i]
    for j in range(N*10**3+1):
        if j < v:
            DP[i+1][j] = DP[i][j]
        else:
            DP[i+1][j] = min(DP[i][j],DP[i][j-v]+w)
ans = 0

for i in range(N*10**3+1):
    if DP[-1][i] <= W:
        ans = i
print(ans)

Solution (Python):
n,W=map(int,input().split())
wv=[]
m=1
for i in range(n):
    p=[int(j) for j in input().split()]
    wv.append(p)
    m+=p[1]

dp=[10**100 for i in range(m)]
dp[0]=0

for i in range(n):
    w,v=wv[i][0],wv[i][1]
    for j in range(m):
        if dp[-1-j]!=10**100:
            dp[-1-j+v]=min(dp[-1-j+v],dp[-1-j]+w)

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

Solution (Python):
import numpy as np

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

dp = np.full(N*1000+1, 10 ** 10, dtype=np.int64)
dp[0] = 0
for n in range(1, N+1):
    weight, value = inputs[n-1][0], inputs[n-1][1]
    dp[value:] = np.minimum(dp[value:], dp[:-value] + weight)

print(np.max(np.where(dp <= W)))

Solution (Python):
N, W = map(int, input().split())
Ls = [tuple(map(int, input().split())) for _ in range(N)]

INF = float("inf")
dp = [INF] * (10 ** 5 + 1)
dp[0] = 0

mv = 0
for m, v in Ls:
    mv += v
    for i in range(mv, v - 1, -1):
        dp[i] = min(dp[i], dp[i - v] + m)

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

Solution (Python):
n,k = map(int,input().split())
mx = 100000
dp = [[k+1 for _ in range(mx+1)]for _ in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
    dp[i][0]= 0
    w,v = map(int,input().split())
    for j in range(v):
        dp[i][j]= dp[i-1][j]
    for j in range(v,mx+1):
        next = w+dp[i-1][j-v]
        if next<=k:
            dp[i][j]= min(next,dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
for i in range(mx,-1,-1):
    if dp[n][i]<=k:
        print(i)
        break

Solution (Python):
import math
import sys

N,W = map(int, sys.stdin.readline().split())

items= [list(map(int, sys.stdin.readline().split()) )for _ in range(N)]
s  =0
for i in range(N):
    s += items[i][1]
INF = 10 **15
dp = [[ INF for _ in range(s +1)] for _ in range(N + 1) ]

dp[0][0] = 0

for j in range(N):  
    for i in range(s + 1): 

        w,v = items[j]
        if i >= v:
        
            dp[j + 1 ][i] = dp[j][i - v]  + w  
        dp[j + 1][i] =  min(dp[j + 1][i] ,dp[j][i]) 
ans = 0
for i in range(s + 1): 
    for j in range(N + 1):  
        if dp[j][i] <= W:
            ans = max(i,ans)

print(ans)

Solution (Python):
n,w=map(int,input().split())
dp=[[100000000001]*100001for _ in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
  a,b=map(int,input().split())
  for j in range(100001):
    if j>=b:dp[i][j]=min(dp[i-1][j],dp[i-1][j-b]+a)
    else:dp[i][j]=dp[i-1][j]
i=10**5
while dp[n][i]>w:i-=1
print(i)

Solution (Python):
N,W = map(int,input().split())
L = []
for _ in range(N):
    A,B = map(int,input().split())
    L.append((A,B))

dp = [[10**12+1 for i in range(10 ** 5 + 100)] for i in range(N + 10)]

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


for j in reversed(range(10** 5 + 10)):
    if dp[N][j] != 10**12 + 1:
        print(j)
        quit()

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

IN = list(list(map(int, input().split())) for _ in range(N))
sumw = 0
sumv = 0
for w, v in IN:
    sumw += w
    sumv += v

DP = dict()
DP[sumv] = sumw

def minv(i, v):
    if not DP.get(i):
        DP[i] = v
    else:
        if v < DP[i]:
            DP[i] = v

for w, v in IN:
    DPpre = DP.copy()
    for i in DPpre:
        minv(i-v, DPpre[i]-w)

for v in sorted(DP, reverse=True):
    if DP[v] <= W:
        print(v)
        break

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

IN = list(list(map(int, input().split())) for _ in range(N))
sumw = 0
sumv = 0
for w, v in IN:
    sumw += w
    sumv += v

DP = dict()
DP[sumv] = sumw

def minv(i, v):
    if not DP.get(i):
        DP[i] = v
    else:
        if v < DP[i]:
            DP[i] = v

if sumw <= W:
    ans = sumv
else:
    ans = 0
    for w, v in IN:
        DPpre = DP.copy()
        for i in DPpre:
            answ = i - v
            minv(answ, DPpre[i]-w)
            if answ > ans:
                if DP[answ] <= W:
                    ans = answ
                    continue

print(ans)

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

IN = list(list(map(int, input().split())) for _ in range(N))
sumw = 0
sumv = 0
for w, v in IN:
    sumw += w
    sumv += v

DP = dict()
DP[sumv] = sumw

def minv(i, v):
    if not DP.get(i):
        DP[i] = v
    else:
        if v < DP[i]:
            DP[i] = v

if sumw <= W:
    ans = sumv
else:
    ans = 0
    for w, v in IN:
        DPpre = DP.copy()
        for i in DPpre:
            answ = i - v
            minv(answ, DPpre[i]-w)
            if answ > ans:
                if DP[answ] <= W:
                    ans = answ
                    continue

print(ans)

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

IN = list(list(map(int, input().split())) for _ in range(N))
sumw = 0
sumv = 0
for w, v in IN:
    sumw += w
    sumv += v

DP = dict()
DP[sumv] = sumw

def minv(i, v):
    if not DP.get(i):
        DP[i] = v
    else:
        if v < DP[i]:
            DP[i] = v

for w, v in IN:
    DPpre = DP.copy()
    for i in DPpre:
        minv(i-v, DPpre[i]-w)

for v in sorted(DP, reverse=True):
    if DP[v] <= W:
        print(v)
        break

Solution (Python):
if __name__ == '__main__':
    n, w = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(n)]

    sum_value = sum([v for (_, v) in wv])

    dp = [[10**9 + 7 for _ in range(sum_value + 1)] for _ in range(n + 1)]

    dp[0][0] = 0

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

    a = sorted(range(sum_value + 1), reverse = True)

    for i in a:
        if dp[n][i] <= w:
            print(i)
            break

Solution (Python):
n, w = map(int, input().split())
weight = []
value = []

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




dp = [[10 ** 9 + 7 for i in range(sum(value) + 1)] for j in range(n + 1)]

dp[0][0] = 0

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

        else:
            dp[i + 1][j] = dp[i][j]

a = sorted(range(sum(value) + 1), reverse = True)

for i in a:
    if dp[n][i] <= w:
        print(i)
        break

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

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

for i in range(N):
    for sum_v in range(10**5+1):
        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])

res = 0
for sum_v in range(10**5+1):
    if dp[N][sum_v] <= W:
        res = sum_v

print(res)

Solution (Python):
N, maxW = map(int, input().split())
maxV = 10**3*100
dp = [[float('inf') for i in range(maxV+1)] for j in range(N+1)]
W = [0 for i in range(N+1)]
V = [0 for i in range(N+1)]
for i in range(1, N+1):
    W[i], V[i] = map(int, input().split())

nv = 0
nw = 0
dp[0][0] = 0
for i in range(1, N+1):
    for v in range(maxV+1):
        dp[i][v] = min(dp[i-1][v], dp[i][v])
        nv = v + V[i]
        if nv <= maxV:
            dp[i][nv] = dp[i-1][v] + W[i]
ans = 0
for v in range(maxV, -1, -1):
    if maxW >= dp[N][v]:
        ans = v
        break

print(ans)

Solution (Python):
N,W = map(int,input().split())
wv = list(list(map(int,input().split()))for i in range(N))
DP = [[float('inf')]*(N*1000+1)for i in range(N+1)]
DP[0][0] = 0
for i in range(N):
    w,v = wv[i]
    for j in range(N*1000+1):
        if j < v:
            DP[i+1][j] = DP[i][j] 
        else:
            DP[i+1][j] = min(DP[i][j],DP[i][j-v]+w)
for i in range(len(DP[-1])-1,-1,-1):
    if DP[-1][i] <= W:
        print(i)
        break

Solution (Python):

import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math






def main():
	N, W = map(int, input().split())
	wv = []
	for i in range(N):
		w, v = map(int, input().split())
		wv.append((w,v))
		
	DP = [[1000000000000000000000000 for _ in range(100001)] for _ in range(N)]
	
	for i, val in enumerate(wv):
		w, v = val
		if i == 0:
			DP[i][v] = w
			DP[i][0] = 0
			continue
		
		for j in range(100001):
			DP[i][j] = min(DP[i][j], DP[i-1][j])
			if j+v < 100001:
				DP[i][j+v] = min(DP[i][j+v], DP[i-1][j] + w)
				
	ans = -1
	for i, val in enumerate(DP[N-1]):
		if val <= W:
			
			if ans == -1 or ans < i:
				ans = i
		
	print(ans)
	
	
if __name__ == "__main__":
	main()

Solution (Python):



N,W=list(map(int,input().split()))
items=[]
for _ in range(N):
    w,v=list(map(int,input().strip().split()))
    items+=[(w,v)]
    
MAX_val=N*10**3+1 
dp=[[10**9+1]*MAX_val for i in range(N)] 
dp[0][items[0][1]]=items[0][0] 
for i in range(1,N):
    for val in range(1,MAX_val):
        if val-items[i][1]>0: 
            dp[i][val]=min(dp[i-1][val],dp[i-1][val-items[i][1]]+items[i][0])
        elif val==items[i][1]: 
            dp[i][val]=min(items[i][0],dp[i-1][val])
        dp[i][val]=min(dp[i][val],dp[i-1][val])

MAX=0
for i in range(len(dp[-1])): 
    if dp[-1][i]<=W:
        
        MAX=i
print(MAX)

Solution (Python):
n,w = map(int, input().split())
l = [tuple(map(int, input().split())) for _ in range(n)]
inf = float("inf")
dp = [inf]*(10**5+1)
dp[0] = 0
mv = 0
for x,v in l:
  mv += v
  for i in range(mv,v-1,-1):
    dp[i] = min(dp[i],dp[i-v]+x)
    
for i in range(mv,-1,-1):
  if dp[i]<=w:
    print(i)
    break

Solution (Python):
n,w = map(int,input().split())

lis = [list(map(int,input().split())) for i in range(n)]
lis.sort(key = lambda x:x[1])

dp = {0:0}

for weight ,value in lis:
    gone = dp.copy()
    for key in dp:
        gone[key+value] = min(dp[key] + weight, dp.get(key+value, float("inf")))
    dp = gone
for key in sorted(dp.keys(), reverse = True):
    if dp[key] <= w:
        print(key)
        exit()

Solution (Python):
n,w = map(int,input().split())

lis = [list(map(int,input().split())) for i in range(n)]
lis.sort(key = lambda x:x[1])

dp = {0:0}

for weight ,value in lis:
    gone = dp.copy()
    for key in dp:
        gone[key+value] = min(dp[key] + weight, dp.get(key+value, float("inf")))
    dp = gone
for key in sorted(dp.keys(), reverse = True):
    if dp[key] <= w:
        print(key)
        exit()

Solution (Python):



def main():
    n, w = map(int, input().split())
    ws = [0 for _ in range(n)]
    vs = [0 for _ in range(n)]
    inf = 10 ** 12
    dp = [[inf for _ in range(((n + 1) * 10 ** 3) + 1)] for _ in range(n + 1)]

    for i in range(n):
        wi, vi = map(int, input().split())
        ws[i] = wi
        vs[i] = vi

    dp[0][0] = 0

    for i in range(n):
        for sum_v in range(((n + 1) * 10 ** 3) + 1):
            if sum_v - vs[i] >= 0:
                dp[i + 1][sum_v] = min(dp[i + 1][sum_v],
                                       dp[i][sum_v - vs[i]] + ws[i])

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

    ans = 0

    for index, d in enumerate(dp[n]):
        if d <= w:
            ans = index

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):




import sys
def LI(): return list(map(int, sys.stdin.readline().split()))
def LIR(n): return [LI() for _ in range(n)]
def e():
    n,W = LI()
    wv = LIR(n)

    
    dp = [[float("inf") for _ in range(10**5+1)] for _ in range(n+1)]
    dp[0][0] = 0
    for i in range(1,n+1):
        for j in range(10**5+1):
            
            if j < wv[i-1][1]:
                
                dp[i][j] = dp[i-1][j]
            else:
                
                dp[i][j] = min(dp[i-1][j],dp[i-1][j - wv[i-1][1]] + wv[i-1][0])
    ans = 0
    
    for i in range(10**5+1):
        if dp[n][i] <= W:
            ans = i
    print(ans)
if __name__ == '__main__':
    e()

Solution (Python):





def e():
    n,W = map(int,input().split())
    wv = [list(map(int,input().split())) for _ in range(n)]
    
    dp = [[float("inf") for _ in range(10**5+1)] for _ in range(n+1)]
    dp[0][0] = 0
    for i in range(1,n+1):
        for j in range(10**5+1):
            
            if j < wv[i-1][1]:
                
                dp[i][j] = dp[i-1][j]
            else:
                
                dp[i][j] = min(dp[i-1][j],dp[i-1][j - wv[i-1][1]] + wv[i-1][0])
    ans = 0
    
    for i in range(10**5+1):
        if dp[n][i] <= W:
            ans = i
    print(ans)
if __name__ == '__main__':
    e()

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
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,W = inpl()
wvs = [inpl() for _ in range(N)]
dp = [INF]*(10**5+5)
dp[0] = 0

for w,v in wvs:
    for i in reversed(range(10**5+5)):
        dp[i] = min(dp[i-v] + w,dp[i])
        if i == v:
            break
ans = 0
for i in range(10**5+5):
    if dp[i] <= W:
        ans = i

print(ans)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
def factorial(n):
    if (n==0) or (n==1):
        return 1
    ret = 1
    for i in range(2, n+1):
        ret *= i
    return ret
def combination(n, k):
    return factorial(n)//factorial(k)//factorial(n-k)
sys.setrecursionlimit(1000000)
INF = float("inf")
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N, W = LI()
wv = LIR(N)
V = sum(list(map(lambda x: x[1], wv)))

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

for i in range(N):
    w, v = wv[i]
    for j in range(V+1):
        if (j < v):
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i][j-v] + w)

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

Solution (Python):
N,W=list(map(int,input().strip().split(" ")))
items=[]
for _ in range(N):
    w,v=list(map(int,input().strip().split(" ")))
    items+=[(w,v)]

MAX_val=N*10**3+1
dp=[[10**9+1]*MAX_val for i in range(N)]
dp[0][items[0][1]]=items[0][0]
for i in range(1,N):
    for val in range(1,MAX_val):
        if val-items[i][1]>0:
            dp[i][val]=min(dp[i-1][val],dp[i-1][val-items[i][1]]+items[i][0])
        elif val==items[i][1]:
            dp[i][val]=min(items[i][0],dp[i-1][val])
        dp[i][val]=min(dp[i][val],dp[i-1][val])

MAX=0
for i in range(len(dp[-1])):
    if dp[-1][i]<=W:
        
        MAX=i
print(MAX)

Solution (Python):
from __future__ import division, print_function
def main():
    dp=[10**18]*(10**5+1)
    dp[0]=0
    n,w=map(int,input().split())
    l1=[]
    s=0
    for _ in range(n):
        l1.append(list(map(int,input().split())))
        s+=l1[_][1]
    for i in range(n):
        for j in range(s,l1[i][1]-1,-1):
            dp[j]=min(dp[j],dp[j-l1[i][1]]+l1[i][0])
    for j in range(10**5,-1,-1):
        if dp[j]<=w:
            print(j)
            sys.exit()











py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
sys.setrecursionlimit(10**5)
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')


import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'


def readnumbers(zero = 0):
    conv = ord if py2 else lambda x:x
    A = []; numb = zero; sign = 1; i = 0; s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'0' [0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-' [0]: sign = -1
            elif s[i] != b'\r' [0]:
                A.append(sign*numb)
                numb = zero; sign = 1
            i += 1
    except:pass
    if s and s[-1] >= b'0' [0]:
        A.append(sign*numb)
    return A

if __name__== "__main__":
  main()

Solution (Python):


import sys

class EKnapsack2:
    def solve(self):
        n, W = [int(_) for _ in input().split()]
        w = [0] * (n + 1)
        v = [0] * (n + 1)
        for i in range(1, n + 1):
            w[i], v[i] = [int(_) for _ in input().split()]

        V = sum(v)
        dp = [[float('inf')] * (n + 1) for _ in range(V + 1)]

        for ve in range(V + 1):
            dp[0][0] = 0
            for k in range(1, n + 1):
                dp[ve][k] = dp[ve][k - 1]
                if ve >= v[k]:
                    dp[ve][k] = min(dp[ve][k], dp[ve - v[k]][k - 1] + w[k])

        ans = 0
        for ve in range(V + 1):
            if dp[ve][n] <= W:
                ans = ve

        print(ans)

solver = EKnapsack2()
input = sys.stdin.readline

solver.solve()

Solution (Python):
inf = float('inf')

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

M = sum(v)

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

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

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

print(ans)

Solution (Python):

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

wv = []
vmax = 0

for i in range(N):

    w,v = map(int,input().split())

    vmax += v
    wv.append([w,v])


lis = [[0] + [float("inf")] * vmax]

for i in wv:

    new = [0] + [float("inf")] * vmax

    for j in range(vmax+1):

        new[j] = min(new[j] , lis[-1][j])

        if j + i[1] <= vmax:

            new[j + i[1]] = min (new[j + i[1]] , lis[-1][j] + i[0])

    lis.append(new)



lis[-1].reverse()

for i in range(vmax+1):

    if lis[-1][i] <= W:
        print (vmax - i)
        break

Solution (Python):
N, W = map(int, input().split())
INF = float('inf')
weight = [0] * N
value = [0] * N
Max_v = 0
for i in range(N):
    w, v = map(int, input().split())
    weight[i], value[i] = w, v
    Max_v += v

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


for i in range(0, value[0]+1):
    dp[0][i] = weight[0] if i else 0

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

for i in reversed(range(Max_v+1)):
    if dp[N-1][i] <= W:
        print(i)
        break

Solution (Python):
N, W = map(int, input().split())
INF = float('inf')
weight = [0] * N
value = [0] * N
Max_v = 0
for i in range(N):
    w, v = map(int, input().split())
    weight[i], value[i] = w, v
    Max_v += v

dp = [[INF]*(Max_v+1) for _ in range(N)]
for i in range(0, value[0]+1):
    dp[0][i] = weight[0] if i else 0

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

for i in reversed(range(Max_v+1)):
    if dp[N-1][i] <= W:
        print(i)
        break

Solution (Python):













import numpy as np

N, W = map(int, input().split())
dp = np.full(N * 1000 + 1, 10 ** 10, 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 + 1)).max())