Problem:
0-1 Knapsack Problem You have N items that you want to put them into a knapsack. Item i has value v i and weight w i . You want to find a subset of items to put such that:  The total value of the items is as large as possible.  The items have combined weight at most W , that is capacity of the knapsack.  Find the maximum total value of items in the knapsack. Input  N  W  v 1  w 1  v 2  w 2 : v N  w N  The first line consists of the integers N and W . In the following lines, the value and weight of the i -th item are given. Output Print the maximum total values of the items in a line. Constraints  1 ≤ N ≤ 100  1 ≤ v i ≤ 1000  1 ≤ w i ≤ 1000  1 ≤ W ≤ 10000  Sample Input 1 4 5
4 2
5 2
2 1
8 3 Sample Output 1 13 Sample Input 2 2 20
5 9
4 10 Sample Output 2 9

Solution (Python):
N,W = map(int, input().split())
dp = [0]*(W+1)

for i in range(1,N+1):
    v,w = map(int,input().split())
    for j in range(W, w-1, -1):
        x = v+dp[j-w]
        if x > dp[j]: dp[j] = x

print(dp[W])

Solution (Python):
M = {}

N, W = [int(x) for x in input().split()]
items = []
for i in range(N):
    items.append(tuple(int(x) for x in input().split()))


def dfs(i, j):
    if (i, j) in M:
        return M[i, j]
    if i == N:
        return 0

    v, w = items[i]
    if w <= j:
        r = max(dfs(i+1, j), v + dfs(i+1, j-w))
    else:
        r = dfs(i+1, j)
    M[i, j] = r
    return r


print(dfs(0, W))

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


DP = [[0] * (W+1) for _ in range(N+1)]

for i in range(N):
    for j in range(W+1):
        v, w = items[i]
        if w <= j:
            DP[i+1][j] = max(DP[i][j], v + DP[i][j-w])
        else:
            DP[i+1][j] = DP[i][j]

print(DP[-1][-1])

Solution (Python):

N, W = [int(x) for x in input().split()]
items = []
for i in range(N):
    items.append(tuple(int(x) for x in input().split()))

DP = [0] * (W+1)
for i in range(N):
    v, w = items[i]
    for j in range(W, w-1, -1):
        DP[j] = max(DP[j], v + DP[j-w])

print(DP[-1])

Solution (Python):
def main():
    [N,W]=input().split(" ")
    N=int(N)
    W=int(W)
    inputset=[]
    for i in range(N):
        [vi,wi]=input().split(" ")
        inputset.append([int(vi),int(wi)])

    graph=[]
    for i in range(N+1):
        graph.append([])
        for j in range(W+1):
            graph[i].append(0)

    for i in range(N):
        for j in range(W+1):
            if(inputset[i][1]>j):
                graph[i+1][j]=graph[i][j]
            else:
                rest=j-inputset[i][1]
                choosevalue=graph[i][rest]+inputset[i][0]
                nonchoosevalue=graph[i][j]
                if(choosevalue>nonchoosevalue):
                    graph[i+1][j]=choosevalue
                else:
                    graph[i+1][j]=nonchoosevalue

    print(graph[N][W])

main()

Solution (Python):

'''
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=jp
???????¨???????
???????????¶????????????
'''
N, W = map(int, input().split())

class Item():
    def __init__(self, v, w):
        self.v = v
        self.w = w

items = []

for _ in range(N):
    v, w = map(int, input().split())
    item = Item(v, w)
    items.append(item)

C = dict()
for n in range(N+1):
    C[(n, 0)] = 0

for w in range(W+1):
    C[(0, w)] = 0

for n in range(1, N+1):
    for w in range(1, W+1):
        if w-items[n-1].w < 0:
            C[(n, w)] = C[(n-1, w)]
            continue
        C[(n, w)] = max(C[(n-1, w)], C[(n-1, w-items[n-1].w)] + items[n-1].v)

print(C[(n, w)])

Solution (Python):
N,W = raw_input().split()
N=int(N);W=int(W)
v=[]
w=[]
for i in xrange(N):
    vi,wi = raw_input().split()
    vi=int(vi);wi=int(wi)
    v.append(vi)
    w.append(wi)
