 |
Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
|
|
Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
|
Yet another variant of FirstFewValues or MaxBoundedSubsetSum. More...
#include <util.h>
Public Member Functions | |
| absl::Span< const int64_t > | Compute (absl::Span< const int64_t > elements, int64_t maximum_sum, bool abort_if_maximum_reached=false) |
| absl::Span< const int64_t > | SortedSums () const |
| Returns the possible subset sums sorted. | |
Yet another variant of FirstFewValues or MaxBoundedSubsetSum.
| absl::Span< const int64_t > operations_research::sat::SortedSubsetSums::Compute | ( | absl::Span< const int64_t > | elements, |
| int64_t | maximum_sum, | ||
| bool | abort_if_maximum_reached = false ) |
Computes all the possible subset sums in [0, maximum_sum]. Returns them sorted. All elements must be non-negative.
If abort_if_maximum_reached is true, we might not return all possible subset sums as we stop the exploration as soon as a subset sum is equal to maximum_sum. When this happen, we guarantee that the last element returned will be maximum_sum though.
Worst case complexity is in O(2^num_elements) if maximum_sum is large or O(maximum_sum * num_elements) if that is lower.
Optimization: If all the sums in [0, maximum_sum] are already reachable we can abort early since no new reachable sum wil be discovered.
Early abort when asked if we already reached maximum_sum.
We merge sort sums_ and sums_ + e into new_sums_.
We are sure of this since we will break only when to_push > maximum_sum and we are guarantee to have pushed all sums below "to_push" before, that includes all the initial sums in sums_.
|
inline |
1.13.2