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.size(); ++i) {
if (weight[i] < max_weight)
last[weight[i]] = max(last[weight[i]], value[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})$$.