operations_research::KnapsackDivideAndConquerSolver Class Reference

Inheritance diagram for operations_research::KnapsackDivideAndConquerSolver:

Public Member Functions
	KnapsackDivideAndConquerSolver (absl::string_view solver_name)
	--— KnapsackDivideAndConquerSolver --—
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

--— KnapsackDivideAndConquerSolver --— KnapsackDivideAndConquerSolver solves the 0-1 knapsack problem (KP) using divide and conquer and dynamic programming. By using one-dimensional vectors it keeps a complexity of O(capacity * number_of_items) in time, but reduces the space complexity to O(capacity + number_of_items) and is therefore suitable for large hard to solve (KP)/(SSP). The implemented algorithm is based on 'DP-2' and Divide and Conquer for storage reduction from [Hans Kellerer et al., "Knapsack problems" (DOI 10.1007/978-3-540-24777-7)].

Definition at line 1055 of file knapsack_solver.cc.

Constructor & Destructor Documentation

KnapsackDivideAndConquerSolver()

operations_research::KnapsackDivideAndConquerSolver::KnapsackDivideAndConquerSolver ( absl::string_view solver_name )

explicit

--— KnapsackDivideAndConquerSolver --—

Definition at line 1090 of file knapsack_solver.cc.

Member Function Documentation

best_solution()

bool operations_research::KnapsackDivideAndConquerSolver::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 1069 of file knapsack_solver.cc.

Init()

void operations_research::KnapsackDivideAndConquerSolver::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.

Implements operations_research::BaseKnapsackSolver.

Definition at line 1100 of file knapsack_solver.cc.

Solve()

int64_t operations_research::KnapsackDivideAndConquerSolver::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.

Implements operations_research::BaseKnapsackSolver.

Definition at line 1171 of file knapsack_solver.cc.

---

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

• ortools/algorithms/knapsack_solver.cc