All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Macros Pages
knapsack_0_1_two_app.hpp
Go to the documentation of this file.
1 //=======================================================================
2 // Copyright (c) 2013 Piotr Wygocki
3 //
4 // Distributed under the Boost Software License, Version 1.0. (See
5 // accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 //=======================================================================
15 #ifndef PAAL_KNAPSACK_0_1_TWO_APP_HPP
16 #define PAAL_KNAPSACK_0_1_TWO_APP_HPP
17 
19 #include "paal/utils/functors.hpp"
22 
23 #include <boost/iterator/counting_iterator.hpp>
24 #include <boost/iterator/filter_iterator.hpp>
25 #include <boost/range/algorithm/find_if.hpp>
26 #include <boost/range/algorithm/sort.hpp>
27 
28 #include <type_traits>
29 #include <utility>
30 
31 namespace paal {
32 
33 namespace detail {
34 template <typename KnapsackData,
35  typename ObjectIter = typename KnapsackData::object_iter,
36  typename ObjectRef = typename KnapsackData::object_ref,
37  typename Size = typename KnapsackData::size,
38  typename Value = typename KnapsackData::value>
39 std::tuple<Value, Size, boost::iterator_range<ObjectIter>>
40 get_greedy_fill(KnapsackData knap_data, zero_one_tag) {
41 
42  auto density = knap_data.get_density();
43  auto compare = utils::make_functor_to_comparator(density, utils::greater{});
44  // objects must be lvalue because we return a subrange of this range
45  auto &objects = knap_data.get_objects();
46 
47  // finding the biggest set elements with the greatest density
48  boost::sort(objects, compare);
49 
50  Value valueSum{};
51  Size sizeSum{};
52  auto range = boost::find_if<boost::return_begin_found>(
53  objects, [ =, &sizeSum, &valueSum](ObjectRef obj) {
54  auto newSize = sizeSum + knap_data.get_size(obj);
55  if (newSize > knap_data.get_capacity()) {
56  return true;
57  }
58  sizeSum = newSize;
59  valueSum += knap_data.get_value(obj);
60  return false;
61  });
62  return std::make_tuple(valueSum, sizeSum, range);
63 }
64 
65 template <typename ObjectsRange, typename OutputIter>
66 void greedy_to_output(ObjectsRange range, OutputIter & out, zero_one_tag) {
67  for (auto obj : range) {
68  *out = obj;
69  ++out;
70  }
71 }
72 
73 }
74 
76 template <typename OutputIterator, typename Objects, typename ObjectSizeFunctor,
77  typename ObjectValueFunctor,
78  // this enable if assures that range can be permuted
79  typename std::enable_if<
80  !detail::is_range_const<Objects>::value>::type * = nullptr>
81 typename detail::knapsack_base<Objects, ObjectSizeFunctor,
82  ObjectValueFunctor>::return_type
84  Objects &&objects,
85  typename detail::FunctorOnRangePValue<ObjectSizeFunctor, Objects> capacity,
86  OutputIterator out, ObjectValueFunctor value, ObjectSizeFunctor size) {
87  return detail::knapsack_general_two_app(
88  detail::make_knapsack_data(std::forward<Objects>(objects), capacity,
89  size, value, out),
91 }
92 }
93 #endif // PAAL_KNAPSACK_0_1_TWO_APP_HPP
auto make_functor_to_comparator(Functor functor, Compare compare=Compare())
make for functor to comparator
Definition: functors.hpp:654
This file contains set of simple useful functors or functor adapters.
greater functor
Definition: functors.hpp:478
detail::knapsack_base< Objects, ObjectSizeFunctor, ObjectValueFunctor >::return_type knapsack_0_1_two_app(Objects &&objects, typename detail::FunctorOnRangePValue< ObjectSizeFunctor, Objects > capacity, OutputIterator out, ObjectValueFunctor value, ObjectSizeFunctor size)
detail