All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Macros Pages
knapsack_0_1.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_HPP
16 #define PAAL_KNAPSACK_0_1_HPP
17 
18 #include "paal/utils/functors.hpp"
21 #include "paal/utils/irange.hpp"
25 
26 #include <boost/range/adaptor/reversed.hpp>
27 #include <boost/function_output_iterator.hpp>
28 #include <boost/optional.hpp>
29 
30 #include <vector>
31 
32 namespace paal {
33 
34 namespace detail {
35 
41  template <typename T>
42  auto operator()(T begin, T end)
43  ->decltype(irange(begin, end) | boost::adaptors::reversed) {
44  return irange(begin, end) | boost::adaptors::reversed;
45  }
46 };
47 
57 template <typename Objects, typename ObjectSizeFunctor,
58  typename ObjectValueFunctor, typename Comparator>
59 class Knapsack_0_1 {
61  using SizeType = typename base::SizeType;
62  using ValueType = typename base::ValueType;
63  using ObjectType = typename base::ObjectType;
64  using ObjectRef = typename base::ObjectRef;
65  using ReturnType = typename base::return_type;
66  using ValueOrNull = boost::optional<ValueType>;
67  static_assert(std::is_integral<SizeType>::value,
68  "Size type must be integral");
69  using ValueOrNullVector = std::vector<ValueOrNull>;
70 
71  public:
72 
73  Knapsack_0_1(ObjectSizeFunctor size, ObjectValueFunctor value,
74  Comparator compare = Comparator())
75  : m_size(size), m_value(value), m_comparator(compare) {}
76 
81  template <typename GetBestElement>
82  ReturnType solve(Objects objects, SizeType capacity,
83  GetBestElement getBest) {
84  m_object_on_size.resize(capacity + 1);
85  fill_table(m_object_on_size, objects, capacity);
86  auto maxValue = getBest(m_object_on_size.begin(),
87  m_object_on_size.end(), m_comparator);
88 
89  if (maxValue != m_object_on_size.end()) {
90  return ReturnType(**maxValue, maxValue - m_object_on_size.begin());
91  } else {
92  return ReturnType(ValueType{}, SizeType{});
93  }
94  }
95 
96  //@brief here we find actual solution
97  // that is, the chosen objects
98  // this is done by simple divide and conquer strategy
99  template <typename OutputIterator>
100  void retrieve_solution(ValueType maxValue, SizeType size, Objects objects,
101  OutputIterator & out) const {
102  m_object_on_size.resize(size + 1);
103  m_object_on_size_rec.resize(size + 1);
104  retrieve_solution_rec(maxValue, size, std::begin(objects),
105  std::end(objects), out);
106  }
107 
108  private:
109  template <typename OutputIterator, typename ObjectsIter>
110  void retrieve_solution_rec(ValueType maxValue, SizeType capacity,
111  ObjectsIter oBegin, ObjectsIter oEnd,
112  OutputIterator & out) const {
113  if (maxValue == ValueType()) {
114  return;
115  }
116 
117  auto objNr = std::distance(oBegin, oEnd);
118  assert(objNr);
119 
120  // boundary case only one object left
121  if (objNr == 1) {
122  assert(m_value(*oBegin) == maxValue);
123  *out = *oBegin;
124  ++out;
125  return;
126  }
127 
128  // main case, at least 2 objects left
129  auto midle = oBegin + objNr / 2;
130  fill_table(m_object_on_size, boost::make_iterator_range(oBegin, midle),
131  capacity);
132  fill_table(m_object_on_size_rec,
133  boost::make_iterator_range(midle, oEnd), capacity);
134 
135  SizeType capacityLeftPartInOptimalSolution{};
136  for (auto capacityLeftPart : irange(capacity + 1)) {
137  auto left = m_object_on_size[capacityLeftPart];
138  auto right = m_object_on_size_rec[capacity - capacityLeftPart];
139  if (left && right) {
140  if (*left + *right == maxValue) {
141  capacityLeftPartInOptimalSolution = capacityLeftPart;
142  break;
143  }
144  }
145  }
146  auto left = m_object_on_size[capacityLeftPartInOptimalSolution];
147  auto right =
148  m_object_on_size_rec[capacity - capacityLeftPartInOptimalSolution];
149  assert(left && right && *left + *right == maxValue);
150 
151  retrieve_solution_rec(*left, capacityLeftPartInOptimalSolution, oBegin,
152  midle, out);
153  retrieve_solution_rec(
154  *right, capacity - capacityLeftPartInOptimalSolution, midle, oEnd,
155  out);
156  }
157 
158  template <typename ObjectsRange>
159  void fill_table(ValueOrNullVector &values, ObjectsRange &&objects,
160  SizeType capacity) const {
162  values.begin(), values.begin() + capacity + 1,
163  std::forward<ObjectsRange>(objects), m_size,
164  [&](ValueOrNull val,
165  typename boost::range_iterator<ObjectsRange>::type obj) {
166  return *val + m_value(*obj);
167  },
168  [&](ValueOrNull left, ValueOrNull right) {
169  return m_comparator(*left, *right);
170  },
171  [](ValueOrNull & val) {
172  val = ValueType{};
173  },
174  Knapsack_0_1_get_position_range{});
175  }
176 
177  ObjectSizeFunctor m_size;
178  ObjectValueFunctor m_value;
179  Comparator m_comparator;
180  mutable ValueOrNullVector m_object_on_size;
181  mutable ValueOrNullVector m_object_on_size_rec;
182 };
183 
184 template <typename Objects, typename ObjectSizeFunctor,
185  typename ObjectValueFunctor, typename Comparator>
186 Knapsack_0_1<Objects, ObjectSizeFunctor, ObjectValueFunctor, Comparator>
187 make_knapsack_0_1(ObjectSizeFunctor size, ObjectValueFunctor value,
188  Comparator comp) {
189  return Knapsack_0_1<Objects, ObjectSizeFunctor, ObjectValueFunctor,
190  Comparator>(size, value, comp);
191 }
192 
193 template <typename Knapsack, typename IndexType, typename ValueType,
194  typename Objects, typename OutputIterator>
195 void retrieve_solution(const Knapsack &knapsack, ValueType maxValue,
196  IndexType size, Objects &&objects, OutputIterator & out,
197  retrieve_solution_tag) {
198  knapsack.retrieve_solution(maxValue, size, objects, out);
199 }
200 
201 template <typename Knapsack, typename IndexType, typename ValueType,
202  typename Objects, typename OutputIterator>
203 void retrieve_solution(const Knapsack &knapsack, ValueType maxValue,
204  IndexType size, Objects &&objects, OutputIterator & out,
205  no_retrieve_solution_tag) {}
206 
211 template <typename KnapsackData, typename retrieve_solution_tag>
212 auto knapsack(KnapsackData knap_data, zero_one_tag, integral_size_tag,
213  retrieve_solution_tag retrieve_solutionTag) {
214  using Value = typename KnapsackData::value;
215 
216  auto knapsack = make_knapsack_0_1<typename KnapsackData::objects>(
217  knap_data.get_size(), knap_data.get_value(), utils::less{});
218  auto value_size =
219  knapsack.solve(knap_data.get_objects(), knap_data.get_capacity(),
221  retrieve_solution(knapsack, value_size.first, value_size.second,
222  knap_data.get_objects(), knap_data.get_output_iter(),
223  retrieve_solutionTag);
224  return value_size;
225 }
226 
231 template <typename KnapsackData, typename retrieve_solution_tag>
232 auto knapsack(KnapsackData knap_data, zero_one_tag, integral_value_tag,
233  retrieve_solution_tag retrieve_solutionTag) {
234  using Value = typename KnapsackData::value;
235  using Size = typename KnapsackData::size;
236 
237  auto knapsack = make_knapsack_0_1<typename KnapsackData::objects>(
238  knap_data.get_value(), knap_data.get_size(), utils::greater{});
239  auto maxValue = get_value_bound(knap_data, zero_one_tag{}, upper_tag{});
240  auto value_size = knapsack.solve(
241  knap_data.get_objects(), maxValue,
243  Value>(
244  boost::optional<Size>(knap_data.get_capacity() + 1)));
245  retrieve_solution(knapsack, value_size.first, value_size.second,
246  knap_data.get_objects(), knap_data.get_output_iter(),
247  retrieve_solutionTag);
248  return std::make_pair(value_size.second, value_size.first);
249 }
250 
251 } // detail
252 
266 template <typename Objects, typename OutputIterator, typename ObjectSizeFunctor,
267  typename ObjectValueFunctor = utils::return_one_functor>
268 auto knapsack_0_1(Objects &&objects,
269  detail::FunctorOnRangePValue<ObjectSizeFunctor, Objects>
270  capacity, // capacity is of size type
271  OutputIterator out, ObjectSizeFunctor size,
272  ObjectValueFunctor value = ObjectValueFunctor{}) {
273 
274  return detail::knapsack_check_integrality(
275  detail::make_knapsack_data(std::forward<Objects>(objects), capacity,
276  size, value, out),
277  detail::zero_one_tag{});
278 }
279 
293 template <typename Objects, typename ObjectSizeFunctor,
294  typename ObjectValueFunctor = utils::return_one_functor>
295 auto knapsack_0_1_no_output(Objects &&objects,
296  detail::FunctorOnRangePValue<ObjectSizeFunctor, Objects>
297  capacity, // capacity is of size type
298  ObjectSizeFunctor size,
299  ObjectValueFunctor value = ObjectValueFunctor{}) {
300  auto out = boost::make_function_output_iterator(utils::skip_functor{});
301  return detail::knapsack_check_integrality(
302  detail::make_knapsack_data(
303  std::forward<Objects>(objects), capacity, size, value, out),
304  detail::zero_one_tag{}, detail::no_retrieve_solution_tag{});
305 }
306 
307 } // paal
308 
309 #endif // PAAL_KNAPSACK_0_1_HPP
less functor
Definition: functors.hpp:497
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)
Computes dynamic algorithm table (valuesBegin, valuesEnd) The values collection has element type Valu...
For 0/1 knapsack dynamic algorithm for given element the table has to be traversed from the highest t...
auto knapsack_0_1_no_output(Objects &&objects, detail::FunctorOnRangePValue< ObjectSizeFunctor, Objects > capacity, ObjectSizeFunctor size, ObjectValueFunctor value=ObjectValueFunctor{})
Solution to Knapsack 0/1 problem, without retrieving the objects in the solution. ...
auto irange(T begin, T end)
irange
Definition: irange.hpp:22
ReturnType solve(Objects objects, SizeType capacity, GetBestElement getBest)
Function solves dynamic programming problem.
This file contains set of simple useful functors or functor adapters.
Functor does nothing.
Definition: functors.hpp:52
greater functor
Definition: functors.hpp:478
auto knapsack_0_1(Objects &&objects, detail::FunctorOnRangePValue< ObjectSizeFunctor, Objects > capacity, OutputIterator out, ObjectSizeFunctor size, ObjectValueFunctor value=ObjectValueFunctor{})
Solution to Knapsack 0/1 problem.
This class helps solving 0/1 knapsack problem. Function solve returns the optimal value Function Retr...