knapsack running time code example

Example: knapsack problem

// memory efficient and iterative approach to the knapsack problem

#include <bits/stdc++.h>
using namespace std;

// n is the number of items
// w is the knapsack's capacity
int n, w;

int main() {
/*
input format:
n w
value_1 cost_1
value_2 cost_2
.
.
value_n cost_n
*/
    cin >> n >> w;
  	vector<long long> dp(w + 1, 0);

    for (int i = 0; i < n; ++i) {
        int value, cost;
        cin >> value >> cost;
        for (int j = w; j >= cost; --j)
            dp[j] = max(dp[j], value + dp[j - cost]);
    }

    // the answer is dp[w]
    cout << dp[w];
}