C++ Reference
C++ Reference: Algorithms
knapsack_solver.h
void CopyCurrentStateToSolutionPropagator(std::vector< bool > *solution) const override
const KnapsackAssignment & assignment() const
Definition: knapsack_solver.h:340
int GetNumberOfItems() const
Definition: knapsack_solver.h:420
const KnapsackSearchNode & from() const
Definition: knapsack_solver.h:393
virtual bool best_solution(int item_id) const =0
KnapsackCapacityPropagator(const KnapsackState &state, int64 capacity)
const KnapsackState & state() const
Definition: knapsack_solver.h:493
virtual ~KnapsackPropagator()
@ KNAPSACK_64ITEMS_SOLVER
Optimized method for single dimension small problems.
Definition: knapsack_solver.h:142
void set_profit_upper_bound(int64 profit)
Definition: knapsack_solver.h:497
virtual void GetLowerAndUpperBoundWhenItem(int item_id, bool is_item_in, int64 *lower_bound, int64 *upper_bound)
void set_profit_lower_bound(int64 profit)
Definition: knapsack_solver.h:496
int next_item_id() const
Definition: knapsack_solver.h:348
void set_next_item_id(int id)
Definition: knapsack_solver.h:349
virtual void Init(const std::vector< int64 > &profits, const std::vector< std::vector< int64 > > &weights, const std::vector< int64 > &capacities)=0
KnapsackAssignment(int _item_id, bool _is_in)
Definition: knapsack_solver.h:291
bool use_reduction() const
Definition: knapsack_solver.h:222
virtual void InitPropagator()=0
virtual int GetNextItemId() const =0
int GetNumberOfItems() const
Definition: knapsack_solver.h:617
Definition: dense_doubly_linked_list.h:21
KnapsackState()
void Init(int number_of_items)
bool IsSolutionOptimal() const
Returns true if the solution was proven optimal.
Definition: knapsack_solver.h:219
void GetLowerAndUpperBoundWhenItem(int item_id, bool is_item_in, int64 *lower_bound, int64 *upper_bound) override
double GetEfficiency(int64 profit_max) const
Definition: knapsack_solver.h:312
void set_master_propagator_id(int master_propagator_id)
Definition: knapsack_solver.h:625
~KnapsackGenericSolver() override
KnapsackPropagator(const KnapsackState &state)
void set_profit_upper_bound(int64 profit)
Definition: knapsack_solver.h:346
bool is_bound(int id) const
Definition: knapsack_solver.h:421
const KnapsackSearchNode & via() const
Definition: knapsack_solver.h:394
int64 current_profit() const
Definition: knapsack_solver.h:462
int GetNextItemId() const override
Definition: knapsack_solver.h:534
int64 profit_lower_bound() const
Definition: knapsack_solver.h:463
@ KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER
Dynamic Programming approach for single dimension problems.
Definition: knapsack_solver.h:150
bool UpdateState(bool revert, const KnapsackAssignment &assignment)
virtual ~KnapsackSolver()
void Init(const std::vector< int64 > &profits, const std::vector< int64 > &weights)
void set_current_profit(int64 profit)
Definition: knapsack_solver.h:343
bool Update(bool revert, const KnapsackAssignment &assignment)
virtual std::string GetName() const
Definition: knapsack_solver.h:593
void CopyCurrentStateToSolution(bool has_one_propagator, std::vector< bool > *solution) const
virtual ~BaseKnapsackSolver()
Definition: knapsack_solver.h:573
bool best_solution(int item_id) const override
Definition: knapsack_solver.h:632
KnapsackItem(int _id, int64 _weight, int64 _profit)
Definition: knapsack_solver.h:310
int64 current_profit() const
Definition: knapsack_solver.h:342
bool BestSolutionContains(int item_id) const
Returns true if the item 'item_id' is packed in the optimal knapsack.
virtual bool UpdatePropagator(bool revert, const KnapsackAssignment &assignment)=0
const std::vector< KnapsackItemPtr > & items() const
Definition: knapsack_solver.h:494
This library solves knapsack problems.
Definition: knapsack_solver.h:120
void set_use_reduction(bool use_reduction)
Definition: knapsack_solver.h:223
bool UpdatePropagator(bool revert, const KnapsackAssignment &assignment) override
BaseKnapsackSolver(const std::string &solver_name)
Definition: knapsack_solver.h:571
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.
const KnapsackSearchNode & to() const
Definition: knapsack_solver.h:395
int64 Solve(TimeLimit *time_limit, bool *is_solution_optimal) override
KnapsackSearchPath(const KnapsackSearchNode &from, const KnapsackSearchNode &to)
KnapsackGenericSolver(const std::string &solver_name)
virtual void CopyCurrentStateToSolutionPropagator(std::vector< bool > *solution) const =0
KnapsackSearchNode(const KnapsackSearchNode *const parent, const KnapsackAssignment &assignment)
void set_time_limit(double time_limit_seconds)
Time limit in seconds.
Definition: knapsack_solver.h:230
virtual void ComputeProfitBounds()=0
int64 profit_upper_bound() const
Definition: knapsack_solver.h:345
int64 profit_upper_bound() const
Definition: knapsack_solver.h:464
void InitPropagator() override
void Init(const std::vector< int64 > &profits, const std::vector< std::vector< int64 > > &weights, const std::vector< int64 > &capacities) override
int64 Solve()
Solves the problem and returns the profit of the optimal solution.
KnapsackSolver(SolverType solver_type, const std::string &solver_name)
const KnapsackSearchNode *const parent() const
Definition: knapsack_solver.h:339
~KnapsackCapacityPropagator() override
void ComputeProfitBounds() override
std::string GetName() const
virtual int64 Solve(TimeLimit *time_limit, bool *is_solution_optimal)=0
KnapsackSolver(const std::string &solver_name)
const KnapsackSearchNode * MoveUpToDepth(const KnapsackSearchNode &node, int depth) const