knapsack algorithm in python

1# a dynamic approach
2# Returns the maximum value that can be stored by the bag
3def knapSack(W, wt, val, n):
4   K = [[0 for x in range(W + 1)] for x in range(n + 1)]
5   #Table in bottom up manner
6   for i in range(n + 1):
7      for w in range(W + 1):
8         if i == 0 or w == 0:
9            K[i][w] = 0
10         elif wt[i-1] <= w:
11            K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
12         else:
13            K[i][w] = K[i-1][w]
14   return K[n][W]
15#Main
16val = [50,100,150,200]
17wt = [8,16,32,40]
18W = 64
19n = len(val)
20print(knapSack(W, wt, val, n))

1// memory efficient and iterative approach to the knapsack problem
2
3#include <bits/stdc++.h>
4using namespace std;
5
6// n is the number of items
7// w is the knapsack's capacity
8int n, w;
9
10int main() {
11/*
12input format:
13n w
14value_1 cost_1
15value_2 cost_2
16.
17.
18value_n cost_n
19*/
20    cin >> n >> w;
21  	vector<long long> dp(w + 1, 0);
22
23    for (int i = 0; i < n; ++i) {
24        int value, cost;
25        cin >> value >> cost;
26        for (int j = w; j >= cost; --j)
27            dp[j] = max(dp[j], value + dp[j - cost]);
28    }
29
30    // the answer is dp[w]
31    cout << dp[w];
32}