fill_knapsack_dynamic_table.hpp

Go to the documentation of this file.

//=======================================================================
// Copyright (c) 2013 Piotr Wygocki
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#ifndef PAAL_FILL_KNAPSACK_DYNAMIC_TABLE_HPP
#define PAAL_FILL_KNAPSACK_DYNAMIC_TABLE_HPP

#include "paal/utils/knapsack_utils.hpp"

namespace paal {
template <typename ValueIterator, typename Objects, typename ObjectSizeFunctor,
          typename Combine, typename Compare, typename Init,
          typename GetPositionRange>
detail::FunctorOnRangePValue<ObjectSizeFunctor, Objects>
fill_knapsack_dynamic_table(ValueIterator valuesBegin, ValueIterator valuesEnd,
                            Objects &&objects, ObjectSizeFunctor size,
                            Combine combine, Compare compare, Init init,
                            GetPositionRange get_range) {
    using Size = detail::FunctorOnRangePValue<ObjectSizeFunctor, Objects>;

    Size maxSize = std::distance(valuesBegin, valuesEnd);

    std::fill(valuesBegin + 1, valuesEnd, boost::none);
    init(*valuesBegin);

    auto posRange = get_range(0, maxSize);

    auto objIter = std::begin(objects);
    auto oEnd = std::end(objects);
    for (; objIter != oEnd; ++objIter) {
        auto &&obj = *objIter;
        auto objSize = size(obj);
        // for each position, from largest to smallest
        for (auto pos : posRange) {
            auto stat = *(valuesBegin + pos);
            // if position was reached before
            if (stat != boost::none) {
                Size newPos = pos + objSize;
                auto &newStat = *(valuesBegin + newPos);
                // if we're not exceeding maxSize
                if (newPos < maxSize) {
                    auto newValue = combine(stat, objIter);
                    // if the value is bigger than previous
                    if (newStat == boost::none || compare(newStat, newValue)) {
                        // update value
                        newStat = newValue;
                    }
                }
            }
        }
    }
    return maxSize - 1;
}

}      
#endif // PAAL_FILL_KNAPSACK_DYNAMIC_TABLE_HPP