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.
Both variants of the knapsack problem are solved using the dynamic approach. In our library, both variants of the knapsack problem are solved using dynamic programming. Our algorithm is actually composed out of two algorithms, and the faster of these two is chosen. In the first one the dynamic table is indexed by total size of the items, whereas in the second one it is indexed by values. In the size indexed case, we construct a table of size \([0-capacity]\). Each cell of the table contains an information about the best value for this size of knapsack. The value indexed case is analogous. The algorithm proceeds in rounds in which one new object is added to the table.
In the knapsack 0/1 it is impossible to read the resulting set of objects directly from the computed dynamic table without additional computation. We can only read the optimal value of the knapsack and the size of the optimal set. In this case the divide and conquer approach is used to retrieve the set of objects in the optimal solution. The algorithm divides the set of objects into two groups and computes the dynamic table for both groups. In the next step algorithm finds cells in the both computed tables satisfying the optimality conditions and proceed recursively. (see  for more details).
Knapsack unbounded example:
example file is knapsack_unbounded_example.cpp
Knapsack 0/1 example:
example file is knapsack_0_1_example.cpp
Knapsack 0/1 example (without computing items in knapsack) example:
example file is knapsack_0_1_no_output_example.cpp
The library provides knapsack_unbounded function which solves the unbounded version of the problem and two versions of knapsack 0/1 problem : knapsack_0_1 and knapsack_0_1_no_output.
The first one solves the knapsack 0/1 with retrieving solution whereas the second one without this procedure. Although retrieving solution does not increase the overall complexity, it is a costly procedure.
The algorithms works in \( O(min(Capacity, Opt) NumberOfObjects)\) time and in \(O(min(Capacity, Opt))\) memory, where Opt is the optimal value of the knapsack.
The algorithm is described in the