ryzom/server/src/ai_service/knapsack_solver.cpp

   1 // Ryzom - MMORPG Framework <http://dev.ryzom.com/projects/ryzom/>
   2 // Copyright (C) 2010  Winch Gate Property Limited
   3 //
   4 // This source file has been modified by the following contributors:
   5 // Copyright (C) 2020  Jan BOON (Kaetemi) <jan.boon@kaetemi.be>
   6 //
   7 // This program is free software: you can redistribute it and/or modify
   8 // it under the terms of the GNU Affero General Public License as
   9 // published by the Free Software Foundation, either version 3 of the
  10 // License, or (at your option) any later version.
  11 //
  12 // This program is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU Affero General Public License for more details.
  16 //
  17 // You should have received a copy of the GNU Affero General Public License
  18 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  19
  20
  21
  22 #include "stdpch.h"
  23 #include "knapsack_solver.h"
  24
  25 //////////////////////////////////////////////////////////////////////////////
  26 // CKnapsackSolver                                                          //
  27 //////////////////////////////////////////////////////////////////////////////
  28
  29 std::string CKnapsackSolver::toString(Algorithm a)
  30 {
  31         switch (a)
  32         {
  33         case Optimal:                           return "Optimal";
  34         case FullAddCheck:                      return "FullAddCheck";
  35         case AddCheck:                          return "AddCheck";
  36         case FastAddCheck:                      return "FastAddCheck";
  37         case FullSingleReplace:         return "FullSingleReplace";
  38         case SingleReplace:                     return "SingleReplace";
  39         case FastSingleReplace:         return "FastSingleReplace";
  40         case VeryFastSingleReplace:     return "VeryFastSingleReplace";
  41         case TakeAll:                           return "TakeAll";
  42         default:                                        return "undefined";
  43         }
  44 }
  45
  46 CKnapsackSolver::Algorithm CKnapsackSolver::fromString(std::string const& a)
  47 {
  48         if (a=="Optimal")                               return Optimal;
  49         if (a=="FullAddCheck")                  return FullAddCheck;
  50         if (a=="AddCheck")                              return AddCheck;
  51         if (a=="FastAddCheck")                  return FastAddCheck;
  52         if (a=="FullSingleReplace")             return FullSingleReplace;
  53         if (a=="SingleReplace")                 return SingleReplace;
  54         if (a=="FastSingleReplace")             return FastSingleReplace;
  55         if (a=="VeryFastSingleReplace") return VeryFastSingleReplace;
  56         if (a=="TakeAll")                               return TakeAll;
  57         return UndefinedAlgorithm;
  58 }
  59
  60 /// Find the set that fit the specified maximum weight which have the maximal
  61 /// value total, using an already defined good solution.
  62 void CKnapsackSolver::optimize(float wMax, Algorithm algorithm)
  63 {
  64         H_AUTO(CKnapsackSolver_optimize);
  65         _WMax = wMax;
  66         // Solve the problem
  67         switch (algorithm)
  68         {
  69         case FullAddCheck:                      optimizeFullAddCheck();                         break;
  70         case AddCheck:                          optimizeAddCheck();                                     break;
  71         case FastAddCheck:                      optimizeFastAddCheck();                         break;
  72         case FullSingleReplace:         optimizeFullSingleReplace();            break;
  73         case SingleReplace:                     optimizeSingleReplace();                        break;
  74         default:
  75         case FastSingleReplace:         optimizeFastSingleReplace();            break;
  76         case VeryFastSingleReplace:     optimizeVeryFastSingleReplace();        break;
  77         case Optimal:                           optimizeOptimal();                                      break;
  78         case TakeAll:                           optimizeTakeAll();                                      break;
  79         }
  80 }
  81
  82 /// Algorithm is taken from http://eleves.ensmp.fr/P00/00rouaul/sacados/sacados_swp.html
  83 /// This algorithm complexity is O(N^2)
  84 void CKnapsackSolver::optimizeOptimal()
  85 {
  86         H_AUTO(CKnapsackSolver_optimizeOptimal);
  87         // :FIXME: Not thread safe
  88         // Allocate temporary solution
  89         bool* take = new bool[size()];
  90         for (size_t i=0; i<size(); ++i)
  91                 take[i] = false;
  92         // Run the optimization recursion
  93         optimizeOptimalRec((int)size()-1, _WMax, 0, take);
  94         // Delete temporary solution
  95         delete [] take;
  96 }
  97
  98 /// @param i take[j] for j>i are already determined by the recursion
  99 /// @param w Free weight to fill
 100 /// @param v Sum of the taken values (ie all value(j) where take[j] is true and j > i)
 101 /// @param take Current examined partial solution
 102 void CKnapsackSolver::optimizeOptimalRec(int i, float w, float v, bool* take)
 103 {
 104         nlassert(i>=-1);
 105         if (i==-1)
 106         {
 107                 if (v > _VBest)
 108                 {
 109                         _WBest = _WMax - w;
 110                         _VBest = v;
 111                         std::copy(take, take+size(), _Take);
 112                 }
 113         }
 114         else
 115         {
 116                 take[i] = false;
 117                 optimizeOptimalRec(i-1, w, v, take);
 118                 if (weight(i) <= w)
 119                 {
 120                         take[i] = true;
 121                         optimizeOptimalRec(i - 1, w - weight(i), v + value(i), take);
 122                 }
 123         }
 124 }
 125
 126 /// Here we consider already defined solution has lots of take[i] that are
 127 /// true. We just find the first i for which take[i] is false and that don't
 128 /// exceed maximal weight. If we find one we take it which gives a better
 129 /// solution.
 130 /// Note: We start at the end since CTargetable puts candidate at end.
 131 /// This algorithm complexity is O(N)
 132 void CKnapsackSolver::optimizeAddCheck()
 133 {
 134         H_AUTO(CKnapsackSolver_optimizeAddCheck);
 135         int i = (int)size()-1;
 136         float w = _WMax - _WBest;
 137         while (i>=0)
 138         {
 139                 if (!_Take[i] && weight(i) <= w)
 140                 {
 141                         _Take[i] = true;
 142                         _WBest += weight(i);
 143                         _VBest += value(i);
 144                         break;
 145                 }
 146                 --i;
 147         }
 148 }
 149
 150 /// Same as AddCheck, except that we consider all false take[i], even if we already took some.
 151 /// This algorithm complexity is Theta(N)
 152 void CKnapsackSolver::optimizeFullAddCheck()
 153 {
 154         H_AUTO(CKnapsackSolver_optimizeFullAddCheck);
 155         int i = (int)size()-1;
 156         float w = _WMax - _WBest;
 157         while (i>=0)
 158         {
 159                 if (!_Take[i] && weight(i) <= w)
 160                 {
 161                         _Take[i] = true;
 162                         _WBest += weight(i);
 163                         _VBest += value(i);
 164                 }
 165                 --i;
 166         }
 167 }
 168
 169 /// Same as AddCheck, except that we examine only a single false take[i], event if it cannot be taken.
 170 /// This algorithm complexity is O(N), but O(1) when used by CTargetable
 171 void CKnapsackSolver::optimizeFastAddCheck()
 172 {
 173         H_AUTO(CKnapsackSolver_optimizeFastAddCheck);
 174         int i = (int)size()-1;
 175         float w = _WMax - _WBest;
 176         while (i>=0)
 177         {
 178                 if (!_Take[i])
 179                 {
 180                         if (weight(i) <= w)
 181                         {
 182                                 _Take[i] = true;
 183                                 _WBest += weight(i);
 184                                 _VBest += value(i);
 185                         }
 186                         break;
 187                 }
 188                 --i;
 189         }
 190 }
 191
 192 /// First try FullAddCheck, then try to replace the already taken elements with not taken ones.
 193 /// This algorithm complexity is Theta(N^2)
 194 void CKnapsackSolver::optimizeFullSingleReplace()
 195 {
 196         optimizeFullAddCheck();
 197         H_AUTO(CKnapsackSolver_optimizeFullSingleReplace);
 198         int i = (int)size()-1;
 199         while (i>=0)
 200         {
 201                 // For each not taken ith element
 202                 if (!_Take[i])
 203                 {
 204                         float w = weight(i);
 205                         float v = value(i);
 206                         int worst = i;
 207                         // Find the worst element that ith element can replace
 208                         int j = (int)size()-1;
 209                         while (j>=0)
 210                         {
 211                                 if (i!=j && _Take[j] && w<=weight(j) && v>value(j))
 212                                 {
 213                                         worst = j;
 214                                         w = weight(j);
 215                                         v = value(j);
 216                                 }
 217                                 --j;
 218                         }
 219                         // If we find one untake it and take ith.
 220                         if (worst!=i)
 221                         {
 222                                 _Take[worst] = false;
 223                                 _WBest -= weight(worst);
 224                                 _VBest -= value(worst);
 225                                 _Take[i] = true;
 226                                 _WBest += weight(i);
 227                                 _VBest += value(i);
 228                         }
 229                 }
 230                 --i;
 231         }
 232 }
 233
 234 /// First try FastAddCheck, and if it fails optimizing try to replace a not
 235 /// taken one with an already taken element (the worst one) until a
 236 /// replacement occurs.
 237 /// This algorithm complexity is Theta(N^2) and O(N^2) for CTargetable
 238 void CKnapsackSolver::optimizeSingleReplace()
 239 {
 240         float vBest = _VBest;
 241         optimizeAddCheck();
 242         if (_VBest > vBest)
 243                 return;
 244         H_AUTO(CKnapsackSolver_optimizeSingleReplace);
 245         int i = (int)size()-1;
 246         while (i>=0)
 247         {
 248                 // For each not taken ith element
 249                 if (!_Take[i])
 250                 {
 251                         float w = weight(i);
 252                         float v = value(i);
 253                         int worst = i;
 254                         // Find the worst element that ith element can replace
 255                         int j = (int)size()-1;
 256                         while (j>=0)
 257                         {
 258                                 if (i!=j && _Take[j] && w<=weight(j) && v>value(j))
 259                                 {
 260                                         worst = j;
 261                                         w = weight(j);
 262                                         v = value(j);
 263                                 }
 264                                 --j;
 265                         }
 266                         // If we find one untake it and take ith.
 267                         if (worst!=i)
 268                         {
 269                                 _Take[worst] = false;
 270                                 _WBest -= weight(worst);
 271                                 _VBest -= value(worst);
 272                                 _Take[i] = true;
 273                                 _WBest += weight(i);
 274                                 _VBest += value(i);
 275                                 break;
 276                         }
 277                 }
 278                 --i;
 279         }
 280 }
 281
 282 /// First try FastAddCheck, and if it fails optimizing try to replace the
 283 /// first not taken element with an already taken element (the worst one).
 284 /// This algorithm complexity is O(N^2) and Theta(N) for CTargetable
 285 void CKnapsackSolver::optimizeFastSingleReplace()
 286 {
 287         float vBest = _VBest;
 288         optimizeFastAddCheck();
 289         if (_VBest > vBest)
 290                 return;
 291         H_AUTO(CKnapsackSolver_optimizeFastSingleReplace);
 292         int i = (int)size()-1;
 293         while (i>=0)
 294         {
 295                 // For each not taken ith element
 296                 if (!_Take[i])
 297                 {
 298                         float w = weight(i);
 299                         float v = value(i);
 300                         int worst = i;
 301                         // Find the worst element that ith element can replace
 302                         int j = (int)size()-1;
 303                         while (j>=0)
 304                         {
 305                                 if (i!=j && _Take[j] && w<=weight(j) && v>value(j))
 306                                 {
 307                                         worst = j;
 308                                         w = weight(j);
 309                                         v = value(j);
 310                                 }
 311                                 --j;
 312                         }
 313                         // If we find one untake it and take ith.
 314                         if (worst!=i)
 315                         {
 316                                 _Take[worst] = false;
 317                                 _WBest -= weight(worst);
 318                                 _VBest -= value(worst);
 319                                 _Take[i] = true;
 320                                 _WBest += weight(i);
 321                                 _VBest += value(i);
 322                         }
 323                         break;
 324                 }
 325                 --i;
 326         }
 327 }
 328
 329 /// First try FastAddCheck, and if it fails optimizing try to replace the
 330 /// first not taken element with an already taken one (the first worst that
 331 /// the not taken one).
 332 /// This algorithm complexity is O(N^2) and O(N) for CTargetable
 333 void CKnapsackSolver::optimizeVeryFastSingleReplace()
 334 {
 335         float vBest = _VBest;
 336         optimizeFastAddCheck();
 337         if (_VBest > vBest)
 338                 return;
 339         H_AUTO(CKnapsackSolver_optimizeVeryFastSingleReplace);
 340         int i = (int)size()-1;
 341         while (i>=0)
 342         {
 343                 // For each not taken ith element
 344                 if (!_Take[i])
 345                 {
 346                         float w = weight(i);
 347                         float v = value(i);
 348                         int worst = i;
 349                         // Find the worst element that ith element can replace
 350                         int j = (int)size()-1;
 351                         while (j>=0)
 352                         {
 353                                 if (i!=j && _Take[j] && w<=weight(j) && v>value(j))
 354                                 {
 355                                         worst = j;
 356                                         w = weight(j);
 357                                         v = value(j);
 358                                         break;
 359                                 }
 360                                 --j;
 361                         }
 362                         // If we find one untake it and take ith.
 363                         if (worst!=i)
 364                         {
 365                                 _Take[worst] = false;
 366                                 _WBest -= weight(worst);
 367                                 _VBest -= value(worst);
 368                                 _Take[i] = true;
 369                                 _WBest += weight(i);
 370                                 _VBest += value(i);
 371                         }
 372                         break;
 373                 }
 374                 --i;
 375         }
 376 }
 377
 378 void CKnapsackSolver::optimizeTakeAll()
 379 {
 380         H_AUTO(CKnapsackSolver_optimizeTakeAll);
 381         _WBest = 0;
 382         _VBest = 0;
 383         int i = (int)size()-1;
 384         while (i>=0)
 385         {
 386                 _Take[i] = true;
 387                 _WBest += weight(i);
 388                 _VBest += value(i);
 389                 --i;
 390         }
 391 }
 392
 393 CKnapsackSolver::CKnapsackSolver(IKnapsackContext* context, bool* _take)
 394 : _Context(context)
 395 , _Take(_take)
 396 , _AllocatedTake(_take==NULL)
 397 , _WBest(0.f)
 398 , _VBest(0.f)
 399 , _WMax(0.f)
 400 {
 401         if (_take==NULL && size()!=0)
 402         {
 403                 size_t sz = size();
 404                 _Take = new bool[sz];
 405                 for (size_t i = 0; i < sz; ++i)
 406                         _Take[i] = false;
 407         }
 408         else
 409         {
 410                 for (size_t i=0; i<size(); ++i)
 411                 {
 412                         if (take(i))
 413                         {
 414                                 _WBest += weight(i);
 415                                 _VBest += value(i);
 416                         }
 417                 }
 418                 _WMax = _WBest;
 419         }
 420 }
 421
 422 CKnapsackSolver::~CKnapsackSolver()
 423 {
 424         if (_AllocatedTake)
 425                 delete [] _Take;
 426 }
 427
 428 float CKnapsackSolver::weight(size_t i)
 429 {
 430         if (_Context!=0)
 431                 return _Context->weight(i);
 432         else
 433                 return 0.f;
 434 }
 435
 436 float CKnapsackSolver::value(size_t i)
 437 {
 438         if (_Context!=0)
 439                 return _Context->value(i);
 440         else
 441                 return 0.f;
 442 }
 443
 444 size_t CKnapsackSolver::size()
 445 {
 446         if (_Context!=0)
 447                 return _Context->size();
 448         else
 449                 return 0;
 450 }
 451
 452 bool CKnapsackSolver::take(size_t i)
 453 {
 454         if (_Take!=0 && i>=0 && i<size())
 455                 return _Take[i];
 456         else
 457                 return false;
 458 }
 459
 460 float CKnapsackSolver::totalWeight()
 461 {
 462         return _WBest;
 463 }
 464
 465 float CKnapsackSolver::totalValue()
 466 {
 467         return _VBest;
 468 }
 469
 470 float CKnapsackSolver::totalFreeWeight()
 471 {
 472         return _WMax - _WBest;
 473 }
 474
 475 //////////////////////////////////////////////////////////////////////////////
 476 // CKnapsackContext                                                         //
 477 //////////////////////////////////////////////////////////////////////////////
 478
 479 CKnapsackContext::CKnapsackContext(size_t size, float* weights, float* values)
 480 : _Size(size)
 481 , _Weights(weights)
 482 , _Values(values)
 483 {
 484 }
 485
 486 float CKnapsackContext::weight(size_t i)
 487 {
 488         if (i>=0 && i<_Size)
 489                 return _Weights[i];
 490         else
 491                 return 0.f;
 492 }
 493
 494 float CKnapsackContext::value(size_t i)
 495 {
 496         if (i>=0 && i<_Size)
 497                 return _Values[i];
 498         else
 499                 return 0.f;
 500 }
 501
 502 size_t CKnapsackContext::size()
 503 {
 504         return _Size;
 505 }