 |
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
|
Similar to MaxBoundedSubsetSum() above but use a different algo. More...
#include <util.h>
Public Member Functions | |
| int64_t | MaxSubsetSum (absl::Span< const int64_t > elements, int64_t bin_size) |
| double | ComplexityEstimate (int num_elements, int64_t bin_size) |
Similar to MaxBoundedSubsetSum() above but use a different algo.
| double operations_research::sat::MaxBoundedSubsetSumExact::ComplexityEstimate | ( | int | num_elements, |
| int64_t | bin_size ) |
Returns an estimate of how many elementary operations MaxSubsetSum() is going to take.
| int64_t operations_research::sat::MaxBoundedSubsetSumExact::MaxSubsetSum | ( | absl::Span< const int64_t > | elements, |
| int64_t | bin_size ) |
If we pack the given elements into a bin of size 'bin_size', returns largest possible sum that can be reached.
This implementation allow to solve this in O(2^(num_elements/2)) allowing to go easily to 30 or 40 elements. If bin_size is small, complexity is more like O(num_element * bin_size).
Get rid of a few easy to decide corner cases.
We split the elements in two equal-sized parts.
For all possible sum a, we compute the largest sum b that fits. We do that in linear time thanks to the sorted partial sums.
1.13.2