#include<vector>
#include<algorithm>


struct KnapsackSolver {
    struct Item {
        int weight;
        int value;
    };
    std::vector<Item> items_;
    
    void add_item(int weight, int value) {
        items_.push_back({weight, value});
    }
    
    // Exhaustive search over all the subsets of `item_set`.
    // Output resulting (total weight, total value) pairs to `results`
    void _get_subset_combinations(std::vector<Item> &item_set,
                                  std::vector<std::pair<int, int> > &results,
                                  int i=0,
                                  int total_weight = 0,
                                  int total_value = 0) {
        if(i == (int)item_set.size()) {
            results.push_back({total_weight, total_value});
            return;
        }
        _get_subset_combinations(item_set,
                                 results,
                                 i+1,
                                 total_weight,
                                 total_value);  // Don't take the item
                                 
        _get_subset_combinations(item_set,
                                 results,
                                 i+1,
                                 total_weight + item_set[i].weight,
                                 total_value + item_set[i].value);  // Take the item
    }
    
    // Clean a computed results array so we have increasing (weight, value) pairs
    void _clean_results(std::vector<std::pair<int, int> > &results) {
        std::sort(results.begin(), results.end());
        
        int size=0;  // results[size] tracks the last candidate of addition
        for(int j=0; j < (int)results.size(); j++) {
            if(results[size].first < results[j].first && results[size].second < results[j].second) {
                size++;
                std::swap(results[size], results[j]);  // Greater weight and value, so append to the end
            }
            else if (results[size].second < results[j].second) {
                std::swap(results[size], results[j]);  // Greater value at same weight, so swap with the last candidate
            }
        }
        size++;  // Last candidate is valid by default
        results.resize(size);
    }
    
    int solve_knapsack_problem(int capacity) {
        // First we divide items into two parts of rougly equal size
        int left_size = items_.size()/2;
        std::vector<Item> left_items(items_.begin(), items_.begin() + left_size);
        std::vector<Item> right_items(items_.begin() + left_size, items_.end());
        
        // Next we find all arrangements for both halves and clean them
        std::vector<std::pair<int, int> > left_results, right_results;
        _get_subset_combinations(left_items, left_results);
        _get_subset_combinations(right_items, right_results);
        
        _clean_results(left_results);
        _clean_results(right_results);
        
        // Finally go through left-side results and right-side results in opposite order in order to find the optimal
        // solution to the full item set
        int result_value = 0;
        for(int i=0, j=right_results.size()-1; i < (int)left_results.size(); i++) {
            while(j >= 0 && left_results[i].first + right_results[j].first > capacity) {
                j--;  // Decrement j until the weights of left_result i and right_result j fit within knapsack
            }
            if(j >= 0) {
                // Got a valid combination, now update the result value
                result_value = std::max(result_value, left_results[i].second + right_results[j].second);
            }
        }
        
        return result_value;
    }
};
 
int main() {
    KnapsackSolver solver;
    solver.add_item(5, 7);
    solver.add_item(4, 4);
    solver.add_item(2, 4);
    int result = solver.solve_knapsack_problem(6);
}