dp=[[0]*(W+10) for i in xrange(N+10)]
for i in xrange(N):
    for j in xrange(W+1):
        if j>=w[i]:
            dp[i+1][j]=max(dp[i][j-w[i]]+v[i],dp[i][j])
        else:
            dp[i+1][j]=dp[i][j]
print dp[N][W]

Solution (Python):
N,W = map(int,input().split())
val = []
wei = []
for i in range(N):
    a,b = map(int,input().split())
    val.append(a)
    wei.append(b)

dp = [[0 for j in range(W+1)] for i in range(N+1)]


for i in range(N):
    for w in range(W+1):
        if(w >= wei[i]):
            dp[i+1][w] = max(dp[i][w - wei[i]] + val[i],dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]

print(int(dp[N][W]))

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

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

for i in range(N):
    for j in range(W+1):
        if VW[i][1] > j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-VW[i][1]]+VW[i][0])

print(dp[N][W])

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


dp = [0] * (W+1)

for i in range(N):
    for j in range(W, w[i]-1, -1):
        dp[j] = max(dp[j], dp[j-w[i]]+v[i])

print(dp[W])

Solution (Python):



def knapsack(N,W,values,weights):
    dp = [[0 for j in range(W+1)] for i in range(N+1)]

    for i in range(N):
        for w in range(W+1):
            if w >= weights[i]:
                dp[i+1][w] = max(dp[i][w-weights[i]]+values[i], dp[i][w])
            else:
                dp[i+1][w] = dp[i][w]

    return dp[N][W]


tmp = [int(x) for x in input().split()]
N = tmp[0]
W = tmp[1]

values = []
weights = []
for i in range(N):
    tmp = [int(x) for x in input().split()]
    values.append(tmp[0])
    weights.append(tmp[1])

print(knapsack(N,W,values,weights))

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

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

print(dp[N][W])

Solution (Python):



if __name__ == '__main__':

    N, W = map(int, input().split())
    I = [None] + [list(map(int, input().split())) for _ in range(N)]
    C = [[0 for _ in range(W + 1)] for _ in range(N + 1)]

    for i in range(1, N + 1):
        for w in range(1, W + 1):
            if I[i][1] <= w:
                C[i][w] = max(C[i - 1][w - I[i][1]] + I[i][0], C[i - 1][w])
            else:
                C[i][w] = C[i - 1][w]

    print(C[N][W])

Solution (Python):
N, W = map(int, input().split())
dp = [[0] * (W+1) for _ in range(N+1)]
weights = list()
values = list()
for _ in range(N):
    v, w = map(int, input().split())
    values.append(v)
    weights.append(w)

for i in range(N):
    for w in range(W+1):
        if w >= weights[i]: 
            dp[i+1][w] = max(dp[i][w-weights[i]] + values[i], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]

print(dp[N][W])

Solution (Python):
N, W = map(int, input().split())
dp = [[0] * (W+1) for _ in range(N)]
weights = list() 
values = list() 
for _ in range(N):
    v, w = map(int, input().split())
    values.append(v)
    weights.append(w)

for n in range(N):
    for w in range(1, W+1):
        if n == 0 and w >= weights[n]:
            dp[n][w] = values[n]
        elif w >= weights[n]: 
            dp[n][w] = max(dp[n-1][w-weights[n]] + values[n], dp[n-1][w])
        else:
            dp[n][w] = dp[n-1][w]
print(dp[N-1][W])

Solution (Python):
n,w = map(int, input().split())
value = []
weight = []
dp = [[0 for i in range(w+1)]for j in range(n+1)]
for i in range(n):
    v,we = map(int, input().split())
    value.append(v)
    weight.append(we)

for i in range(n):
    for j in range(w+1):
        if(j >= weight[i]):
            dp[i+1][j] = max(dp[i][j], dp[i][j-weight[i]]+value[i])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[n][-1])

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

dp = [[0 for i in range(W+1)] for j in range(n+1)]
for i in range(n):
    for w in range(W+1):
        if w >= items[i][1]:
            dp[i+1][w] = max(dp[i][w], dp[i][w - items[i][1]] + items[i][0])
        else:
            dp[i+1][w] = dp[i][w]

