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?
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["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. |"]]
