ryzom/server/src/ai_service/knapsack_solver.h

   1 // Ryzom - MMORPG Framework <http://dev.ryzom.com/projects/ryzom/>
   2 // Copyright (C) 2010  Winch Gate Property Limited
   3 //
   4 // This program is free software: you can redistribute it and/or modify
   5 // it under the terms of the GNU Affero General Public License as
   6 // published by the Free Software Foundation, either version 3 of the
   7 // License, or (at your option) any later version.
   8 //
   9 // This program is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 // GNU Affero General Public License for more details.
  13 //
  14 // You should have received a copy of the GNU Affero General Public License
  15 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16
  17 #ifndef RYAI_KNAPSACK_SOLVER_H
  18 #define RYAI_KNAPSACK_SOLVER_H
  19
  20 //////////////////////////////////////////////////////////////////////////////
  21 // IKnapsackContext                                                          //
  22 //////////////////////////////////////////////////////////////////////////////
  23
  24 class IKnapsackContext
  25 {
  26 public:
  27         virtual ~IKnapsackContext() { }
  28         virtual float weight(size_t i) = 0;
  29         virtual float value(size_t i) = 0;
  30         virtual size_t size() = 0;
  31 };
  32
  33 //////////////////////////////////////////////////////////////////////////////
  34 // CKnapsackSolver                                                          //
  35 //////////////////////////////////////////////////////////////////////////////
  36
  37 /// This class resolves the knapsack problem, in french "probleme du sac a
  38 /// dos"
  39 class CKnapsackSolver
  40 {
  41 public:
  42         enum Algorithm
  43         {
  44                 UndefinedAlgorithm,
  45                 Optimal,
  46                 FullAddCheck,
  47                 AddCheck,
  48                 FastAddCheck,
  49                 FullSingleReplace,
  50                 SingleReplace,
  51                 FastSingleReplace,
  52                 VeryFastSingleReplace,
  53         //- /!\ Algorithms below don't respect constraints
  54                 TakeAll
  55         };
  56         static std::string toString(Algorithm a);
  57         static CKnapsackSolver::Algorithm fromString(std::string const& a);
  58 private:
  59         IKnapsackContext* _Context;
  60         bool* _Take;
  61         bool _AllocatedTake;
  62         float _WBest;
  63         float _VBest;
  64         float _WMax;
  65 public:
  66         explicit CKnapsackSolver(IKnapsackContext* context, bool* take = NULL);
  67         virtual ~CKnapsackSolver();
  68         bool take(size_t i);
  69         float totalWeight();
  70         float totalValue();
  71         float totalFreeWeight();
  72
  73         /// @param wMax Max weight that can be taken
  74         /// @note Not thread safe
  75         void optimize(float wMax, Algorithm algorithm = Optimal);
  76 private:
  77         float weight(size_t i);
  78         float value(size_t i);
  79         size_t size();
  80         /// @name Algorithms entry points
  81         //@{
  82         void optimizeOptimal();
  83         void optimizeFullAddCheck();
  84         void optimizeAddCheck();
  85         void optimizeFastAddCheck();
  86         void optimizeFullSingleReplace();
  87         void optimizeSingleReplace();
  88         void optimizeFastSingleReplace();
  89         void optimizeVeryFastSingleReplace();
  90         void optimizeTakeAll();
  91         //@}
  92         /// @name Algorithms helper functions
  93         //@{
  94         void optimizeOptimalRec(int i, float w, float v, bool* take);
  95         //@}
  96 };
  97
  98 //////////////////////////////////////////////////////////////////////////////
  99 // CKnapsackContext                                                         //
 100 //////////////////////////////////////////////////////////////////////////////
 101
 102 class CKnapsackContext
 103 : public IKnapsackContext
 104 {
 105         size_t _Size;
 106         float* _Weights;
 107         float* _Values;
 108 public:
 109         CKnapsackContext(size_t size, float* weights, float* values);
 110         virtual float weight(size_t i);
 111         virtual float value(size_t i);
 112         virtual size_t size();
 113 };
 114
 115 #endif