knapsack_greedy.hpp
Go to the documentation of this file.
1 //=======================================================================
2 // Copyright (c) 2013 Piotr Wygocki
3 //
5 // accompanying file LICENSE_1_0.txt or copy at
7 //=======================================================================
8
17 #ifndef PAAL_KNAPSACK_GREEDY_HPP
18 #define PAAL_KNAPSACK_GREEDY_HPP
19
22
23 #include <boost/iterator/counting_iterator.hpp>
24 #include <boost/range/algorithm/remove_if.hpp>
25
26 namespace paal {
27 namespace detail {
28
29 // if the knapsack dynamic table is indexed by values,
30 // the procedure to find the best element is to find the biggest index i in the
31 // table that
32 // *i is smaller than given threshold(capacity)
33 template <typename MaxValueType, typename SizeType>
35  get_max_element_on_value_indexed_collection(MaxValueType maxValue)
36  : m_max_value(maxValue) {}
37
38  template <typename Iterator, typename Comparator>
39  Iterator operator()(Iterator begin, Iterator end, Comparator compare) {
40  auto compareOpt = make_less_pointees_t(compare);
41  // traverse in reverse order, skip the first
42  for (auto iter = end - 1; iter != begin; --iter) {
43  if (*iter && compareOpt(m_max_value, *iter)) {
44  return iter;
45  }
46  }
47
48  return end;
49  }
50
51  private:
52  MaxValueType m_max_value;
53 };
54
55 // if the knapsack dynamic table is indexed by sizes,
56 // the procedure to find the best element is to find the biggest
57 // index i in the table that maximizes *i
58 template <typename ValueType>
60  template <typename Iterator, typename Comparator>
61  Iterator operator()(Iterator begin, Iterator end, Comparator compare) {
62  return std::max_element(begin, end, make_less_pointees_t(compare));
63  }
64 };
65
66 template <typename KnapsackData,
67  typename Is_0_1_Tag,
68  typename Value = typename KnapsackData::value,
69  typename Size = typename KnapsackData::size>
70 typename KnapsackData::return_type knapsack_general_two_app(
71  KnapsackData knapsack_data, Is_0_1_Tag is_0_1_Tag) {
72
73  using ObjectRef = typename KnapsackData::object_ref;
74
75  static_assert(std::is_arithmetic<Value>::value &&
76  std::is_arithmetic<Size>::value,
77  "Size type and Value type must be arithmetic types");
78  auto capacity = knapsack_data.get_capacity();
79
80  auto bad_size = [=](ObjectRef o){return knapsack_data.get_size(o) > capacity;};
81
82  auto objects = boost::remove_if<boost::return_begin_found>(knapsack_data.get_objects(), bad_size);
83
84  if (boost::empty(objects)) {
85  return std::pair<Value, Size>();
86  }
87
88  // finding the element with the greatest density
89  auto greedyFill = get_greedy_fill(
90  make_knapsack_data(
91  objects, capacity,
92  knapsack_data.get_size(),
93  knapsack_data.get_value(),
94  knapsack_data.get_output_iter()), is_0_1_Tag);
95
96  // finding the biggest set elements with the greatest density
97  // this is actually small optimization compare to original algorithm
98  // note that largest is transformed iterator!
99  auto largest = max_element_functor(objects, knapsack_data.get_value());
100
101  if (*largest > std::get<0>(greedyFill)) {
102  knapsack_data.out(*largest.base());
103  return std::make_pair(*largest, knapsack_data.get_size(*largest.base()));
104  } else {
105  greedy_to_output(std::get<2>(greedyFill), knapsack_data.get_output_iter(), is_0_1_Tag);
106  return std::make_pair(std::get<0>(greedyFill), std::get<1>(greedyFill));
107  }
108 }
109
110 template <typename Range>
112  using ref = typename boost::range_reference<Range>::type;
113  static const bool value = std::is_const<ref>::value ||
114  !std::is_reference<ref>::value;
115 };
116 }
117 }
118 #endif // PAAL_KNAPSACK_GREEDY_HPP
auto max_element_functor(Range &&range, Functor f)