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,MaxW = list(map(int,input().split()))

V = []
W = []

for i in range(N):
    v,w = list(map(int,input().split()))
    V.append(v)
    W.append(w)
    
dp = [[0]*(MaxW+1) for i in range(N+1)]

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


print(dp[N][MaxW])

Solution (Python):


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

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

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

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

print(dp[N][W])

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

dp =[[0 for j in range(W+1)]for i in range(N+1)]
v = []
w = []
for i in range(N):
    temp_v,temp_w = map(int,input().split())
    v.append(temp_v)
    w.append(temp_w)
    
    

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

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

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 >= 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(max([max(e) for e in dp]))

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 el in range(n):
    x, y = map(int, input().split())
    value.append(x)
    weight.append(y)

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

for i in range(n):
    for w in range(W + 1):
        if w >= weight[i]:
            
            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())
dp = [0]*(W+1)

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

Solution (Python):
def main():
    N, W = map(int, input().split())
    value = []
    weight = []
    for i in range(N):
        a, b = map(int, input().split())
        value.append(a)
        weight.append(b)
    dp = [[-float("inf") for i in range(W+1)] for j in range(N+1)]
    for w in range(W+1):
        dp[0][w] = 0

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

if __name__ == '__main__':
    print(main())

Solution (Python):
def get_max_value(n, W, v, w):
	dp = [[0 for x in range(W+1)] for x in range(n+1)]
	for i in range(1, n+1):
		wt = w[i-1]
		vl = v[i-1]
		for j in range(W+1):
			if wt > j:
				dp[i][j]=dp[i-1][j]
			else:
				dp[i][j]=max(dp[i-1][j], dp[i-1][j-wt]+vl)
	return dp[n][W]

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())
print(get_max_value(n, W, v, w))

Solution (Python):
def get_max_value(n, W, v, w):
	dp = [[0 for x in range(W+1)] for x in range(n+1)]
	for i in range(1,n+1):
		wt = w[i-1]
		vl = v[i-1]
		for j in range(1,W+1):
			if wt > j:
				dp[i][j]=dp[i-1][j]
			else:
				dp[i][j]=max(dp[i-1][j], dp[i-1][j-wt]+vl)
	return dp[n][W]

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())
print(get_max_value(n, W, v, w))

Solution (Python):
def get_max_value(n, W, v, w):
	dp = [[0 for x in range(W+1)] for x in range(n+1)]
	for i in range(1,n+1):
		wt = w[i-1]
		vl = v[i-1]
		for j in range(1,W+1):
			if wt > j:
				dp[i][j]=dp[i-1][j]
			else:
				dp[i][j]=max(dp[i-1][j], dp[i-1][j-wt]+vl)
	return dp[n][W]

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())
print(get_max_value(n, W, v, w))

Solution (Python):
N, W = (int(i) for i in input().split())
bagage = [[int(i) for i in input().split()] for _ in range(N)]
weight = []
value = []
for b in bagage:
    value.append(b[0])
    weight.append(b[1])

dp = [[0]*10010 for i in range(110)]

for j in range(W):
    dp[N][j] = 0

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

print(dp[0][W])

Solution (Python):
def ramp(t):
    if t >= 0:
        return t
    else:
        return 0
def heav(t):
    if t >= 0:
        return(1)
    else:
        return(0)
N,W = map(int,input().strip().split(" "))
lst = []
for i in range(N):
    l = list(map(int,input().strip().split(" ")))
    lst.append(l)
table = [[0 for c in range(W+1)] for i in range(N+1)]
for i in range(1,N+1):
    for c in range(1,W+1):
        table[i][c] = max(table[i-1][c],table[i-1][ramp(c-lst[i-1][1])]+lst[i-1][0]*heav(c-lst[i-1][1]))
print(table[N][W])

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

    
for i in range(N):
    v=goods[i][0]
    w=goods[i][1]
    for j in range(W+1):
        dp[i+1][j]=max(dp[i][j],dp[i+1][j])
        next_w=j+w
        next_v=dp[i][j]+v
        if(next_w<=W and next_v>dp[i+1][next_w]):
            dp[i+1][next_w]=next_v

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

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):
def Knapsack(N, W, vs, ws):
    dp = [[0 for n in range(W+1)] for w in range(N+1)]

    for n in range(N):
        for w in range(W+1):
            if (w >= ws[n]):
                dp[n+1][w] = max(dp[n][w-ws[n]] + vs[n], dp[n][w])
            else:
                dp[n+1][w] = dp[n][w]

    return dp[N][W]

