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.
|
Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 4.0 License, and code samples are licensed under the Apache 2.0 License. For details, see the Google Developers Site Policies. Java is a registered trademark of Oracle and/or its affiliates.
Last updated 2024-08-06 UTC.
[null,null,["Last updated 2024-08-06 UTC."],[],["The `MaxBoundedSubsetSum` class in C++ uses dynamic programming to find the maximum reachable subset sum within a specified bound. It allows adding values via the `Add` method to a base set. `Reset` clears the set and sets a new bound. `CurrentMax` returns the upper bound on the maximum sum, potentially the set bound. The computation is aborted if it becomes too costly. All values added and the bound must be non-negative.\n"]]
