Stay organized with collections Save and categorize content based on your preferences.

C++ Reference: class MaxBoundedSubsetSum

Note: This documentation is automatically generated.

Simple DP to compute the maximum reachable value of a "subset sum" under a given bound (inclusive). Note that we abort as soon as the computation become too important.

Precondition: Both bound and all added values must be >= 0.

TODO(user): Compute gcd of all value so we can return a better bound for large sets?
Method
Add

Return type: void

Arguments: int64_t value

Add a value to the base set for which subset sums will be taken.

Bound

Return type: int64_t

CurrentMax

Return type: int64_t

Returns an upper bound (inclusive) on the maximum sum <= bound_. This might return bound_ if we aborted the computation.

MaxBoundedSubsetSum

MaxBoundedSubsetSum

Return type: explicit

Arguments: int64_t bound

Reset

Return type: void

Arguments: int64_t bound

Resets to an empty set of values. We look for the maximum sum <= bound.