operations_research::KnapsackDynamicProgrammingSolver Class Reference

KnapsackDynamicProgrammingSolver KnapsackDynamicProgrammingSolver solves the 0-1 knapsack problem using dynamic programming. More...

Inheritance diagram for operations_research::KnapsackDynamicProgrammingSolver:

List of all members.

Public Member Functions
	KnapsackDynamicProgrammingSolver (const string &solver_name)
	KnapsackDynamicProgrammingSolver.
void	Init (const std::vector< int64 > &profits, const std::vector< std::vector< int64 > > &weights, const std::vector< int64 > &capacities)
	Initializes the solver and enters the problem to be solved.
int64	Solve ()
	Solves the problem and returns the profit of the optimal solution.
bool	best_solution (int item_id) const
	Returns true if the item 'item_id' is packed in the optimal knapsack.

---

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

operations_research::KnapsackDynamicProgrammingSolver::KnapsackDynamicProgrammingSolver

(

const string &

solver_name

)

[explicit]

KnapsackDynamicProgrammingSolver.

Definition at line 976 of file knapsack_solver.cc.

---

Member Function Documentation

void operations_research::KnapsackDynamicProgrammingSolver::Init	(	const std::vector< int64 > &	profits,
		const std::vector< std::vector< int64 > > &	weights,
		const std::vector< int64 > &	capacities
	)			[virtual]

Initializes the solver and enters the problem to be solved.

Implements operations_research::BaseKnapsackSolver.

Definition at line 986 of file knapsack_solver.cc.

int64 operations_research::KnapsackDynamicProgrammingSolver::Solve

(

)

[virtual]

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

Implements operations_research::BaseKnapsackSolver.

Definition at line 1022 of file knapsack_solver.cc.

bool operations_research::KnapsackDynamicProgrammingSolver::best_solution

(

int

item_id

)

const [inline, virtual]

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

Implements operations_research::BaseKnapsackSolver.

Definition at line 960 of file knapsack_solver.cc.

---

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

• or-tools/src/algorithms/knapsack_solver.cc