print(dp[n][W])

Solution (Python):



n, max_w = [int(i) for i in input().split()]

v = []
w = []
for j in range(n):
    value,weight=[int(i) for i in input().split()]
    v.append(value)
    w.append(weight)

dp = [[0 for i in range(max_w+1)] for j in range(n+1)]

for i in range(n):
    for cw in range(max_w+1):
        if cw >= w[i]:
            dp[i+1][cw] = max(dp[i][cw-w[i]]+v[i], dp[i][cw])
        else:
            dp[i+1][cw] = dp[i][cw]
print(dp[n][max_w])

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







dp = [[0 for _ in range(w+1)] for _ in range(n+1)]





for i in range(n):
    for j in range(w+1):
        if things[i][1] <= j:
            dp[i+1][j] = max(dp[i][j-things[i][1]]+things[i][0],dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[n][w])

Solution (Python):

import time

value_weight = {}
value_list = []
weight_list = []
input_data = input().split()
N, W = map(int, input_data)
for i in range(int(N)): 
    input_data = input().split()
    v, w = map(int, input_data)
    value_list.append(v)
    weight_list.append(w)

value_weight = [[0 for i in range(10010)] for j in range(110)]

for i in range(N):
    for w in range(W + 1):
        if w >= weight_list[i]:
            value_weight[i + 1][w] = max(value_weight[i][w - weight_list[i]] + value_list[i], value_weight[i][w])
        else:
            value_weight[i + 1][w] = value_weight[i][w]
print(value_weight[N][W])

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

dp = [[-1 for i in range(W+1)] for j in range(N+1)]

items = []
for i in range(N):
  items.append(list(map(int, input().split())))


def rec(i, empty):
  if dp[i][empty] != -1:
    return dp[i][empty]

  res = 0
  if i == N:
    pass
  elif empty < items[i][1]:
    res = rec(i+1, empty)
  else:
    res = max(rec(i+1, empty), rec(i+1, empty - items[i][1]) + items[i][0])

  dp[i][empty] = res
  return res

print(rec(0, W))

Solution (Python):

"""
Created on Sat May  5 11:31:13 2018
Napsack problem
@author: maezawa
"""

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

dp = [[0 for _ in range(wmax+1)] for _ in range(n+1)]

for i in range(n):
    for j in range(wmax+1):
        if j-w[i] < 0:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j-w[i]] + v[i], dp[i][j])
            
print(dp[n][wmax])

Solution (Python):
import math

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

v=[]
w=[]

for i in range(N):
    v1,w1 =map(int,input().split(' ') )
    v.append(v1)
    w.append(w1)
    
inf = 0

dp = [ [ inf for j in range(W+1) ] for i in range(N+1) ]

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

print(dp[N][W])

Solution (Python):
import queue


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

    dp = [[-float('inf') for _ in range(W + 1)] for _ in range(N + 1)]

    for i in range(W + 1):
        dp[0][i] = 0

    v = []
    w = []

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

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

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

            if w[i] <= j:
                dp[i + 1][j] = max(dp[i][j - w[i]] + v[i], dp[i][j])

    print(dp[N][W])

    return


if __name__ == '__main__':
    main()

Solution (Python):
from collections import namedtuple

if __name__ == '__main__':
    Item = namedtuple('Item', 'v w')
    N, W = map(int, input().split())
    lisItem = [Item(*map(int, input().split())) for _ in range(N)]
    
    dp = [[0 for _ in range(W + 1)] for __ in range(N + 1)]
    for i in range(0, N):
        for w in range(W + 1):
            if lisItem[i].w <= w:
                dp[i+1][w] = max(dp[i][w-lisItem[i].w] + lisItem[i].v, dp[i][w])
            else:
                dp[i+1][w] = dp[i][w]
    print(dp[N][W])

Solution (Python):
N,W=map(int,input().split())
I=[[*map(int,input().split())]for _ in[0]*N]
I=[0]+I
C=[[0]*-~W for _ in[0]*-~N]
G=[[0]*-~W for _ in[0]*-~N]
for i in range(1,N+1):
 for w in range(1,W+1):
  C[i][w]=C[i-1][w]
  if I[i][1]>w:continue
  if I[i][0]+C[i-1][w-I[i][1]]>C[i-1][w]:
   C[i][w]=I[i][0]+C[i-1][w-I[i][1]]
   G[i][w]=1