N, W = map(int, input().split(' '))
vs, ws = [0] * N, [0] * N
for n in range(N):
    vs[n], ws[n] = map(int, input().split(' '))

ans = Knapsack(N, W, vs, ws)
print(ans)

Solution (Python):

N,W=map(int,input().split())
data=[]
for i in range(N):
    v,w=map(int,input().split())
    data.append((v,w))
ans={0:0}
for i in data:
    ans1=ans.copy()
    for v in ans:
        if i[1]+v in ans.keys():
            ans1[i[1]+v]=max(ans[i[1]+v],ans[v]+i[0])
        else:
            ans1[i[1]+v]=ans[v]+i[0]
    ans=ans1
maxv=0
for i in ans:
    if i<=W and ans[i]>maxv:
        maxv=ans[i]
print(maxv)

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

values = []
weights = []
for i in range(n):
    value, weight = map(int, input().split())
    values.append(value)
    weights.append(weight)

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

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

print(dp[n][w])

Solution (Python):

def dp(i, j):
    if dp_list[i][j] != 0:
        return dp_list[i][j]
    if i == len(lists):
        return 0
    if j < lists[i][1]:
        dp_list[i][j] = dp(i + 1, j)
        return dp_list[i][j]
    else:
        dp_list[i][j] = max(dp(i + 1, j), dp(i + 1, j - lists[i][1]) + lists[i][0])
        return dp_list[i][j]


N, W = (int(x) for x in input().split())

lists = []
for i in range(N):
    lists.append(list(map(lambda x: int(x), input().split())))
dp_list = [[0 for i in range(W + 1)] for j in range(N + 1)]
print(dp(0, W))

Solution (Python):
import copy
length, capacity = map(int, input().split(" "))
nap = []
for _ in range(length):
    v, w = map(int, input().split(" "))
    nap.append([v, w])
dp = [0 for n in range(capacity + 1)]

for i, (v, w) in enumerate(nap):
    new_dp = dp[::]
    if w <= capacity:
        new_dp[w] = max(v, dp[w])
    for j, now_v in enumerate(dp):
        if now_v and j + w <= capacity:
            new_dp[j + w] = max(dp[j + w], now_v + v)
    dp = new_dp
answer = 0
for v in dp:
    answer = max(answer, v)
print(answer)

Solution (Python):

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

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




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





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

Solution (Python):
INF = 10 ** 12

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

items =[] * N

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

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+1):
    dp[i][0] = 0

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

print(dp[N][W])

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

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

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

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


print(dp[N][W])

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

for _ in range(N):
    tmp_v, tmp_w = (int(x) for x in input().split())
    value.append(tmp_v)
    weight.append(tmp_w)

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

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

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

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

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

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

Solution (Python):
import sys

def knappack(N, W, vs, ws):
    dp = [0] * (W + 1)
    for i in range(N):
        for j in range(W, ws[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - ws[i]] + vs[i])
            
    return dp[-1]
    
    
if __name__ == '__main__':
    line = sys.stdin.readline()
    Nstr, Wstr = line.split()
    N, W = int(Nstr), int(Wstr)
    vs, ws = [], []
    for i in range(N):
        line = sys.stdin.readline()
        v, w = line.split()
        v, w = int(v), int(w)
        vs.append(v)
        ws.append(w)
    sys.stdout.write(str(knappack(N, W, vs, ws)))
    sys.stdout.write('\n')

Solution (Python):
from sys import stdin
import operator
readline = stdin.readline


n, total_wait = map(int, readline().split())
value_wait = [list(map(int, readline().split())) for _ in range(n)]
value_wait.sort(key=operator.itemgetter(1), reverse=True)

dp = [[0] * (total_wait + 1) for _ in range(n + 1)]
for ni, (v, w) in enumerate(value_wait):
    for tw in range(w, total_wait + 1):
        dp[ni + 1][tw] = max(dp[ni][tw], dp[ni][tw - w] + v)
