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."],[[["\u003cp\u003eThe \u003ccode\u003eMaxBoundedSubsetSum\u003c/code\u003e class uses dynamic programming to calculate the maximum achievable subset sum within a specified bound.\u003c/p\u003e\n"],["\u003cp\u003eIt requires all input values and the bound to be non-negative.\u003c/p\u003e\n"],["\u003cp\u003eThe computation may be aborted if it becomes too large, and in such cases, the returned upper bound might be equal to the initial bound.\u003c/p\u003e\n"],["\u003cp\u003eThe class provides methods to add values to the set, reset the computation with a new bound, and retrieve the current maximum sum.\u003c/p\u003e\n"]]],["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"],null,["# MaxBoundedSubsetSum\n\nC++ Reference: class MaxBoundedSubsetSum\n========================================\n\n\nNote: This documentation is automatically generated.\nSimple 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. \n\nPrecondition: Both bound and all added values must be \\\u003e= 0. \n\nTODO(user): Compute gcd of all value so we can return a better bound for large sets?\n\n| Method ||\n|-----------------------------------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------------------------------------------------|\n| [`Add`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/util.h#L206) | Return type: `void ` Arguments: `int64_t value` Add a value to the base set for which subset sums will be taken. |\n| [`Bound`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/util.h#L212) | Return type: `int64_t ` \u003cbr /\u003e |\n| [`CurrentMax`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/util.h#L210) | Return type: `int64_t ` Returns an upper bound (inclusive) on the maximum sum \\\u003c= bound_. This might return bound_ if we aborted the computation. |\n| [`MaxBoundedSubsetSum`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/util.h#L198) | \u003cbr /\u003e |\n| [`MaxBoundedSubsetSum`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/util.h#L199) | Return type: `explicit ` Arguments: `int64_t bound` \u003cbr /\u003e |\n| [`Reset`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/util.h#L203) | Return type: `void ` Arguments: `int64_t bound` Resets to an empty set of values. We look for the maximum sum \\\u003c= bound. |"]]
