operations_research::sat::MaxBoundedSubsetSum Class Reference

#include <util.h>

Public Member Functions
	MaxBoundedSubsetSum ()
	MaxBoundedSubsetSum (int64_t bound, int max_complexity_per_add=50)
void	Reset (int64_t bound)
int64_t	MaxIfAdded (int64_t candidate) const
	Returns the updated max if value was added to the subset-sum.
void	Add (int64_t value)
	Add a value to the base set for which subset sums will be taken.
void	AddChoices (absl::Span< const int64_t > choices)
void	AddMultiples (int64_t coeff, int64_t max_value)
	Adds [0, coeff, 2 * coeff, ... max_value * coeff].
int64_t	CurrentMax () const
int64_t	Bound () const

Detailed Description

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.

Definition at line 376 of file util.h.

Constructor & Destructor Documentation

MaxBoundedSubsetSum() [1/2]

operations_research::sat::MaxBoundedSubsetSum::MaxBoundedSubsetSum ( )

inline

Definition at line 378 of file util.h.

MaxBoundedSubsetSum() [2/2]

operations_research::sat::MaxBoundedSubsetSum::MaxBoundedSubsetSum ( int64_t bound, int max_complexity_per_add = 50 )

inlineexplicit

Definition at line 379 of file util.h.

Member Function Documentation

Add()

void operations_research::sat::MaxBoundedSubsetSum::Add

(

int64_t

value

)

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

Definition at line 501 of file util.cc.

AddChoices()

void operations_research::sat::MaxBoundedSubsetSum::AddChoices

(

absl::Span< const int64_t >

choices

)

Add a choice of values to the base set for which subset sums will be taken.

Note

even if this doesn't include zero, not taking any choices will also be an option.

The max is already reachable or we aborted.

Filter out zero and values greater than bound_.

So we can abort early in the AddChoicesInternal() inner loops.

Definition at line 508 of file util.cc.

AddMultiples()

void operations_research::sat::MaxBoundedSubsetSum::AddMultiples	(	int64_t	coeff,
		int64_t	max_value )

Adds [0, coeff, 2 * coeff, ... max_value * coeff].

We only keep GCD in this case.

Definition at line 532 of file util.cc.

Bound()

int64_t operations_research::sat::MaxBoundedSubsetSum::Bound ( ) const

inline

Definition at line 406 of file util.h.

CurrentMax()

int64_t operations_research::sat::MaxBoundedSubsetSum::CurrentMax ( ) const

inline

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

Definition at line 404 of file util.h.

MaxIfAdded()

int64_t operations_research::sat::MaxBoundedSubsetSum::MaxIfAdded

(

int64_t

candidate

)

const

Returns the updated max if value was added to the subset-sum.

Mode 1: vector of all possible sums (with duplicates).

Mode 2: bitset of all possible sums.

Definition at line 614 of file util.cc.

Reset()

void operations_research::sat::MaxBoundedSubsetSum::Reset

(

int64_t

bound

)

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

Definition at line 492 of file util.cc.

---

The documentation for this class was generated from the following files:

• ortools/sat/util.h
• ortools/sat/util.cc