print(dp[-1][-1])

Solution (Python):
N, maxW = map(int, input().split())
V, W = [], []
for i in range(N):
    v, w = map(int, input().split())
    V.append(v); W.append(w)
dp = [[0]*(maxW+1) for _ in range(N+1)]
for i in range(N):
    for j in range(maxW+1):
        if j < W[i]:
            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][maxW])

Solution (Python):
N, maxW = map(int, input().split())
V, W = [], []
for i in range(N):
    v, w = map(int, input().split())
    V.append(v); W.append(w)
dp = [[0]*(maxW+1) for _ in range(2)]
for i in range(N):
    for j in range(maxW+1):
        if j < W[i]:
            dp[(i+1)&1][j] = dp[i&1][j]
        else:
            dp[(i+1)&1][j] = max(dp[i&1][j], dp[i&1][j-W[i]] + V[i])
print(dp[N&1][maxW])

Solution (Python):


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

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

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

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

print(dp[N][W])

Solution (Python):
n, w = map(int, raw_input().split())
goods = [map(int, raw_input().split()) for i in range(n)]
dp = [0]*(w+1)
for g in goods:
    ndp = [0]*(w+1)
    for i in range(w+1):
        if i - g[1] < 0:
            ndp[i] = dp[i]
        else:
            ndp[i] = max(dp[i-g[1]] + g[0], dp[i])
    dp = ndp
print dp[w]

Solution (Python):
"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B
"""

from __future__ import division
from sys import stdin, maxint

def knapsack(N, W, infos):
	dp = [0] * (W + 1)
	for i in range(N):
		for j in range(W, infos[i][1] - 1, -1):
			dp[j] = max(dp[j], dp[j - infos[i][1]] + infos[i][0])

	return dp[W]


if __name__ == '__main__':
    N, W = map(int, stdin.readline().strip().split())
    infos = []
    for _ in range(N):
    	v, w = map(int, stdin.readline().strip().split())
    	infos.append((v, w))
    print(knapsack(N, W, infos))

Solution (Python):
"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B
"""

from __future__ import division
from sys import stdin, maxint


def knapsack(N, W, infos):
	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 j >= infos[i - 1][1]:
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - infos[i - 1][1]] + infos[i - 1][0])
			else:
				dp[i][j] = dp[i - 1][j]


	return dp[N][W]


if __name__ == '__main__':
    N, W = map(int, stdin.readline().strip().split())
    infos = []
    for _ in range(N):
    	v, w = map(int, stdin.readline().strip().split())
    	infos.append((v, w))
    print(knapsack(N, W, infos))

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

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

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


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

    if i == N:
        res = 0
    elif j < w[i]:
        res = rec(i + 1, j)
    else:
        res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i])

    dp[i][j] = res
    return res

print(rec(0, W))

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

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

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

for i in range(N - 1, -1, -1):
    for j in range(W + 1):
        if j < w[i]:
            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):
a = map(int, raw_input().split())
N = a[0]
W = a[1]

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

Items = [Item(0,0)]
for i in xrange(N):
    a = map(int,raw_input().split())
    Items.append(Item(a[0],a[1]))

C = [ [0] * (W+1) for _ in xrange(N+1)]
G = [ [''] * (W+1) for _ in xrange(N+1)] 

def knapsack():
    for i in xrange(1,N+1):
        for w in xrange(1,W+1):
            if Items[i].w <= w:
                if Items[i].v + C[i-1][w-Items[i].w] > C[i-1][w]:
                    C[i][w] = Items[i].v + C[i-1][w-Items[i].w]
                    G[i][w] = 'DIAGONAL'
                else:
                    C[i][w] = C[i-1][w]
                    G[i][w] = 'TOP'
            else:
                C[i][w] = C[i-1][w]
                G[i][w] = 'TOP'

    print C[N][W]
    return 0

knapsack()

Solution (Python):


from __future__ import print_function
from __future__ import unicode_literals
from __future__ import division
from __future__ import absolute_import
import math
import string
import itertools
import fractions
import heapq
import collections
import re
import array
import bisect

def array2d(row, col, init = None):
    return [[init for _ in range(col)] for _ in range(row)]

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)

dpt = array2d(N + 1, W + 1)

