operations_research::KnapsackDynamicProgrammingSolver Class Reference

Inheritance diagram for operations_research::KnapsackDynamicProgrammingSolver:

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

--— KnapsackDynamicProgrammingSolver --— KnapsackDynamicProgrammingSolver solves the 0-1 knapsack problem using dynamic programming. This algorithm is pseudo-polynomial because it depends on capacity, ie. the time and space complexity is O(capacity * number_of_items). The implemented algorithm is 'DP-3' in "Knapsack problems", Hans Kellerer, Ulrich Pferschy and David Pisinger, Springer book (ISBN 978-3540402862).

Definition at line 947 of file knapsack_solver.cc.

Constructor & Destructor Documentation

KnapsackDynamicProgrammingSolver()

operations_research::KnapsackDynamicProgrammingSolver::KnapsackDynamicProgrammingSolver ( absl::string_view solver_name )

explicit

--— KnapsackDynamicProgrammingSolver --—

Definition at line 977 of file knapsack_solver.cc.

Member Function Documentation

best_solution()

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

Init()

void operations_research::KnapsackDynamicProgrammingSolver::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 987 of file knapsack_solver.cc.

Solve()

int64_t operations_research::KnapsackDynamicProgrammingSolver::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 1022 of file knapsack_solver.cc.

---

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

• ortools/algorithms/knapsack_solver.cc