m=C[N][W]
w=W
D=[]
for i in range(N,0,-1):
 if G[i][w]:
  D+=[i]
  w-=I[i][1]
print(C[N][W])

Solution (Python):
N,W=map(int,input().split())
I=[0]+[[*map(int,input().split())]for _ in[0]*N]
C=[[0]*-~W for _ in[0]*-~N]
for i in range(1,N+1):
 for w in range(1,W+1):
  C[i][w]=C[i-1][w]
  if I[i][1]>w:continue
  if I[i][0]+C[i-1][w-I[i][1]]>C[i-1][w]:
   C[i][w]=I[i][0]+C[i-1][w-I[i][1]]
print(C[N][W])

Solution (Python):
N,W=map(int,input().split())
I=[0]+[[*map(int,input().split())]for _ in[0]*N]
C=[[0]*-~W for _ in[0]*-~N]
for i in range(1,N+1):
 for w in range(1,W+1):
  C[i][w]=C[i-1][w]
  if w>=I[i][1]and I[i][0]+C[i-1][w-I[i][1]]>C[i-1][w]:
   C[i][w]=I[i][0]+C[i-1][w-I[i][1]]
print(C[N][W])

Solution (Python):
N,W=map(int,input().split())
I=[[*map(int,input().split())]for _ in[0]*N]
C=[0]*-~W
for i in range(1,N+1):
 v,w=I[~-i]
 for j in range(W,w-1,-1):
  t=v+C[j-w]
  if t>C[j]:C[j]=t
print(C[W])

Solution (Python):
N,W=map(int,input().split())
I=[[*map(int,input().split())]for _ in[0]*N]
C=[0]*-~W
for i in range(1,N+1):
 v,w=I[~-i]
 for j in range(W,w-1,-1):
  t=v+C[j-w]
  if t>C[j]:C[j]=t
print(C[W])

Solution (Python):
N,W=map(int,input().split())
I=[[*map(int,input().split())]for _ in[0]*N]
C=[0]*-~W
for i in range(1,N+1):
 v,w=I[~-i]
 for j in range(W,w-1,-1):
  t=v+C[j-w]
  if t>C[j]:C[j]=t
print(C[W])

Solution (Python):
N,W=map(int,input().split())
I=[[*map(int,input().split())]for _ in[0]*N]
C=[0]*-~W
for i in range(1,N+1):
 v,w=I[~-i]
 for j in range(W,w-1,-1):
  t=v+C[j-w]
  if t>C[j]:C[j]=t
print(C[W])

Solution (Python):
import sys
W=int(input().split()[1])
C=[0]*-~W
for e in sys.stdin:
 v,w=map(int,e.split())
 for i in range(W,w-1,-1):
  t=v+C[i-w]
  if t>C[i]:C[i]=t
print(C[W])

Solution (Python):
import sys
W=int(input().split()[1])
C=[0]*-~W
for e in sys.stdin:
 v,w=map(int,e.split())
 for i in range(W,w-1,-1):
  t=v+C[i-w]
  if t>C[i]:C[i]=t
print(C[W])

Solution (Python):
import sys
W=int(input().split()[1])
C=[0]*-~W
for e in sys.stdin:
 v,w=map(int,e.split())
 for i in range(W,w-1,-1):
  t=v+C[i-w]
  if t>C[i]:C[i]=t
print(C[W])

Solution (Python):
N,W=map(int,input().split())
C=[0]*-~W
for _ in[0]*N:
 v,w=map(int,input().split())
 for i in range(W,w-1,-1):
  t=v+C[i-w]
  if t>C[i]:C[i]=t
print(C[W])

Solution (Python):
N,W=map(int,input().split())
C=[0]*-~W
for _ in[0]*N:
 v,w=map(int,input().split())
 for i in range(W,w-1,-1):
  t=v+C[i-w]
  if t>C[i]:C[i]=t
print(C[W])

