The 0-1 Knapsack problem is a popular combinatorial optimization problem:

Given a set of n items, each having a value \( p_i \) and a weight of \( w_i \), find a subset of these items such that the total value is maximized, while keeping the total weight of the items under a given constant weight capacity W.

Formally, we need to maximize \( \sum_{i=1}^{n}{p_{i}f_{i}} \), while subjecting to \( \sum_{i=1}^{n}{w_{i}f_{i}} \le W \), \( f_i \in \{0, 1\}, \forall i \in \{ 1, …, n\} \).

This problem has a nice Dynamic Programming solution, which runs in \( O(nW) \) time (pseudopolynomial). It is a computationally hard problem, as it is NP-Complete, but it has many important applications.

It has many known variations, one of which is the Multiple Choice Knapsack Problem. In this case, the items are subdivided into \( k \) classes, each having \( N_i \) items, and exactly one item must be taken from each class. Formally, we need to maximize \( \sum_{i=1}^{k}\sum_{j \in N_i}{p_{ij}x_{ij}} \), while subjecting to \( \sum_{i=1}^{k}\sum_{j \in N_i}{w_{ij}x_{ij}} \le W\), with \( \sum_{j \in N_i}{x_{ij}} = 1, \forall i \in \{1, …, k\}\) and \( x_{ij} \in \{0, 1\}, \forall i \in \{1, …, k\} \) and \( \forall j \in N_i \).

To solve this problem, we will use a Dynamic Programming approach. The recursive equation that describes the relation between the overlapping subproblems is the following:

\[ Value[i, j] = \max_{1 \le u \le N_i, w_{iu} \le j}\{ Value[i-1, j-w_{iu}] + p_{iu} \} \]

Below is an implementation in C++:

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int max_value(const vector<vector<int>>& weight,
               const vector<vector<int>>& value,
               int max_weight) {
    if (weight.empty())
        return 0;

    vector<int> last(max_weight + 1, -1);
    for (int i = 0; i < weight[0].size(); ++i) {
        if (weight[0][i] < max_weight)
            last[weight[0][i]] = max(last[weight[0][i]], value[0][i]);
    }

    vector<int> current(max_weight + 1);
    for (int i = 1; i < weight.size(); ++i) {
        fill(current.begin(), current.end(), -1);
        for (int j = 0; j < weight[i].size(); ++j) {
            for (int k = weight[i][j]; k <= max_weight; ++k) {
                if (last[k - weight[i][j]] > 0)
                    current[k] = max(current[k],
                                     last[k - weight[i][j]] + value[i][j]);
            }
        }
        swap(current, last);
    }

    return *max_element(last.begin(), last.end());
}

// driver code
int main(int argc, char const* argv[]) {
    vector<int> values_class_1;
    values_class_1.push_back(2);
    values_class_1.push_back(3);

    vector<int> weights_class_1;
    weights_class_1.push_back(3);
    weights_class_1.push_back(4);

    vector<int> values_class_2;
    values_class_2.push_back(1);
    values_class_2.push_back(2);

    vector<int> weights_class_2;
    weights_class_2.push_back(2);
    weights_class_2.push_back(3);

    vector<vector<int>> values;
    values.push_back(values_class_1);
    values.push_back(values_class_2);
    vector<vector<int>> weights;
    weights.push_back(weights_class_1);
    weights.push_back(weights_class_2);

    int max_weight = 7;

    cout << max_value(weights, values, max_weight) << endl;

    return 0;
}

The time complexity of this solution is \(O(C\sum_{i=1}^{k}{N_i})\).