C++ Алгоритм решения максимизации в линейном программировании

Question

Я изучаю максимизацию с помощью линейного программирования и натолкнулся на алгоритм максимизации с двумя переменными (в данном случаесеребром и золотом), но я не уверен, что делает определенный раздел кода:

using namespace std;


class PreciousStones {
  int n;
  vector<int> as;
  vector<int> ag;

Функция ниже - это раздел, который мне неясен:

  double maxg (double s) {
    double g = 0;
    for (int i=0; i<n; i++)
      if (s == 0)
        g += ag[i];
      else if (as[i] <= s) 
        s -= as[i];
      else {
        g += (1-s/as[i])*ag[i];
        s = 0;
      }
    return g;
  }

Остальная часть кода приведена ниже (для контекста), если кто-то знает о некоторых соответствующих документах по этому алгоритму или может дать краткое объяснение этой функции, я был бы очень признателен

public:
  double value(vector <int> silver, vector <int> gold) {
    n = silver.size();
    as = silver;
    ag = gold;
    for (int i=0; i<n; i++) 
      for (int j=i+1; j<n; j++) 
        if (as[j]*ag[i] > as[i]*ag[j]) {
          swap(as[i], as[j]);
          swap(ag[i], ag[j]);
        }
    double lo = 0;
    double hi = 51*100;
    double D = 1e-10;
    while (lo+D < hi && lo*(1+D) < hi) {
      double mid = (lo+hi)/2;
      if (mid <= maxg(mid))
        lo = mid;
      else
        hi = mid;
    }
    return lo;
  }
}; 

Answer 1

Волшебные слова, которые вам нужны в Google - это "Симплексный алгоритм" для максимизации ограничений линейного программирования. Эта слайд-колода выглядит так, как будто вы хотите этого. http://www.cs.nccu.edu/~melikyan/mat_fm/lec/lec5_4.pdf