Solution (Python):
N,W=map(int,input().split())
C=[0]*-~W
for _ in[0]*N:
 v,w=map(int,input().split())
 for i in range(W,w-1,-1):
  t=v+C[i-w]
  if t>C[i]:C[i]=t
print(C[W])

Solution (Python):
import sys
def s():
 W=int(input().split()[1])
 C=[0]*-~W
 for e in sys.stdin:
  v,w=map(int,e.split())
  for i in range(W,w-1,-1):
   t=v+C[i-w]
   if t>C[i]:C[i]=t
 print(C[W])
if'__main__'==__name__:s()

Solution (Python):
import sys
def s():
 W=int(input().split()[1])
 C=[0]*-~W
 for e in sys.stdin:
  v,w=map(int,e.split())
  for i in range(W,w-1,-1):
   t=v+C[i-w]
   if t>C[i]:C[i]=t
 print(C[W])
if'__main__'==__name__:s()

Solution (Python):
import sys
def s():
 W=int(input().split()[1])
 C=[0]*-~W
 for e in sys.stdin:
  v,w=map(int,e.split())
  for i in range(W,w-1,-1):
   t=v+C[i-w]
   if t>C[i]:C[i]=t
 print(C[W])
if'__main__'==__name__:s()

Solution (Python):
import sys
def s():
 W=int(input().split()[1])
 C=[0]*-~W
 for e in sys.stdin:
  v,w=map(int,e.split())
  for i in range(W,w-1,-1):
   t=v+C[i-w]
   if t>C[i]:C[i]=t
 print(C[W])
if'__main__'==__name__:s()

Solution (Python):
import sys
def s():
 W=int(input().split()[1])
 C=[0]*-~W
 for e in sys.stdin:
  v,w=map(int,e.split())
  for i in range(W,w-1,-1):
   t=v+C[i-w]
   if t>C[i]:C[i]=t
 print(C[W])
s()

Solution (Python):
import sys
def s():
 W=int(input().split()[1])
 C=[0]*-~W
 for e in sys.stdin:
  v,w=map(int,e.split())
  for i in range(W,w-1,-1):
   t=v+C[i-w]
   if t>C[i]:C[i]=t
 print(C[W])
s()

Solution (Python):
import sys
def s():
 W=int(input().split()[1])
 C=[0]*-~W
 for e in sys.stdin:
  v,w=map(int,e.split())
  for i in range(W,w-1,-1):
   t=v+C[i-w]
   if t>C[i]:C[i]=t
 print(C[W])
s()

Solution (Python):
N,W=map(int,input().split())
v=[None]*N
w=[None]*N

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

dp=[]
for i in range(N+1):
    dp.append([0]*(W+1))

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

print(dp[0][W])

Solution (Python):
n,m=list(map(int,input().split()))
d=[0]*(m+1)
for i in range(n):
    v,w=map(int,input().split())
    for j in range(m+1-w):
        if d[m-j]<d[m-j-w]+v:
            d[m-j]=d[m-j-w]+v
print(max(d))

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

dp = [[-1 for i in range(W+1)] for j in range(N+1)]

for i in range(W+1):
    dp[0][i] = 0

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

Solution (Python):

"""
Created on Fri May 25 22:23:44 2018
Knapsack by memorized recursive call
@author: maezawa
"""

n, maxw = list(map(int, input().split()))
w = []
v = []
dp = [[None for _ in range(maxw+1)] for _ in range(n)]

for i in range(n):
    i, j = list(map(int, input().split())) 
    v.append(i)
    w.append(j)

def total_value(i, wi):
    if i == n:
        return 0
    if dp[i][wi] != None:
        return dp[i][wi]
    if wi < w[i]:
        dp[i][wi] = total_value(i+1,wi)
    else:
        dp[i][wi] = max(total_value(i+1,wi), total_value(i+1,wi-w[i])+v[i])
    return dp[i][wi]

print(total_value(0, maxw))

Solution (Python):
N, W = map(int, input().split())
mo = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * (W+1) for _ in range(N+1)]

for i, m in enumerate(mo):
    for j in range(W+1):
        if j < m[1]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-m[1]] + m[0])
print(dp[N][W])

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

table = [[0 for j in range(w+1)] for i in range(n+1)]

