Knapsack problem

main.cpp

#include <iostream>
#include <vector>
#include <utility>
#include <functional>

using namespace std;

int knapsack_problem(vector<pair<int, int>> &items, int capacity) {
    function<int(vector<pair<int, int>> &, int, int)> recursion;
    recursion = [&](vector<pair<int, int>> &items, int i, int j) -> int {
        if (((i == 0) && (j >= 0)) || ((i >= 0) && (j == 0)))
            return 0;

        if ((j - items[i - 1].first) >= 0)
            return max(recursion(items, i - 1, j),
                       items[i - 1].second + recursion(items, i - 1, j - items[i - 1].first));
        else
            return recursion(items, i - 1, j);
    };

    return recursion(items, items.size(), capacity);
}

int main() {
    {
        vector<pair<int, int>> items{{3, 20}};

        cout << knapsack_problem(items, 4) << '$' << endl;
    }

    {
        vector<pair<int, int>> items{{2, 12},
                                     {3, 20}};

        cout << knapsack_problem(items, 4) << '$' << endl;
    }

    {
        vector<pair<int, int>> items{{2, 12},
                                     {1, 10},
                                     {3, 20},
                                     {2, 15}};

        cout << knapsack_problem(items, 5) << '$' << endl;
    }

    return 0;
}