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_max = map(int, raw_input().split())

value  = []
weight = []

for i in range(N):
	x,y = map(int,raw_input().split())
	value.append(x)
	weight.append(y)
	
dp = [[0 for i in range(W_max+1)] for j in range(N+1)]


for i in range(0,N):
	for w in range(W_max+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_max]

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


'''
dp[i+1][ww]: i番目までの品物から容量がwを超えないように入れた時の価値の合計の最大値
0 <= ww <= W
0 <= i <= N
'''


dp = [[0]*(W+1)] 

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

print(dp[N][W])