C++ Reference
C++ Reference: Algorithms
Detailed Description
This library solves knapsack problems.
Problems the library solves include:
- 0-1 knapsack problems,
- Multi-dimensional knapsack problems,
Given n items, each with a profit and a weight, given a knapsack of capacity c, the goal is to find a subset of items which fits inside c and maximizes the total profit. The knapsack problem can easily be extended from 1 to d dimensions. As an example, this can be useful to constrain the maximum number of items inside the knapsack. Without loss of generality, profits and weights are assumed to be positive.
From a mathematical point of view, the multi-dimensional knapsack problem can be modeled by d linear constraints:
ForEach(j:1..d)(Sum(i:1..n)(weight_ij * item_i) <= c_j where item_i is a 0-1 integer variable.
Then the goal is to maximize:
Sum(i:1..n)(profit_i * item_i).
There are several ways to solve knapsack problems. One of the most efficient is based on dynamic programming (mainly when weights, profits and dimensions are small, and the algorithm runs in pseudo polynomial time). Unfortunately, when adding conflict constraints the problem becomes strongly NP-hard, i.e. there is no pseudo-polynomial algorithm to solve it. That's the reason why the most of the following code is based on branch and bound search.
For instance to solve a 2-dimensional knapsack problem with 9 items, one just has to feed a profit vector with the 9 profits, a vector of 2 vectors for weights, and a vector of capacities. E.g.:
Python:
C++:
Java:
Definition at line 117 of file knapsack_solver.h.
Public Types | |
enum | SolverType { KNAPSACK_BRUTE_FORCE_SOLVER = 0 , KNAPSACK_64ITEMS_SOLVER = 1 , KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER = 2 , KNAPSACK_MULTIDIMENSION_CBC_MIP_SOLVER = 3 , KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER = 5 , KNAPSACK_MULTIDIMENSION_SCIP_MIP_SOLVER = 6 } |
Enum controlling which underlying algorithm is used. More... | |
Public Member Functions | |
KnapsackSolver (const std::string &solver_name) | |
KnapsackSolver (SolverType solver_type, const std::string &solver_name) | |
virtual | ~KnapsackSolver () |
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. More... | |
int64 | Solve () |
Solves the problem and returns the profit of the optimal solution. More... | |
bool | BestSolutionContains (int item_id) const |
Returns true if the item 'item_id' is packed in the optimal knapsack. More... | |
bool | IsSolutionOptimal () const |
Returns true if the solution was proven optimal. More... | |
std::string | GetName () const |
bool | use_reduction () const |
void | set_use_reduction (bool use_reduction) |
void | set_time_limit (double time_limit_seconds) |
Time limit in seconds. More... | |
Member Enumeration Documentation
◆ SolverType
enum SolverType |
Enum controlling which underlying algorithm is used.
This enum is passed to the constructor of the KnapsackSolver object. It selects which solving method will be used.
Definition at line 124 of file knapsack_solver.h.
Constructor & Destructor Documentation
◆ KnapsackSolver() [1/2]
|
explicit |
◆ KnapsackSolver() [2/2]
KnapsackSolver | ( | SolverType | solver_type, |
const std::string & | solver_name | ||
) |
◆ ~KnapsackSolver()
|
virtual |
Member Function Documentation
◆ BestSolutionContains()
bool BestSolutionContains | ( | int | item_id | ) | const |
Returns true if the item 'item_id' is packed in the optimal knapsack.
◆ GetName()
std::string GetName | ( | ) | const |
◆ Init()
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.
◆ IsSolutionOptimal()
|
inline |
Returns true if the solution was proven optimal.
Definition at line 216 of file knapsack_solver.h.
◆ set_time_limit()
|
inline |
Time limit in seconds.
When a finite time limit is set the solution obtained might not be optimal if the limit is reached.
Definition at line 227 of file knapsack_solver.h.
◆ set_use_reduction()
|
inline |
Definition at line 220 of file knapsack_solver.h.
◆ Solve()
int64 Solve | ( | ) |
Solves the problem and returns the profit of the optimal solution.
◆ use_reduction()
|
inline |
Definition at line 219 of file knapsack_solver.h.
The documentation for this class was generated from the following file: