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

This solution implements the greedy algorithm. The algorithm proceeds in rounds in which one new object is added to the set of objects. The new object added to the set is the one with the biggest average value (value to size ratio). The algorithm returns the better of the following two sets:

the greedy chosen set of the size not greater than the capacity
or the most valuable item with the size not greater than the capacity of the knapsack.

Note that the algorithm might change the order of objects in the range.

Examples

Knapsack 0/1 example:

#include "paal/greedy/knapsack_0_1_two_app.hpp"
#include <vector>
#include <iostream>
int main() {
    const int capacity = 6;
    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 } };
    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_two_app(
        objects, capacity, std::back_inserter(result), value, size);
    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_two_app_example.cpp

Knapsack example:

#include "paal/greedy/knapsack_unbounded_two_app.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_two_app(
        objects, capacity,
        std::back_inserter(result), value, size);
    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_two_app_example.cpp

Approximation ratio equals 2.

Complexity

The algorithms works in \(O(n log(n))\) time and in \(O(1)\) memory where n is the number of objects.

References

The algorithm is described in the [23]