Knapsack Dynamic

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

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 [16] for more details).

Examples

Knapsack unbounded example:

#include "paal/dynamic/knapsack_unbounded.hpp"

#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" << std::endl;
    auto maxValue = paal::knapsack_unbounded(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_unbounded_example.cpp

Knapsack 0/1 example:

#include "paal/dynamic/knapsack_0_1.hpp"

#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 0 / 1" << std::endl;
    auto maxValue = paal::knapsack_0_1(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_example.cpp

Knapsack 0/1 example (without computing items in knapsack) example:

#include "paal/dynamic/knapsack_0_1.hpp"

#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 0 / 1 no output" << std::endl;
    auto maxValue =
        paal::knapsack_0_1_no_output(objects, capacity, size, value);

    std::cout << "Max value " << maxValue.first << ", Total size "
              << maxValue.second << std::endl;

    return 0;
}

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.

Complexity

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.

References

The algorithm is described in the [16]

See Also

• Knapsack 0/1 FPTAS
• Knapsack Greedy