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())
dp=[[float("inf")]*(10**5+1) for i in range(N+1)]
dp[0][0]=0
for i in range(N):
  w_,v_=map(int,input().split())
  for v in range(10**5+1):
    dp[i+1][v]=min(dp[i][v],dp[i][v-v_]+w_)
for v in range(10**5+1)[::-1]:
  if dp[N][v]<=W:
    print(v)
    exit()

Solution (Python):
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 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()))
解()

Solution (Python):
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

for i in range(n):
	for v in range(1000*n, t[i][1]-1, -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)

Solution (Python):
N, W = map(int, input().split())
goods = [list(map(int, input().split())) for i in range(N)]
v_sum = sum([i[1] for i in goods])
dp = [float("inf") for i in range(v_sum + 1)]
dp[0] = 0
for i in range(N):
    for j in range(v_sum, -1, -1):
        dp[j] = min(dp[j - goods[i][1]] + goods[i][0], dp[j])

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

Solution (Python):
N, W = map(int, input().split())
wlst = []
vlst = []
for _ in range(N):
  w, v = map(int, input().split())
  wlst.append(w)
  vlst.append(v)

max_V = sum(vlst)
INF = 10 ** 20
dp = [INF] * (max_V + 1)
dp[0] = 0
for w, v in zip(wlst, vlst):
  for i in range(max_V, v - 1, -1):
    dp[i] = min(dp[i], dp[i - v] + w)

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

Solution (Python):
N,W=map(int,input().split())
table=[]
for i in range(N):
    w,v=map(int,input().split())
    table.append((w,v))
dp=[[10**22]*(N*(10**3)+1) for i in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
    w,v=table[i-1]
    for j in range(N*(10**3)+1):
        if j-v>=0:
            dp[i][j]=min(dp[i-1][j-v]+w,dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
for j in range(N*(10**3),-1,-1):
    if dp[N][j]<=W:
        print(j)
        break

Solution (Python):
import sys
fin = sys.stdin.readline


MAX_INT = (1 << 63) - 1
N, W = [int(elem) for elem in fin().split()]
weight_value_pairs = tuple(tuple(int(elem) for elem in fin().split()) for _ in range(N))
max_value = max(v for _, v in weight_value_pairs)
max_total_value = N * max_value

dp = [MAX_INT] * (max_total_value + 1)
dp[0] = 0
for i in range(N):
    w, v = weight_value_pairs[i]
    for j in reversed(range(max_total_value + 1)):
        dp[j] = min(dp[j], dp[j - v] + w)

max_val = 0
for val, total_weight in enumerate(dp):
    if total_weight <= W:
        max_val = val
print(max_val)

Solution (Python):
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())
MAX_NV = 100*1000 
inf = float('inf')

dp = [inf]*(MAX_NV+1) 
dp[0]  = 0
for i in range(N):
    for j in reversed(range(MAX_NV+1)):
        if j-v[i]<0:
            dp[j] = dp[j]
        else:
            dp[j] = min(dp[j],
                        dp[j-v[i]] + w[i])
    

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

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

dp = [[0] * (100001) for i in range(N + 1)]
for i in range(1, 100001):
    dp[0][i] = 10 ** 20

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

ans = 0
for i in range(100000, -1, -1):
    if dp[N][i] <= W:
        ans = i
        break

print(ans)

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

N, L = inpl()
DP = [1e10]*(10**5 + 2)
DP[0] = 0
for i in range(N):
    DP2 = [1e10]*(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)

Solution (Python):
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())
V=sum(v)
INF=10**15
dp=[[INF for j in range(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-v[i]>=0:
            dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i],INF)
        else:
            dp[i+1][j]=min(dp[i][j],INF)
b=[]
for i in range(V+1):
    if dp[N][i]!=INF:
        b.append((dp[N][i],i))
ans=0
for (x,y) in b:
    if x<=W:
        ans=max(ans,y)
print(ans)

Solution (Python):
from collections import defaultdict
N, W = [int(i) for i in input().split()]
Things = [[int(i) for i in input().split()] for j in range(N)]

dp = defaultdict(lambda: float('inf'))
dp[0] = 0
for w, v in Things:
    for nv, nw in list(dp.items()):
        if nw + w <= W:
            dp[nv + v] = min(dp[nv + v], nw + w)
ans = 0
for v, w in dp.items():
    if w <= W and v >= ans:
        ans = v
print(ans)

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

dp = [{} for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    w,v = src[i-1]
    for v0,w0 in dp[i-1].items():
        if v0 in dp[i]:
            dp[i][v0] = min(dp[i][v0], w0)
        else:
            dp[i][v0] = w0
        if w0+w > W: continue
        if v0+v in dp[i]:
            dp[i][v0+v] = min(dp[i][v0+v], w0+w)
        else:
            dp[i][v0+v] = w0+w
print(max(dp[-1].keys()))

Solution (Python):
N, W = map(int, input().split())
dp = [[1000000001 for i in range(N*1000+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*1000+1):
        dp[j+1][k] = min(dp[j][k-v] + w, dp[j][k])


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

Solution (Python):
N, W = map(int, raw_input().split())
INF = 0x3f3f3f3f
obj = []
for i in xrange(N):
    w, v = map(int, raw_input().split())
    obj.append((w, v))
dp = [[INF for _ in xrange(100001)] for i in xrange(N)]

w, v = obj[0]
dp[0][0] = 0
dp[0][v] = w
for i in xrange(1, N):
    w, v = obj[i]
    for j in xrange(100001):
        if dp[i-1][j] != INF:
            dp[i][j] = dp[i-1][j]
    for j in xrange(v, 100001):
        if dp[i-1][j-v] != INF and dp[i-1][j-v]+w <= W:
            dp[i][j] = min(dp[i][j], dp[i-1][j-v]+w)
res = 0
for i in xrange(100001):
    if dp[N-1][i] != INF:
        res = i
print res

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


dp = [float('inf')] * (N * 10 ** 3 + 1)
dp[0] = 0

for w, v in Items:
    for i in range(len(dp))[::-1]:
        if i - v < 0:
            continue
        dp[i] = min(dp[i], dp[i - v] + w)

for v, res in zip(range(len(dp))[::-1], dp[::-1]):
    if res <= W:
        print(v)
        exit()

Solution (Python):
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:
            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

Solution (Python):
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**5+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)

Solution (Python):
import sys

n, W = map(int, input().split())
V = n * 1000
dp = {0: 0}
for line in sys.stdin.readlines():
    w, v = map(int, line.split())
    ndp = dp.copy()
    for i, x in dp.items():
        if i + v in dp:
            ndp[i + v] = min(dp[i + v], x + w)
        else:
            ndp[i + v] = x + w
    dp = ndp

print(max(i for i, x in dp.items() if x <= W))

Solution (Python):
import numpy as np
N,W = map(int,input().split())
l = []
for i in range(N):
  y,x =  map(int,input().split())
  l.append((x,y))
V = sum([x[0] for x in l])
dp = np.full((N+1,V+1), np.inf)
dp[0][0]=0
for i in range(N):
  v = l[i][0]
  w = l[i][1]
  dp[i+1]=dp[i]
  dp[i+1][v:] = np.minimum(dp[i][v:],dp[i][:V-v+1]+w)
i = V
while True:
    if dp[N][i] <= W:
      print(i)
      break
    i -= 1

Solution (Python):
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):
    if dp[i] < INF:
        print(i)
        break