for i in range(1, n+1):
    v_i, w_i = items[i-1]
    for j in range(1, w+1):
        if j - w_i < 0:
            table[i][j] = max(table[i][j-1], table[i-1][j])
        else:
            new_val = table[i-1][j-w_i] + v_i
            if new_val > table[i][j-1]:
                table[i][j] = max(new_val, table[i][j-1], table[i-1][j])
            else:
                table[i][j] = max(table[i][j-1], table[i-1][j])

print(table[-1][-1])

Solution (Python):
N,W = map(int, input().split())
items = []
for i in range(N):
    v, w = map(int, input().split())
    items.append([v, w])
dp = [[0 for j in range(W+1)] for i in range(N+1)]
for i in range(1, N+1):
    iv = items[i-1][0]
    iw = items[i-1][1]
    for j in range(1, W+1):
        if iw <= j: dp[i][j] = max(dp[i-1][j-iw] + iv, dp[i-1][j])
        else: dp[i][j] = dp[i-1][j]
print(dp[N][W])

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

items=[]

for i in range(N):
    items.append(list(map(int,input().split())))
    
dp = [[0 for i in range(10001)] for j in range(110)]

for i in range(N):
    dp[i][0]=0
    
for i in range(N):
    for w in range(W+1):
        if w>=items[i][1]:
            dp[i+1][w]=max(dp[i][w-items[i][1]]+items[i][0],dp[i][w])
        else:
            dp[i+1][w]=dp[i][w]
        


print(dp[N][W])

Solution (Python):
N, W = [int(i) for i in input().split(" ")]
VW = [[int(j) for j in input().split(" ")] for i in range(N)]

dp = [[0 for i in range(W + 1)] for j in range(N + 1)]

for i in range(N):
    for w in range(1, W + 1):
        if w < VW[i][1]:
            dp[i + 1][w] = dp[i][w]
        else:
            dp[i + 1][w] = max([dp[i][w], dp[i][w - VW[i][1]] + VW[i][0]])

print(max(dp[N]))

Solution (Python):



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

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

dp = []
for i in range(110):
    o = [0 for i in range(10010)]
    dp.append(o)



for ww in range(w):
    dp[0][ww] = 0

for i in range(0,n):
    for ww in range(w+1):
        
        if ww >= weight[i] :
            dp[i+1][ww] = max(dp[i][ww-weight[i]] + value[i], dp[i][ww])
        else:
            dp[i+1][ww] = dp[i][ww]
print(dp[n][w])

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

dp = [[0]*(W+3) for _ in range(N+3)]
for w in range(1,W+1):
    for k in range(1,N+1):
        if weight[k] > w:
            dp[k][w] = dp[k-1][w]
        else:
            
            dp[k][w] = max(dp[k-1][w], value[k] + dp[k-1][w-weight[k]])
print(dp[N][W])

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

dp = [[0]*(W+3) for _ in range(N+3)]
for w in range(1,W+1):
    for k in range(1,N+1):
        if weight[k] > w:
            dp[k][w] = dp[k-1][w]
        else:
            
            dp[k][w] = max(dp[k-1][w], value[k] + dp[k-1][w-weight[k]])
print(dp[N][W])

Solution (Python):
N, W = list(map(int, input().split()))
items = [[0, 0]]
for _ in range(N):
    v, w = list(map(int, input().split()))
    items.append([v, w])
DP = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(W + 1):
        if items[i][1] > j:
            DP[i][j] = DP[i - 1][j]
        else:
            DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - items[i][1]] + items[i][0])
print(DP[N][W])

Solution (Python):
N, W = list(map(int, input().split()))
items = [[0, 0]]
for _ in range(N):
    v, w = list(map(int, input().split()))
    items.append([v, w])
'''
DP = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(W + 1):
        if items[i][1] > j:
            DP[i][j] = DP[i - 1][j]
        else:
            DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - items[i][1]] + items[i][0])
print(DP[N][W])
'''
DP2 = [0 for _ in range(W + 1)]
for i in range(1, N + 1):
    for j in range(W, items[i][1] - 1, -1):
            DP2[j] = max(DP2[j], DP2[j - items[i][1]] + items[i][0])