def dp(i, j):
    if dpt[i][j] is not None:
        return dpt[i][j]
    if i == 0:
        dpt[i][j] = 0
        return 0
    if j < w[i-1]:
        dpt[i][j] = dp(i-1, j)
        return dpt[i][j]
    dpt[i][j] = max(dp(i-1, j), dp(i-1, j-w[i-1]) + v[i-1])
    return dpt[i][j]

print(dp(N, W))

Solution (Python):
N,W=map(int,raw_input().split())
vw=[map(int,raw_input().split()) for i in xrange(N)]
dp=[[0]*(W+1) for _ in xrange(N+1)]
for i in xrange(N):
    for j in xrange(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):
l = input().split()
N = int(l[0])
W = int(l[1])
products = [] 
for i in range(N):
    l = input().split()
    products.append([int(l[0]),int(l[1])])

DP = [0 for _ in range(W+1)]
p_flag = [[False for _ in range(N)] for _ in range(W+1)]
for i in range(N):
    new_DP = [DP[j] if j < products[i][1] else 0 for j in range(W+1)]
    for j in range(products[i][1], W + 1):
        product_in = DP[j - products[i][1]] + products[i][0]
        if product_in >= DP[j]:
            new_DP[j] = product_in
        else:
            new_DP[j] = DP[j]
    DP = [v for v in new_DP]
print(DP[W])

Solution (Python):
N, W = map(int, raw_input().split())
v = [0]*N
w = [0]*N
for i in xrange(N):
    v[i], w[i] = map(int, raw_input().split())
dp = [0] * (W+1)
for i in xrange(N):
    for j in xrange(W, w[i]-1, -1):
        dp[j] = max(dp[j-w[i]] + v[i], dp[j])
print dp[W]

Solution (Python):
l = input().split()
N = int(l[0])
W = int(l[1])
products = [] 
for i in range(N):
    l = input().split()
    products.append([int(l[0]),int(l[1])])

DP = [0 for _ in range(W + 1)]
p_flag = [[False for _ in range(N)] for _ in range(W + 1)]
for i in range(N):
    new_DP = [DP[j] if j < products[i][1] else 0 for j in range(W + 1)]
    for j in range(products[i][1], W + 1):
        product_in = DP[j - products[i][1]] + products[i][0]
        if product_in >= DP[j]:
            new_DP[j] = product_in
        else:
            new_DP[j] = DP[j]
    DP = [v for v in new_DP]
print(DP[W])

Solution (Python):
l = input().split()
N = int(l[0])
W = int(l[1])

v = []
w = []
for i in range(N):
    l = input().split()
    v.append(int(l[0]))
    w.append(int(l[1]))


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

for j in range(1, N + 1):
    for k in range(1, W + 1):
        if w[j-1] <= k:
            if v[j-1] + c[j-1][k-w[j-1]] > c[j - 1][k]:
                c[j][k] = v[j-1] + c[j-1][k-w[j-1]]
            else:
                c[j][k] = c[j-1][k]
        else:
            c[j][k] = c[j-1][k]
print(c[N][W])

Solution (Python):
n,maxw = map(int, input().split())
arr = [[-1 for i in range(maxw+1)] for j in range(n+1)]
arr[0][0] = 0
ans = 0
for i in range(n):
    v,w = map(int, input().split())
    for j in range(maxw):
        arr[i+1][j] = max(arr[i+1][j], arr[i][j])
        if j + w <= maxw and arr[i][j] >= 0:
            arr[i+1][j+w] = max(arr[i][j+w], arr[i][j] + v)
            ans = max(arr[i+1][j+w], ans)
print(ans)

Solution (Python):
if __name__ == '__main__':

    """prepairing"""

    amount = input()
    factor = amount.split(' ')
    N = int(factor[0])
    W = int(factor[1])

    v = []
    w = []
    v.append(0)
    w.append(0)
    inputs = []

    d = []

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

    """getting inputs and initializing arrays"""

    for x in range(N):
        inputs[:] = []
        inputs = input().split(' ')
        v.append(int(inputs[0]))
        w.append(int(inputs[1]))



    """make array"""

    for row in range(W + 1):
        for column in range(N + 1):
            if row != 0 and column != 0:
                if w[column] > row:
                    d[row][column] = d[row][column - 1]
                else:
                    d[row][column] = max(d[row - w[column]][column - 1] + v[column], d[row][column - 1])

    print(d[W][N])

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

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

