OR-Tools  8.2
knapsack_solver.h
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 #ifndef OR_TOOLS_ALGORITHMS_KNAPSACK_SOLVER_H_
15 #define OR_TOOLS_ALGORITHMS_KNAPSACK_SOLVER_H_
16 
17 #include <math.h>
18 
19 #include <memory>
20 #include <string>
21 #include <vector>
22 
23 #include "absl/memory/memory.h"
26 #include "ortools/base/logging.h"
27 #include "ortools/base/macros.h"
29 
30 namespace operations_research {
31 
32 class BaseKnapsackSolver;
33 
118  public:
124  enum SolverType {
132 
140 
148 
149 #if defined(USE_CBC)
156 #endif // USE_CBC
157 
164 
165 #if defined(USE_SCIP)
172 #endif // USE_SCIP
173 
174 #if defined(USE_XPRESS)
180  KNAPSACK_MULTIDIMENSION_XPRESS_MIP_SOLVER = 7,
181 #endif
182 
183 #if defined(USE_CPLEX)
189  KNAPSACK_MULTIDIMENSION_CPLEX_MIP_SOLVER = 8,
190 #endif
191  };
192 
193  explicit KnapsackSolver(const std::string& solver_name);
194  KnapsackSolver(SolverType solver_type, const std::string& solver_name);
195  virtual ~KnapsackSolver();
196 
200  void Init(const std::vector<int64>& profits,
201  const std::vector<std::vector<int64> >& weights,
202  const std::vector<int64>& capacities);
203 
207  int64 Solve();
208 
212  bool BestSolutionContains(int item_id) const;
216  bool IsSolutionOptimal() const { return is_solution_optimal_; }
217  std::string GetName() const;
218 
219  bool use_reduction() const { return use_reduction_; }
220  void set_use_reduction(bool use_reduction) { use_reduction_ = use_reduction; }
221 
227  void set_time_limit(double time_limit_seconds) {
228  time_limit_seconds_ = time_limit_seconds;
229  time_limit_ = absl::make_unique<TimeLimit>(time_limit_seconds_);
230  }
231 
232  private:
233  // Trivial reduction of capacity constraints when the capacity is higher than
234  // the sum of the weights of the items. Returns the number of reduced items.
235  int ReduceCapacities(int num_items,
236  const std::vector<std::vector<int64> >& weights,
237  const std::vector<int64>& capacities,
238  std::vector<std::vector<int64> >* reduced_weights,
239  std::vector<int64>* reduced_capacities);
240  int ReduceProblem(int num_items);
241  void ComputeAdditionalProfit(const std::vector<int64>& profits);
242  void InitReducedProblem(const std::vector<int64>& profits,
243  const std::vector<std::vector<int64> >& weights,
244  const std::vector<int64>& capacities);
245 
246  std::unique_ptr<BaseKnapsackSolver> solver_;
247  std::vector<bool> known_value_;
248  std::vector<bool> best_solution_;
249  bool is_solution_optimal_ = false;
250  std::vector<int> mapping_reduced_item_id_;
251  bool is_problem_solved_;
252  int64 additional_profit_;
253  bool use_reduction_;
254  double time_limit_seconds_;
255  std::unique_ptr<TimeLimit> time_limit_;
256 
257  DISALLOW_COPY_AND_ASSIGN(KnapsackSolver);
258 };
259 
260 #if !defined(SWIG)
261 // The following code defines needed classes for the KnapsackGenericSolver
262 // class which is the entry point to extend knapsack with new constraints such
263 // as conflicts between items.
264 //
265 // Constraints are enforced using KnapsackPropagator objects, in the current
266 // code there is one propagator per dimension (KnapsackCapacityPropagator).
267 // One of those propagators, named master propagator, is used to guide the
268 // search, i.e. decides which item should be assigned next.
269 // Roughly speaking the search algorithm is:
270 // - While not optimal
271 // - Select next search node to expand
272 // - Select next item_i to assign (using master propagator)
273 // - Generate a new search node where item_i is in the knapsack
274 // - Check validity of this new partial solution (using propagators)
275 // - If valid, add this new search node to the search
276 // - Generate a new search node where item_i is not in the knapsack
277 // - Check validity of this new partial solution (using propagators)
278 // - If valid, add this new search node to the search
279 //
280 // TODO(user): Add a new propagator class for conflict constraint.
281 // TODO(user): Add a new propagator class used as a guide when the problem has
282 // several dimensions.
283 
284 // ----- KnapsackAssignement -----
285 // KnapsackAssignement is a small struct used to pair an item with its
286 // assignment. It is mainly used for search nodes and updates.
288  KnapsackAssignment(int _item_id, bool _is_in)
289  : item_id(_item_id), is_in(_is_in) {}
290  int item_id;
291  bool is_in;
292 };
293 
294 // ----- KnapsackItem -----
295 // KnapsackItem is a small struct to pair an item weight with its
296 // corresponding profit.
297 // The aim of the knapsack problem is to pack as many valuable items as
298 // possible. A straight forward heuristic is to take those with the greatest
299 // profit-per-unit-weight. This ratio is called efficiency in this
300 // implementation. So items will be grouped in vectors, and sorted by
301 // decreasing efficiency.
302 // Note that profits are duplicated for each dimension. This is done to
303 // simplify the code, especially the GetEfficiency method and vector sorting.
304 // As there usually are only few dimensions, the overhead should not be an
305 // issue.
306 struct KnapsackItem {
307  KnapsackItem(int _id, int64 _weight, int64 _profit)
308  : id(_id), weight(_weight), profit(_profit) {}
310  return (weight > 0)
311  ? static_cast<double>(profit) / static_cast<double>(weight)
312  : static_cast<double>(profit_max);
313  }
314 
315  // The 'id' field is used to retrieve the initial item in order to
316  // communicate with other propagators and state.
317  const int id;
318  const int64 weight;
319  const int64 profit;
320 };
322 
323 // ----- KnapsackSearchNode -----
324 // KnapsackSearchNode is a class used to describe a decision in the decision
325 // search tree.
326 // The node is defined by a pointer to the parent search node and an
327 // assignment (see KnapsackAssignement).
328 // As the current state is not explicitly stored in a search node, one should
329 // go through the search tree to incrementally build a partial solution from
330 // a previous search node.
332  public:
335  int depth() const { return depth_; }
336  const KnapsackSearchNode* const parent() const { return parent_; }
337  const KnapsackAssignment& assignment() const { return assignment_; }
338 
339  int64 current_profit() const { return current_profit_; }
340  void set_current_profit(int64 profit) { current_profit_ = profit; }
341 
342  int64 profit_upper_bound() const { return profit_upper_bound_; }
343  void set_profit_upper_bound(int64 profit) { profit_upper_bound_ = profit; }
344 
345  int next_item_id() const { return next_item_id_; }
346  void set_next_item_id(int id) { next_item_id_ = id; }
347 
348  private:
349  // 'depth' field is used to navigate efficiently through the search tree
350  // (see KnapsackSearchPath).
351  int depth_;
352  const KnapsackSearchNode* const parent_;
353  KnapsackAssignment assignment_;
354 
355  // 'current_profit' and 'profit_upper_bound' fields are used to sort search
356  // nodes using a priority queue. That allows to pop the node with the best
357  // upper bound, and more importantly to stop the search when optimality is
358  // proved.
359  int64 current_profit_;
360  int64 profit_upper_bound_;
361 
362  // 'next_item_id' field allows to avoid an O(number_of_items) scan to find
363  // next item to select. This is done for free by the upper bound computation.
364  int next_item_id_;
365 
366  DISALLOW_COPY_AND_ASSIGN(KnapsackSearchNode);
367 };
368 
369 // ----- KnapsackSearchPath -----
370 // KnapsackSearchPath is a small class used to represent the path between a
371 // node to another node in the search tree.
372 // As the solution state is not stored for each search node, the state should
373 // be rebuilt at each node. One simple solution is to apply all decisions
374 // between the node 'to' and the root. This can be computed in
375 // O(number_of_items).
376 //
377 // However, it is possible to achieve better average complexity. Two
378 // consecutively explored nodes are usually close enough (i.e., much less than
379 // number_of_items) to benefit from an incremental update from the node
380 // 'from' to the node 'to'.
381 //
382 // The 'via' field is the common parent of 'from' field and 'to' field.
383 // So the state can be built by reverting all decisions from 'from' to 'via'
384 // and then applying all decisions from 'via' to 'to'.
386  public:
388  const KnapsackSearchNode& to);
389  void Init();
390  const KnapsackSearchNode& from() const { return from_; }
391  const KnapsackSearchNode& via() const { return *via_; }
392  const KnapsackSearchNode& to() const { return to_; }
394  int depth) const;
395 
396  private:
397  const KnapsackSearchNode& from_;
398  const KnapsackSearchNode* via_; // Computed in 'Init'.
399  const KnapsackSearchNode& to_;
400 
401  DISALLOW_COPY_AND_ASSIGN(KnapsackSearchPath);
402 };
403 
404 // ----- KnapsackState -----
405 // KnapsackState represents a partial solution to the knapsack problem.
407  public:
408  KnapsackState();
409 
410  // Initializes vectors with number_of_items set to false (i.e. not bound yet).
411  void Init(int number_of_items);
412  // Updates the state by applying or reverting a decision.
413  // Returns false if fails, i.e. trying to apply an inconsistent decision
414  // to an already assigned item.
415  bool UpdateState(bool revert, const KnapsackAssignment& assignment);
416 
417  int GetNumberOfItems() const { return is_bound_.size(); }
418  bool is_bound(int id) const { return is_bound_.at(id); }
419  bool is_in(int id) const { return is_in_.at(id); }
420 
421  private:
422  // Vectors 'is_bound_' and 'is_in_' contain a boolean value for each item.
423  // 'is_bound_(item_i)' is false when there is no decision for item_i yet.
424  // When item_i is bound, 'is_in_(item_i)' represents the presence (true) or
425  // the absence (false) of item_i in the current solution.
426  std::vector<bool> is_bound_;
427  std::vector<bool> is_in_;
428 
429  DISALLOW_COPY_AND_ASSIGN(KnapsackState);
430 };
431 
432 // ----- KnapsackPropagator -----
433 // KnapsackPropagator is the base class for modeling and propagating a
434 // constraint given an assignment.
435 //
436 // When some work has to be done both by the base and the derived class,
437 // a protected pure virtual method ending by 'Propagator' is defined.
438 // For instance, 'Init' creates a vector of items, and then calls
439 // 'InitPropagator' to let the derived class perform its own initialization.
441  public:
442  explicit KnapsackPropagator(const KnapsackState& state);
443  virtual ~KnapsackPropagator();
444 
445  // Initializes data structure and then calls InitPropagator.
446  void Init(const std::vector<int64>& profits,
447  const std::vector<int64>& weights);
448 
449  // Updates data structure and then calls UpdatePropagator.
450  // Returns false when failure.
451  bool Update(bool revert, const KnapsackAssignment& assignment);
452  // ComputeProfitBounds should set 'profit_lower_bound_' and
453  // 'profit_upper_bound_' which are constraint specific.
454  virtual void ComputeProfitBounds() = 0;
455  // Returns the id of next item to assign.
456  // Returns kNoSelection when all items are bound.
457  virtual int GetNextItemId() const = 0;
458 
459  int64 current_profit() const { return current_profit_; }
460  int64 profit_lower_bound() const { return profit_lower_bound_; }
461  int64 profit_upper_bound() const { return profit_upper_bound_; }
462 
463  // Copies the current state into 'solution'.
464  // All unbound items are set to false (i.e. not in the knapsack).
465  // When 'has_one_propagator' is true, CopyCurrentSolutionPropagator is called
466  // to have a better solution. When there is only one propagator
467  // there is no need to check the solution with other propagators, so the
468  // partial solution can be smartly completed.
469  void CopyCurrentStateToSolution(bool has_one_propagator,
470  std::vector<bool>* solution) const;
471 
472  protected:
473  // Initializes data structure. This method is called after initialization
474  // of KnapsackPropagator data structure.
475  virtual void InitPropagator() = 0;
476 
477  // Updates internal data structure incrementally. This method is called
478  // after update of KnapsackPropagator data structure.
479  virtual bool UpdatePropagator(bool revert,
480  const KnapsackAssignment& assignment) = 0;
481 
482  // Copies the current state into 'solution'.
483  // Only unbound items have to be copied as CopyCurrentSolution was already
484  // called with current state.
485  // This method is useful when a propagator is able to find a better solution
486  // than the blind instantiation to false of unbound items.
488  std::vector<bool>* solution) const = 0;
489 
490  const KnapsackState& state() const { return state_; }
491  const std::vector<KnapsackItemPtr>& items() const { return items_; }
492 
493  void set_profit_lower_bound(int64 profit) { profit_lower_bound_ = profit; }
494  void set_profit_upper_bound(int64 profit) { profit_upper_bound_ = profit; }
495 
496  private:
497  std::vector<KnapsackItemPtr> items_;
498  int64 current_profit_;
499  int64 profit_lower_bound_;
500  int64 profit_upper_bound_;
501  const KnapsackState& state_;
502 
503  DISALLOW_COPY_AND_ASSIGN(KnapsackPropagator);
504 };
505 
506 // ----- KnapsackCapacityPropagator -----
507 // KnapsackCapacityPropagator is a KnapsackPropagator used to enforce
508 // a capacity constraint.
509 // As a KnapsackPropagator is supposed to compute profit lower and upper
510 // bounds, and get the next item to select, it can be seen as a 0-1 Knapsack
511 // solver. The most efficient way to compute the upper bound is to iterate on
512 // items in profit-per-unit-weight decreasing order. The break item is
513 // commonly defined as the first item for which there is not enough remaining
514 // capacity. Selecting this break item as the next-item-to-assign usually
515 // gives the best results (see Greenberg & Hegerich).
516 //
517 // This is exactly what is implemented in this class.
518 //
519 // When there is only one propagator, it is possible to compute a better
520 // profit lower bound almost for free. During the scan to find the
521 // break element all unbound items are added just as if they were part of
522 // the current solution. This is used in both ComputeProfitBounds and
523 // CopyCurrentSolutionPropagator.
524 // For incrementality reasons, the ith item should be accessible in O(1). That's
525 // the reason why the item vector has to be duplicated 'sorted_items_'.
527  public:
529  ~KnapsackCapacityPropagator() override;
530  void ComputeProfitBounds() override;
531  int GetNextItemId() const override { return break_item_id_; }
532 
533  protected:
534  // Initializes KnapsackCapacityPropagator (e.g., sort items in decreasing
535  // order).
536  void InitPropagator() override;
537  // Updates internal data structure incrementally (i.e., 'consumed_capacity_')
538  // to avoid a O(number_of_items) scan.
539  bool UpdatePropagator(bool revert,
540  const KnapsackAssignment& assignment) override;
542  std::vector<bool>* solution) const override;
543 
544  private:
545  // An obvious additional profit upper bound corresponds to the linear
546  // relaxation: remaining_capacity * efficiency of the break item.
547  // It is possible to do better in O(1), using Martello-Toth bound U2.
548  // The main idea is to enforce integrality constraint on the break item,
549  // ie. either the break item is part of the solution, either it is not.
550  // So basically the linear relaxation is done on the item before the break
551  // item, or the one after the break item.
552  // This is what GetAdditionalProfit method implements.
553  int64 GetAdditionalProfit(int64 remaining_capacity, int break_item_id) const;
554 
555  const int64 capacity_;
556  int64 consumed_capacity_;
557  int break_item_id_;
558  std::vector<KnapsackItemPtr> sorted_items_;
559  int64 profit_max_;
560 
561  DISALLOW_COPY_AND_ASSIGN(KnapsackCapacityPropagator);
562 };
563 
564 // ----- BaseKnapsackSolver -----
565 // This is the base class for knapsack solvers.
567  public:
568  explicit BaseKnapsackSolver(const std::string& solver_name)
569  : solver_name_(solver_name) {}
570  virtual ~BaseKnapsackSolver() {}
571 
572  // Initializes the solver and enters the problem to be solved.
573  virtual void Init(const std::vector<int64>& profits,
574  const std::vector<std::vector<int64> >& weights,
575  const std::vector<int64>& capacities) = 0;
576 
577  // Gets the lower and upper bound when the item is in or out of the knapsack.
578  // To ensure objects are correctly initialized, this method should not be
579  // called before ::Init.
580  virtual void GetLowerAndUpperBoundWhenItem(int item_id, bool is_item_in,
581  int64* lower_bound,
582  int64* upper_bound);
583 
584  // Solves the problem and returns the profit of the optimal solution.
585  virtual int64 Solve(TimeLimit* time_limit, bool* is_solution_optimal) = 0;
586 
587  // Returns true if the item 'item_id' is packed in the optimal knapsack.
588  virtual bool best_solution(int item_id) const = 0;
589 
590  virtual std::string GetName() const { return solver_name_; }
591 
592  private:
593  const std::string solver_name_;
594 };
595 
596 // ----- KnapsackGenericSolver -----
597 // KnapsackGenericSolver is the multi-dimensional knapsack solver class.
598 // In the current implementation, the next item to assign is given by the
599 // master propagator. Using SetMasterPropagator allows changing the default
600 // (propagator of the first dimension), and selecting another dimension when
601 // more constrained.
602 // TODO(user): In the case of a multi-dimensional knapsack problem, implement
603 // an aggregated propagator to combine all dimensions and give a better guide
604 // to select the next item (see, for instance, Dobson's aggregated efficiency).
606  public:
607  explicit KnapsackGenericSolver(const std::string& solver_name);
608  ~KnapsackGenericSolver() override;
609 
610  // Initializes the solver and enters the problem to be solved.
611  void Init(const std::vector<int64>& profits,
612  const std::vector<std::vector<int64> >& weights,
613  const std::vector<int64>& capacities) override;
614  int GetNumberOfItems() const { return state_.GetNumberOfItems(); }
615  void GetLowerAndUpperBoundWhenItem(int item_id, bool is_item_in,
616  int64* lower_bound,
617  int64* upper_bound) override;
618 
619  // Sets which propagator should be used to guide the search.
620  // 'master_propagator_id' should be in 0..p-1 with p the number of
621  // propagators.
622  void set_master_propagator_id(int master_propagator_id) {
623  master_propagator_id_ = master_propagator_id;
624  }
625 
626  // Solves the problem and returns the profit of the optimal solution.
627  int64 Solve(TimeLimit* time_limit, bool* is_solution_optimal) override;
628  // Returns true if the item 'item_id' is packed in the optimal knapsack.
629  bool best_solution(int item_id) const override {
630  return best_solution_.at(item_id);
631  }
632 
633  private:
634  // Clears internal data structure.
635  void Clear();
636 
637  // Updates all propagators reverting/applying all decision on the path.
638  // Returns true if fails. Note that, even if fails, all propagators should
639  // be updated to be in a stable state in order to stay incremental.
640  bool UpdatePropagators(const KnapsackSearchPath& path);
641  // Updates all propagators reverting/applying one decision.
642  // Return true if fails. Note that, even if fails, all propagators should
643  // be updated to be in a stable state in order to stay incremental.
644  bool IncrementalUpdate(bool revert, const KnapsackAssignment& assignment);
645  // Updates the best solution if the current solution has a better profit.
646  void UpdateBestSolution();
647 
648  // Returns true if new relevant search node was added to the nodes array, that
649  // means this node should be added to the search queue too.
650  bool MakeNewNode(const KnapsackSearchNode& node, bool is_in);
651 
652  // Gets the aggregated (min) profit upper bound among all propagators.
653  int64 GetAggregatedProfitUpperBound() const;
654  bool HasOnePropagator() const { return propagators_.size() == 1; }
655  int64 GetCurrentProfit() const {
656  return propagators_.at(master_propagator_id_)->current_profit();
657  }
658  int64 GetNextItemId() const {
659  return propagators_.at(master_propagator_id_)->GetNextItemId();
660  }
661 
662  std::vector<KnapsackPropagator*> propagators_;
663  int master_propagator_id_;
664  std::vector<KnapsackSearchNode*> search_nodes_;
665  KnapsackState state_;
666  int64 best_solution_profit_;
667  std::vector<bool> best_solution_;
668 
669  DISALLOW_COPY_AND_ASSIGN(KnapsackGenericSolver);
670 };
671 #endif // SWIG
672 } // namespace operations_research
673 
674 #endif // OR_TOOLS_ALGORITHMS_KNAPSACK_SOLVER_H_
virtual int64 Solve(TimeLimit *time_limit, bool *is_solution_optimal)=0
virtual void GetLowerAndUpperBoundWhenItem(int item_id, bool is_item_in, int64 *lower_bound, int64 *upper_bound)
BaseKnapsackSolver(const std::string &solver_name)
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
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
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)
void Init(const std::vector< int64 > &profits, const std::vector< std::vector< int64 > > &weights, const std::vector< int64 > &capacities) override
bool best_solution(int item_id) const override
int64 Solve(TimeLimit *time_limit, bool *is_solution_optimal) override
void CopyCurrentStateToSolution(bool has_one_propagator, std::vector< bool > *solution) const
virtual bool UpdatePropagator(bool revert, const KnapsackAssignment &assignment)=0
virtual int GetNextItemId() const =0
const KnapsackState & state() const
void Init(const std::vector< int64 > &profits, const std::vector< int64 > &weights)
const std::vector< KnapsackItemPtr > & items() const
virtual void CopyCurrentStateToSolutionPropagator(std::vector< bool > *solution) const =0
KnapsackPropagator(const KnapsackState &state)
bool Update(bool revert, const KnapsackAssignment &assignment)
KnapsackSearchNode(const KnapsackSearchNode *const parent, const KnapsackAssignment &assignment)
const KnapsackAssignment & assignment() const
const KnapsackSearchNode *const parent() const
const KnapsackSearchNode * MoveUpToDepth(const KnapsackSearchNode &node, int depth) const
const KnapsackSearchNode & via() const
KnapsackSearchPath(const KnapsackSearchNode &from, const KnapsackSearchNode &to)
const KnapsackSearchNode & from() const
const KnapsackSearchNode & to() const
This library solves knapsack problems.
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.
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.
SolverType
Enum controlling which underlying algorithm is used.
@ KNAPSACK_MULTIDIMENSION_SCIP_MIP_SOLVER
SCIP based solver.
@ KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER
Generic Solver.
@ KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER
Dynamic Programming approach for single dimension problems.
@ KNAPSACK_64ITEMS_SOLVER
Optimized method for single dimension small problems.
@ KNAPSACK_BRUTE_FORCE_SOLVER
Brute force method.
@ KNAPSACK_MULTIDIMENSION_CBC_MIP_SOLVER
CBC Based Solver.
bool IsSolutionOptimal() const
Returns true if the solution was proven optimal.
void set_use_reduction(bool use_reduction)
void Init(int number_of_items)
bool UpdateState(bool revert, const KnapsackAssignment &assignment)
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
Definition: time_limit.h:105
SharedTimeLimit * time_limit
int64_t int64
const int64 profit_max
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
KnapsackItem * KnapsackItemPtr
int64 capacity
KnapsackAssignment(int _item_id, bool _is_in)
double GetEfficiency(int64 profit_max) const
KnapsackItem(int _id, int64 _weight, int64 _profit)