print(DP2[W])

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

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

vMax = 0
wMax = 0
for i in range(n):
    vMax = max(vMax, a[i][0])
    wMax = max(wMax, a[i][1])

if n <= 30:
    val = []
    if a[0][1] <= w:
        val.append(a[0])

    for i in range(1, n):

        j = 0
        valTemp = val[:]
        while j < len(valTemp):
            k = 0
            if valTemp[j][1] + a[i][1] <= w:
                temp = [valTemp[j][0] + a[i][0], valTemp[j][1] + a[i][1]]
                while k < len(val):
                    if val[k][0] == temp[0]:
                        if temp[1] < val[k][1]:
                            val[k] = temp
                        break
                    elif val[k][0] > temp[0]:
                        if temp[1] < val[k][1]:
                            val.insert(k, temp)
                        break

                    k += 1
                else:
                    val.append(temp)
            j += 1

        if a[i][1] <= w:
            temp = a[i]
            j = 0
            while j < len(val):
                if val[j][0] == temp[0]:
                    if temp[1] < val[j][1]:
                        val[j] = temp
                    break
                elif val[j][0] > temp[0]:
                    if temp[1] < val[j][1]:
                        val.insert(j, temp)
                    break

                j += 1
            else:
                val.append(temp)
        
        j = len(val) - 2

        while j >= 0:
            if val[j][1] >= val[j + 1][1]:
                del val[j]
            j -= 1

    print(val[len(val) - 1][0])

elif wMax <= 1000:
    w = min(w, wMax * n)
    dp = [0 for _ in range(w + 1)]
    for i in range(n):
        for j in range(w, a[i - 1][1] - 1, -1):
            dp[j] = max(dp[j], dp[j - a[i - 1][1]] + a[i - 1][0])

    print(max(dp))
else:
    m = n + vMax
    dp = [0 for _ in range(m + 1)]
    for i in range(n):
        for j in range(m , a[i - 1][0] - 1, -1):
            dp[j] = min(dp[j], dp[j - a[i - 1][0]] + a[i - 1][1])

    ans = 0
    for i in range(n * vMax):
        if dp[n][i] != 0:
            ans = max(ans, i)
 
    print(ans)

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

value = []
weight = []

for _ in range(n):
  vi, wi = map(int, input().split())
  value.append(vi)
  weight.append(wi)

dp = [0 for _ in range(w + 1)]

for i in range(n):
  for j in range(w, weight[i] - 1, -1):
    dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

print(dp[w])

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

dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
for i in range(N):
    for w in range(W + 1):
        if w >= wight[i]:
            dp[i + 1][w] = max(dp[i][w - wight[i]] + value[i], dp[i][w])
        else:
            dp[i + 1][w] = dp[i][w]
print(dp[N][W])

Solution (Python):
N, W = list(map(int, input().split()))
vw = []
dp = [[0 for j in range(W+1)] for i in range(N+1)]

for i in range(N):
    vw_i = list(map(int, input().split()))
    vw.append((vw_i[0], vw_i[1]))

for i in range(N):
    for w in range(W+1):
        if w >= vw[i][1]:
            dp[i+1][w] = max(dp[i][w-vw[i][1]]+vw[i][0], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]

print(dp[N][W])

Solution (Python):

reader = input().split(' ')
item_num = int(reader[0])
w_max = int(reader[1])

value = []
weight = []
for i in range(item_num):
    reader = input().split(' ')
    value.append(int(reader[0]))
    weight.append(int(reader[1]))

dp_table = [[0 for i in range(w_max+1)] for j in range(item_num+1)]

for i in range(item_num):
    for w in range(w_max+1):
        if w >= weight[i]:
            dp_table[i+1][w] = max([dp_table[i][w-weight[i]] + value[i], dp_table[i][w]])
        else:
            dp_table[i+1][w] = dp_table[i][w]

print(str(dp_table[item_num][w_max]))

Solution (Python):
import sys

def solve():
    file_input = sys.stdin
    N, W = map(int, file_input.readline().split())
    C = [0] * (W + 1)
    for line in file_input:
        item_v, item_w = map(int, line.split())
        for i, vals in enumerate(zip(C[item_w:], C)):
            v1, v2 = vals
            v1 += item_v
            if v1 > v2:
                C[i] = v1
    print(C[0])

