#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});
    }
    
    int solve_knapsack_problem(int capacity) {
        // Initializes the 2D array containing solutions to the subproblems
        // sub_problem[x][c] = greatest attainable value for knapsack capacity c when using first x items
        std::vector<std::vector<int> > sub_problem(items_.size() + 1, std::vector<int>(capacity+1, 0));
        
        for(int x=1; x <= (int)items_.size(); x++) {
            Item item = items_[x-1];
            for(int c=0; c <= capacity; c++) {
                // Apply the relation formula. Fundamentally, we either use item x or we don't, and then we can use
                // the solution for the smaller sub-problem
                sub_problem[x][c] = sub_problem[x-1][c];
                if(c >= item.weight) {
                    sub_problem[x][c] = std::max(sub_problem[x][c], sub_problem[x-1][c-item.weight] + item.value);
                }
            }
        }
        return sub_problem[items_.size()][capacity];  // Return 'sub-problem' corresponding to the full problem
    }
};
 
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);
}