operations_research::KnapsackBruteForceSolver Class Reference

Inheritance diagram for operations_research::KnapsackBruteForceSolver:

Public Member Functions
	KnapsackBruteForceSolver (absl::string_view solver_name)
	KnapsackBruteForceSolver (const KnapsackBruteForceSolver &)=delete
	This type is neither copyable nor movable.
KnapsackBruteForceSolver &	operator= (const KnapsackBruteForceSolver &)=delete
void	Init (const std::vector< int64_t > &profits, const std::vector< std::vector< int64_t > > &weights, const std::vector< int64_t > &capacities) override
	Initializes the solver and enters the problem to be solved.
int64_t	Solve (TimeLimit *time_limit, double time_limit_in_second, bool *is_solution_optimal) override
	Solves the problem and returns the profit of the optimal solution.
bool	best_solution (int item_id) const override
	Returns true if the item 'item_id' is packed in the optimal knapsack.
Public Member Functions inherited from operations_research::BaseKnapsackSolver
	BaseKnapsackSolver (absl::string_view solver_name)
virtual	~BaseKnapsackSolver ()=default
virtual void	GetLowerAndUpperBoundWhenItem (int item_id, bool is_item_in, int64_t *lower_bound, int64_t *upper_bound)
	--— BaseKnapsackSolver --—
virtual std::string	GetName () const

Detailed Description

--— KnapsackBruteForceSolver --— KnapsackBruteForceSolver solves the 0-1 knapsack problem when the number of items is less or equal to 30 with brute force, ie. explores all states. Experiments show better results than KnapsackGenericSolver when the number of items is less than 15.

Definition at line 554 of file knapsack_solver.cc.

Constructor & Destructor Documentation

KnapsackBruteForceSolver() [1/2]

operations_research::KnapsackBruteForceSolver::KnapsackBruteForceSolver ( absl::string_view solver_name )

explicit

Definition at line 584 of file knapsack_solver.cc.

KnapsackBruteForceSolver() [2/2]

operations_research::KnapsackBruteForceSolver::KnapsackBruteForceSolver ( const KnapsackBruteForceSolver & )

delete

This type is neither copyable nor movable.

Member Function Documentation

best_solution()

bool operations_research::KnapsackBruteForceSolver::best_solution ( int item_id ) const

inlineoverridevirtual

Returns true if the item 'item_id' is packed in the optimal knapsack.

Implements operations_research::BaseKnapsackSolver.

Definition at line 572 of file knapsack_solver.cc.

Init()

void operations_research::KnapsackBruteForceSolver::Init ( const std::vector< int64_t > & profits, const std::vector< std::vector< int64_t > > & weights, const std::vector< int64_t > & capacities )

overridevirtual

Initializes the solver and enters the problem to be solved.

Todo

(user): Implement multi-dimensional brute force solver.

Implements operations_research::BaseKnapsackSolver.

Definition at line 592 of file knapsack_solver.cc.

operator=()

KnapsackBruteForceSolver & operations_research::KnapsackBruteForceSolver::operator= ( const KnapsackBruteForceSolver & )

delete

Solve()

int64_t operations_research::KnapsackBruteForceSolver::Solve ( TimeLimit * time_limit, double time_limit_in_second, bool * is_solution_optimal )

overridevirtual

Solves the problem and returns the profit of the optimal solution.

This loop starts at 1, because state = 0 was already considered previously, ie. when no items are in, sum_profit = 0.

Implements operations_research::BaseKnapsackSolver.

Definition at line 615 of file knapsack_solver.cc.

---

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

• ortools/algorithms/knapsack_solver.cc