solve()

Solution (Python):
N,W=map(int,input().split())
v=[0]*1010
w=[0]*1010
for i in range(1,N+1):
    x,y=map(int,input().split())
    v[i]=x
    w[i]=y
    
a=[[0 for i in range(W+1)]for j in range(N+1)]
a[0][W]=0
for i in range(1,N+1):
    for j in range(1,1+W):
        if w[i]<=j:
            a[i][j]=max(a[i-1][j-w[i]]+v[i],a[i-1][j])
        else:
            a[i][j]=a[i-1][j]
print(a[N][W])

Solution (Python):
n,w = map(int, input().split())
item = [list(map(int,input().split())) for i in range(n)]
dp = [0 for i in range(w+2)]
for v in item:
    for i in range(1,w+2):
        if w+1-i+v[1] <= w:
            dp[w+1-i+v[1]] = max(dp[w+1-i+v[1]],dp[w+1-i]+v[0])
print(dp[w])

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

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


inf = float("inf")
dp = [[-inf for i in range(W+1)] for j in range(N+1)]
for i in range(W+1):
    dp[0][i] = 0


for i in range(N):
    for w in range(W+1):
        if weight[i] <= w:
            dp[i+1][w] = max(dp[i][w-weight[i]]+value[i], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]

print(dp[N][W])

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

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
dp[0][W] = 0
for i in range(N):
    for w in range(W+1):
        if w >= w_arr[i]:
            dp[i+1][w] = max(dp[i][w - w_arr[i]] + v_arr[i], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
print(dp[N][W])

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

weights = []
values = []

for i in range(n):
	val,wei = map(int,raw_input().split())
	values.append(val)
	weights.append(wei)

dp = [[-1 for i in range(w+1)] for i in range(n+1)]

dp[0][0] = 0

for i in range(n):
	for j in range(w+1):
		if j >= weights[i] and dp[i][j-weights[i]] != -1 :
			dp[i+1][j] = max(dp[i][j-weights[i]] + values[i], dp[i][j])
		else :
			dp[i+1][j] = dp[i][j]

print max(dp[n])

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

for i in range(N):
    shina.append(list(map(int, input().split())))


def memoize(f):
    table = {}

    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func


@memoize
def dp(n, w):
    if n == 0:
        return 0
    elif w - shina[n - 1][1] >= 0:
        return max(dp(n - 1, w), dp(n - 1, w - shina[n - 1][1]) + shina[n - 1][0])
    else:
        return dp(n - 1, w)


print(dp(N, W))

Solution (Python):
N, W = map(int, raw_input().split())
v = [0] * N
d = [0] * N
dp = [[0 for i in range(W + 1)] for j in range(N + 1)]
for i in range(N):
  v[i], d[i] = map(int, raw_input().split())
  for j in range(W + 1):
    if j < d[i]:
      dp[i + 1][j] = dp[i][j];
    else:
      dp[i + 1][j] = max(dp[i][j], dp[i][j - d[i]] + v[i])
print dp[N][W];

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

DP = [0]*(W+1)
for i in range(N):
    value = v[i]; weight = w[i]
    for sum_w in range(W,0,-1):
        if sum_w - weight >= 0:
            DP[sum_w] = max(DP[sum_w], DP[sum_w - weight] + value)

print(DP[W])

Solution (Python):
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readlines

lines = input()

n, W = list(map(int, lines[0].split()))

items = [None] * (n+1)

T = [[0] * (W+1) for i in range(n+1)]
G = [[0] * (W+1) for i in range(n+1)]


for i in range(n):
    items[i+1] = list(map(int, lines[i+1].split()))

for i in range(1, n+1):
    for w in range(1, W+1):
        k = items[i][1]
        if k > w:
            G[i][w] = "top"
            T[i][w] = T[i-1][w]
        else:
            a = T[i-1][w - k] + items[i][0]
            b = T[i-1][w]
            if a > b:
                G[i][w] = "diagonal"
                T[i][w] = a
            else:
                G[i][w] = "top"
                T[i][w] = b

print(T[n][W])