operations_research::sat::FirstFewValues< n > Class Template Reference

#include <util.h>

Public Member Functions
	FirstFewValues ()
void	Reset ()
void	Add (const int64_t positive_value)
bool	MightBeReachable (int64_t sum) const
const std::array< int64_t, n > &	reachable () const
int64_t	LastValue () const

Detailed Description

template<int n>
class operations_research::sat::FirstFewValues< n >

Simple DP to keep the set of the first n reachable value (n > 1).

Todo

(user): Maybe modulo some prime number we can keep more info.

(user): Another common case is a bunch of really small values and larger ones, so we could bound the sum of the small values and keep the first few reachable by the big ones. This is similar to some presolve transformations.

Definition at line 429 of file util.h.

Constructor & Destructor Documentation

FirstFewValues()

template<int n>

operations_research::sat::FirstFewValues< n >::FirstFewValues ( )

inline

Definition at line 431 of file util.h.

Member Function Documentation

Add()

template<int n>

void operations_research::sat::FirstFewValues< n >::Add ( const int64_t positive_value )

inline

We assume the given positive value can be added as many time as wanted.

Todo

(user): Implement Add() with an upper bound on the multiplicity.

We copy from reachable_[i] to new_reachable_[j]. The position zero is already copied.

Eliminate duplicates.

insert candidate in its final place.

Definition at line 442 of file util.h.

LastValue()

template<int n>

int64_t operations_research::sat::FirstFewValues< n >::LastValue ( ) const

inline

Definition at line 474 of file util.h.

MightBeReachable()

template<int n>

bool operations_research::sat::FirstFewValues< n >::MightBeReachable ( int64_t sum ) const

inline

Returns true iff sum might be expressible as a weighted sum of the added value. Any sum >= LastValue() is always considered potentially reachable.

Definition at line 468 of file util.h.

reachable()

template<int n>

const std::array< int64_t, n > & operations_research::sat::FirstFewValues< n >::reachable ( ) const

inline

Definition at line 473 of file util.h.

Reset()

template<int n>

void operations_research::sat::FirstFewValues< n >::Reset ( )

inline

Definition at line 433 of file util.h.

---

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

• ortools/sat/util.h