C++ Reference
C++ Reference: Algorithms
knapsack_solver.h
Go to the documentation of this file.
virtual int64 Solve(TimeLimit *time_limit, bool *is_solution_optimal)=0
virtual ~BaseKnapsackSolver()
Definition: knapsack_solver.h:570
BaseKnapsackSolver(const std::string &solver_name)
Definition: knapsack_solver.h:568
virtual void Init(const std::vector< int64 > &profits, const std::vector< std::vector< int64 > > &weights, const std::vector< int64 > &capacities)=0
virtual std::string GetName() const
Definition: knapsack_solver.h:590
virtual void GetLowerAndUpperBoundWhenItem(int item_id, bool is_item_in, int64 *lower_bound, int64 *upper_bound)
virtual bool best_solution(int item_id) const =0
KnapsackCapacityPropagator(const KnapsackState &state, int64 capacity)
bool UpdatePropagator(bool revert, const KnapsackAssignment &assignment) override
void CopyCurrentStateToSolutionPropagator(std::vector< bool > *solution) const override
void ComputeProfitBounds() override
~KnapsackCapacityPropagator() override
void InitPropagator() override
int GetNextItemId() const override
Definition: knapsack_solver.h:531
~KnapsackGenericSolver() override
KnapsackGenericSolver(const std::string &solver_name)
void GetLowerAndUpperBoundWhenItem(int item_id, bool is_item_in, int64 *lower_bound, int64 *upper_bound) override
void set_master_propagator_id(int master_propagator_id)
Definition: knapsack_solver.h:622
void Init(const std::vector< int64 > &profits, const std::vector< std::vector< int64 > > &weights, const std::vector< int64 > &capacities) override
int GetNumberOfItems() const
Definition: knapsack_solver.h:614
bool best_solution(int item_id) const override
Definition: knapsack_solver.h:629
int64 Solve(TimeLimit *time_limit, bool *is_solution_optimal) override
int64 profit_lower_bound() const
Definition: knapsack_solver.h:460
void CopyCurrentStateToSolution(bool has_one_propagator, std::vector< bool > *solution) const
virtual bool UpdatePropagator(bool revert, const KnapsackAssignment &assignment)=0
void set_profit_lower_bound(int64 profit)
Definition: knapsack_solver.h:493
virtual void InitPropagator()=0
virtual void ComputeProfitBounds()=0
virtual int GetNextItemId() const =0
const KnapsackState & state() const
Definition: knapsack_solver.h:490
void Init(const std::vector< int64 > &profits, const std::vector< int64 > &weights)
const std::vector< KnapsackItemPtr > & items() const
Definition: knapsack_solver.h:491
void set_profit_upper_bound(int64 profit)
Definition: knapsack_solver.h:494
virtual void CopyCurrentStateToSolutionPropagator(std::vector< bool > *solution) const =0
virtual ~KnapsackPropagator()
int64 profit_upper_bound() const
Definition: knapsack_solver.h:461
KnapsackPropagator(const KnapsackState &state)
int64 current_profit() const
Definition: knapsack_solver.h:459
bool Update(bool revert, const KnapsackAssignment &assignment)
void set_current_profit(int64 profit)
Definition: knapsack_solver.h:340
int next_item_id() const
Definition: knapsack_solver.h:345
void set_next_item_id(int id)
Definition: knapsack_solver.h:346
void set_profit_upper_bound(int64 profit)
Definition: knapsack_solver.h:343
KnapsackSearchNode(const KnapsackSearchNode *const parent, const KnapsackAssignment &assignment)
int64 profit_upper_bound() const
Definition: knapsack_solver.h:342
int64 current_profit() const
Definition: knapsack_solver.h:339
const KnapsackAssignment & assignment() const
Definition: knapsack_solver.h:337
const KnapsackSearchNode *const parent() const
Definition: knapsack_solver.h:336
const KnapsackSearchNode & via() const
Definition: knapsack_solver.h:391
KnapsackSearchPath(const KnapsackSearchNode &from, const KnapsackSearchNode &to)
const KnapsackSearchNode * MoveUpToDepth(const KnapsackSearchNode &node, int depth) const
const KnapsackSearchNode & from() const
Definition: knapsack_solver.h:390
const KnapsackSearchNode & to() const
Definition: knapsack_solver.h:392
This library solves knapsack problems.
Definition: knapsack_solver.h:117
KnapsackSolver(SolverType solver_type, const std::string &solver_name)
bool BestSolutionContains(int item_id) const
Returns true if the item 'item_id' is packed in the optimal knapsack.
int64 Solve()
Solves the problem and returns the profit of the optimal solution.
KnapsackSolver(const std::string &solver_name)
void set_time_limit(double time_limit_seconds)
Time limit in seconds.
Definition: knapsack_solver.h:227
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.
@ KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER
Dynamic Programming approach for single dimension problems.
Definition: knapsack_solver.h:147
@ KNAPSACK_64ITEMS_SOLVER
Optimized method for single dimension small problems.
Definition: knapsack_solver.h:139
bool IsSolutionOptimal() const
Returns true if the solution was proven optimal.
Definition: knapsack_solver.h:216
std::string GetName() const
void set_use_reduction(bool use_reduction)
Definition: knapsack_solver.h:220
bool use_reduction() const
Definition: knapsack_solver.h:219
virtual ~KnapsackSolver()
KnapsackState()
int GetNumberOfItems() const
Definition: knapsack_solver.h:417
void Init(int number_of_items)
bool is_bound(int id) const
Definition: knapsack_solver.h:418
bool UpdateState(bool revert, const KnapsackAssignment &assignment)
Definition: dense_doubly_linked_list.h:21
KnapsackAssignment(int _item_id, bool _is_in)
Definition: knapsack_solver.h:288
double GetEfficiency(int64 profit_max) const
Definition: knapsack_solver.h:309
KnapsackItem(int _id, int64 _weight, int64 _profit)
Definition: knapsack_solver.h:307