print(dp[N][W])

Solution (Python):
n, cap = map(int, input().split())
dp = [None] * (cap + 1)
dp[0] = 0

for _ in range(n):
    v, w = map(int, input().split())
    for k in range(cap - w, -1, -1):
        tmp_before_v = dp[k]
        if tmp_before_v == None:
            continue
        tmp_after_v, new_v = dp[k + w], tmp_before_v + v
        if tmp_after_v == None or tmp_after_v < new_v:
            dp[k + w] = new_v

print(max(filter(None, dp)))

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

for _ in range(n):
    v, w = map(int, input().split())
    for k in range(cap - w, -1, -1):
        new_v = dp[k] + v
        if dp[k + w] < new_v:
            dp[k + w] = new_v

print(max(dp))

Solution (Python):
n,w=map(int,raw_input().split())
vw=[map(int,raw_input().split()) for _ in xrange(n)]
dp=[[0]*(w+1) for _ in xrange(n+1)]
for i in xrange(n):
    for j in xrange(w+1):
        if j<vw[i][1]:
            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):
num,weight = (int(n) for n in input().split(" "))
query = []
for n in range(num):
    query.append([int(n) for n in input().split(" ")])
nap = [[0 for n in range(weight + 1)] for m in range(num + 1)]
for n in range(num):
    for w in range(weight + 1):

        if query[n][1] <= w:
            nap[n + 1][w] = max(nap[n][w-query[n][1]] + query[n][0],nap[n][w])
        else:
            nap[n + 1][w] = nap[n][w]
print(nap[num][weight])

Solution (Python):
n,w=map(int,raw_input().split())
vw=[map(int,raw_input().split()) for _ in xrange(n)]
dp=[[0]*(w+1) for _ in xrange(2)]
for i in xrange(n):
    for j in xrange(w+1):
        if j<vw[i][1]:
            dp[(i+1)&1][j]=dp[i&1][j]
        else:
            dp[(i+1)&1][j]=max(dp[i&1][j],dp[i&1][j-vw[i][1]]+vw[i][0])
print(dp[n&1][w])

Solution (Python):
n,w=map(int,raw_input().split())
vw=[map(int,raw_input().split()) for _ in xrange(n)]
dp=[0]*(w+1)
for i in xrange(n):
    for j in xrange(w,vw[i][1]-1,-1):
        dp[j]=max(dp[j],dp[j-vw[i][1]]+vw[i][0])
print(dp[w])

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

def rec(i, j):
    if dp[i][j] != -1:
        return dp[i][j]
    if i == N:
        res = 0
    elif j < w[i]:
        res = rec(i + 1, j)
    else:
        res = max(rec(i + 1, j),rec(i + 1, j - w[i]) + v[i])
    dp[i][j] = res
    return res

print(str(rec(0, W)))

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

def rec(i, j):
    if dp[i][j] != -1:
        return dp[i][j]
    if i == N:
        res = 0
    elif j < w[i]:
        res = rec(i + 1, j)
    else:
        res = max(rec(i + 1, j),rec(i + 1, j - w[i]) + v[i])
    dp[i][j] = res
    return res

print(str(rec(0, W)))

Solution (Python):
l=[]
n,W=input().split()
n=int(n)
W=int(W)
for i in range(n):
	item=list(map(int,input().split()))
	l.append([item[1],item[0]])

dp=[[False for j in range(W+1)] for i in range(n+1)]

def solve(i,w):
	if dp[i][w]==False:
		if i==n:
			res=(0)
		elif w-l[i][0]<0:
			res=(solve(i+1,w))
		else:
			a=solve(i+1,w)
			b=l[i][1]+solve(i+1,w-l[i][0])
			if b>a:
				res=(b)
			else:
				res=(a)
		dp[i][w]=res
		return(res)
	else:
		return(dp[i][w])

print(solve(0,W))

Solution (Python):
value=[0]
weight=[0]
n,W=input().split()
n=int(n)
W=int(W)
for i in range(n):
	item=list(map(int,input().split()))
	value.append(item[0])
	weight.append(item[1])

dp=[[0 for j in range(W+1)] for i in range(n+1)]
for i in range(n+1):
	for j in range(W+1):
		if i==0:
			res=0
		elif j-weight[i]<0:
			res=dp[i-1][j]
		else:
			res=max(dp[i-1][j-weight[i]]+value[i],dp[i-1][j])
		dp[i][j]=res
print(dp[n][W])

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

    
for i in range(N):
    v=goods[i][0]
    w=goods[i][1]
    for j in range(W+1):
        dp[i+1][j]=max(dp[i][j],dp[i+1][j])
        next_w=j+w
        next_v=dp[i][j]+v
        if(next_w<=W and next_v>dp[i+1][next_w]):
            dp[i+1][next_w]=next_v

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

Solution (Python):



"""
input:
4 5
4 2
5 2
2 1
8 3

output:
13
"""

import sys
from collections import namedtuple


def solve():
    for i, item in enumerate(item_list, 1):
        for cp in range(1, real_cp + 1):
            if item.w <= cp:
                
                
                
                
                values[i][cp] = max(values[i - 1][cp], item.v + values[i - 1][cp - item.w])
                
            else:
                values[i][cp] = values[i - 1][cp]
                
    return values[-1][-1]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, real_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', 'v w')
    
    item_list = [Item(v=int(v), w=int(w)) for v, w in items]

    
    values = [[0] * (real_cp + 1) for _ in range(c_items + 1)]
    ans = solve()
    print(ans)

Solution (Python):



"""
input:
4 5
4 2
5 2
2 1
8 3

output:
13
"""

import sys
from collections import namedtuple


def solve():
    for i, item in enumerate(item_list, 1):
        for cp in range(1, real_cp + 1):
            if item.w <= cp:
                values[i][cp] = max(values[i - 1][cp], values[i - 1][cp - item.w] + item.v)
            else:
                values[i][cp] = values[i - 1][cp]
    return values[-1][-1]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, real_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', 'v w')
    item_list = [Item(v=int(v), w=int(w)) for v, w in items]

    values = [[0] * (real_cp + 1) for _ in range(c_items + 1)]
    ans = solve()
    print(ans)

Solution (Python):



"""
input:
4 5
4 2
5 2
2 1
8 3

output:
13
"""

import sys
from collections import namedtuple


def solve():
    for i, item in enumerate(item_list, 1):
        for cp in range(1, real_cp + 1):
            if item.w <= cp:
                values[i][cp] = max(values[i - 1][cp], values[i - 1][cp - item.w] + item.v)
            else:
                values[i][cp] = values[i - 1][cp]
    return values[-1][-1]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, real_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', 'v w')
    item_list = (Item(v=int(v), w=int(w)) for v, w in items)

    values = tuple([0] * (real_cp + 1) for _ in range(c_items + 1))
    ans = solve()
    print(ans)

Solution (Python):



"""
input:
4 5
4 2
5 2
2 1
8 3

output:
13
"""

import sys
from collections import namedtuple


def solve():
    for i, item in enumerate(item_list, 1):
        for cp in range(1, real_cp + 1):
            if item.w <= cp:
                values[i][cp] = max(values[i - 1][cp], values[i - 1][cp - item.w] + item.v)
            else:
                values[i][cp] = values[i - 1][cp]
    return values[-1][-1]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, real_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', 'v w')
    item_list = (Item(v=int(v), w=int(w)) for v, w in items)

    values = [[0] * (real_cp + 1) for _ in range(c_items + 1)]
    ans = solve()
    print(ans)

Solution (Python):



"""
input:
4 5
4 2
5 2
2 1
8 3

output:
13
"""

import sys
from collections import namedtuple


def solve():
    for i, item in enumerate(item_list, 1):
        for cp in range(1, real_cp + 1):
            if item.w <= cp:
                values[i][cp] = max(values[i - 1][cp], values[i - 1][cp - item.w] + item.v)
            else:
                values[i][cp] = values[i - 1][cp]
    return values[-1][-1]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, real_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', 'v w')
    item_list = (Item(v=int(v), w=int(w)) for v, w in items)

    values = [[0] * (real_cp + 1) for _ in range(c_items + 1)]
    ans = solve()
    print(ans)