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++:
int max_value(std::vector<std::vector<int>> const &weights,
std::vector<std::vector<int>> const &values,
int max_weight) {
if (weights.empty()) {
return 0;
}
std::vector<int> last(max_weight + 1, -1);
for (int i = 0; i < weights[0].size(); ++i) {
if (weights[0][i] < max_weight) {
last[weights[0][i]] = std::max(last[weights[0][i]], values[0][i]);
}
}
std::vector<int> curr(max_weight + 1);
for (int i = 1; i < weights.size(); ++i) {
std::fill(curr.begin(), curr.end(), -1);
for (int j = 0; j < weights[i].size(); ++j) {
for (int k = weights[i][j]; k <= max_weight; ++k) {
if (last[k - weights[i][j]] > 0) {
curr[k] = std::max(curr[k], last[k - weights[i][j]] + values[i][j]);
}
}
}
std::swap(curr, last);
}
return *std::max_element(last.begin(), last.end());
}
int main(int argc, char const *argv[]) {
std::vector<int> values_class_1;
values_class_1.push_back(2);
values_class_1.push_back(3);
std::vector<int> weights_class_1;
weights_class_1.push_back(3);
weights_class_1.push_back(4);
std::vector<int> values_class_2;
values_class_2.push_back(1);
values_class_2.push_back(2);
std::vector<int> weights_class_2;
weights_class_2.push_back(2);
weights_class_2.push_back(3);
std::vector<std::vector<int>> values;
values.push_back(values_class_1);
values.push_back(values_class_2);
std::vector<std::vector<int>> weights;
weights.push_back(weights_class_1);
weights.push_back(weights_class_2);
int max_weight = 7;
std::cout << max_value(weights, values, max_weight) << std::endl; // 5
return 0;
}
The time complexity of this solution is \(O(C\sum_{i=1}^{k}{N_i})\).