Problem definition.
In the knapsack problem we are given a set of objects and the capacity of the knapsack. Each object has its size and value.
The goal is to choose a subset of objects of total size not exceeding the capacity, while maximizing the sum of the objects values.
There are two variants of this problem. In the knapsack 0/1 problem each object from the objects set can be chosen only once. In the second variant called knapsack unbounded problem, each object can be chosen many times.
Solution
Knapsack 0/1 is solved using standard dynamic approach on modified sizes or values. When the values are modified we get standard \((1-\epsilon)\) approximation of the knapsack problem. When the sizes are modified we get the optimal value of the knapsack but capacity can be exceeded by \((1+\epsilon)\). The divide and conquer approach is used to retrieve the set of objects in the optimal solution. There are several versions of the algorithm depending on the type of the approximation (on size or on value).
Analogously to dynamic approach, there are two versions of each algorithm : standard and _no_output . The first one solves the knapsack 0/1 with retrieving solution and the second one omits this procedure. Although retrieving solution does not increase the complexity, it is a costly procedure.
Examples
Knapsack 0/1 example - modified values:
#include <vector>
#include <iostream>
int main() {
using Objects = std::vector<std::pair<int, int>>;
Objects objects{ { 1, 3 }, { 2, 2 }, { 3, 65 }, { 1, 1 }, { 2, 2 },
{ 4, 3 }, { 1, 1 }, { 10, 23 } };
const int capacity = 6;
auto size = [](std::pair<int, int> object) { return object.first; }
;
auto value = [](std::pair<int, int> object) { return object.second; }
;
Objects result;
std::cout << "Knapsack unbounded FPTAS on value" << std::endl;
double epsilon = 1. / 4.;
auto maxValue = paal::knapsack_0_1_on_value_fptas(
epsilon, objects, capacity, std::back_inserter(result), size, value);
std::cout << "Max value " << maxValue.first << ", Total size "
<< maxValue.second << std::endl;
for (auto o : result) {
std::cout << "{ size = " << o.first << ", value = " << o.second << "} ";
}
std::cout << std::endl;
return 0;
}
example file is knapsack_0_1_on_value_fptas_example.cpp
Knapsack 0/1 example - modified sizes:
#include <vector>
#include <iostream>
int main() {
using Objects = std::vector<std::pair<int, int>>;
Objects objects{ { 1, 3 }, { 2, 2 }, { 3, 65 }, { 1, 1 }, { 2, 2 },
{ 4, 3 }, { 1, 1 }, { 10, 23 } };
const int capacity = 6;
auto size = [](std::pair<int, int> object) { return object.first; }
;
auto value = [](std::pair<int, int> object) { return object.second; }
;
Objects result;
std::cout << "Knapsack unbounded FPTAS on size" << std::endl;
double epsilon = 1. / 4.;
auto maxValue = paal::knapsack_0_1_on_size_fptas(
epsilon, objects, capacity, std::back_inserter(result), size, value);
std::cout << "Max value " << maxValue.first << ", Total size "
<< maxValue.second << std::endl;
for (auto o : result) {
std::cout << "{ size = " << o.first << ", value = " << o.second << "} ";
}
std::cout << std::endl;
return 0;
}
example file is knapsack_0_1_on_size_fptas_example.cpp
Knapsack 0/1 example - modified values (without computing items in knapsack):
#include <vector>
#include <iostream>
int main() {
using Objects = std::vector<std::pair<int, int>>;
Objects objects{ { 1, 3 }, { 2, 2 }, { 3, 65 }, { 1, 1 }, { 2, 2 },
{ 4, 3 }, { 1, 1 }, { 10, 23 } };
const int capacity = 6;
auto size = [](std::pair<int, int> object) { return object.first; }
;
auto value = [](std::pair<int, int> object) { return object.second; }
;
std::cout << "Knapsack unbounded FPTAS on value no output" << std::endl;
double epsilon = 1. / 4.;
auto maxValue = paal::knapsack_0_1_no_output_on_value_fptas(
epsilon, objects, capacity, size, value);
std::cout << "Max value " << maxValue.first << ", Total size "
<< maxValue.second << std::endl;
return 0;
}
example file is knapsack_0_1_on_value_fptas_no_output_example.cpp
Knapsack 0/1 example - modified sizes (without computing items in knapsack):
#include <vector>
#include <iostream>
int main() {
using Objects = std::vector<std::pair<int, int>>;
Objects objects{ { 1, 3 }, { 2, 2 }, { 3, 65 }, { 1, 1 }, { 2, 2 },
{ 4, 3 }, { 1, 1 }, { 10, 23 } };
const int capacity = 6;
auto size = [](std::pair<int, int> object) { return object.first; }
;
auto value = [](std::pair<int, int> object) { return object.second; }
;
std::cout << "Knapsack unbounded FPTAS on size no output" << std::endl;
double epsilon = 1. / 4.;
auto maxValue = paal::knapsack_0_1_no_output_on_size_fptas(
epsilon, objects, capacity, size, value);
std::cout << "Max value " << maxValue.first << ", Total size "
<< maxValue.second << std::endl;
return 0;
}
example file is knapsack_0_1_on_size_fptas_no_output_example.cpp
Complexity
The algorithms works in \(O(n^2 / \epsilon)\) time and in \(O(n / \epsilon)\) memory.
References
The algorithm is described in the [23]. We use optimizations from [10]. We use dynamic algorithm for knapsack described in Knapsack Dynamic.
See Also
If you are interested in computing knapsack for very big \(n\) you might be interested in implementing [10] or a bit simpler [13]. This algorithms are linear in terms of \(n\) but are more complex in terms of \(1/\epsilon\).
1.8.5
