#include <iostream>
#include <vector>
using namespace std;

double eps = 0.0000001;
bool vec_is_int(vector<vector<double>> v, int j)
{
    double k;
    for (int i = 0; i < v.size() - 2; i++)
    {
        if (v[i][j]<0)
            return false;
    }
    for (int i = 0; i<v.size() - 1; i++)
    {
        k = abs(round(v[i][j]) - v[i][j]);
        if (k >eps)
            return false;
    }
    return true;
}

int main()
{
    int l, k, st = 2, sv = 2;
    bool bEndFlag = true;
    setlocale(LC_CTYPE, "rus");
    double m = 6, n = 11;

    cout << "Введите m: ";
    cin >> m;
    cout << "Введите n: ";
    cin >> n;
    //double **mas;

    //cin >> st; //Число строк
    l = st + 1;
    //cin >> sv; //Число столбцов
    k = sv + l;

    //mas = new double*[n]; //Выделение памяти под n-строк

    //for (i = 0; i < n; i++)
    //{
    //  mas[i] = new double[k]; //Выделение памяти для каждой строки по k-столбцов
    //}
    vector<vector<double>> mas(l);

    for (int i = 0; i < l; i++)
    {
        mas[i].resize(k); //Выделение памяти для каждой строки по k-столбцов
    }
    mas[0][0] = m;
    mas[0][1] = m;
    mas[0][2] = 1;
    mas[0][3] = 0;
    mas[0][4] = 53;
    mas[1][0] = n + 1;
    mas[1][1] = 1;
    mas[1][2] = 0;
    mas[1][3] = 1;
    mas[1][4] = 23;
    mas[2][0] = -n;
    mas[2][1] = -n + 1;
    mas[2][2] = 0;
    mas[2][3] = 0;
    mas[2][4] = 0;


    //for (i = 0; i < l; i++)
    //{
    //  if (i<l - 1)
    //      cout << "Введите коэффициенты(значения базисных переменных,свободные члены) " << i + 1 << " -го ур-ия" << endl;
    //  else
    //      cout << "Введите целевую функцию с ОТРИЦАТЕЛЬНЫМ ЗНАКОМ: " << endl;
    //  for (j = 0; j < k; j++)
    //  {
    //      cout << "mas[" << i << "][" << j << "]="; //Ввод массива
    //      cin >> mas[i][j];
    //  }
    //}
    //вывод массива
    cout << endl;
    cout << endl << "***********************************" << endl;
    cout << " Таблица: " << endl;
    int min;
    for (int i = 0; i < l; i++)
    {
        for (int j = 0; j < k; j++)
        {

            cout << " " << mas[i][j] << " ";
        }
        cout << " " << endl;
    }
    cout << endl << "***********************************" << endl;

    int w = 0;
    w = sv + 1;

    //определяем оптимальность решения
    int kpol = 0;
    for (int j = 0; j < k; j++)
    {
        if (mas[l - 1][j] > 0)
            kpol++;
    }
    // cout<<"kpol="<<kpol<<"\n";если в последней строчке 4 положительных числа,то мы нашли решение
    cout << "целевая функция равняется" << mas[l - 1][k - 1] << "\n";

    while (kpol<w)
    {
        kpol = 0;

        // поиск минимального
        min = 0;
        for (int j = 1; j < sv; j++)
            if (mas[l - 1][j] < mas[l - 1][min]) min = j;
        cout << " этот столбец ведущий " << mas[l - 1][min] << endl;
        double t;

        t = mas[l - 1][min];

        // поиск столбца
        cout << endl << "***********************************" << endl;
        int myn = 0;
        double r = 0, z = 0;
        z = (mas[myn][k - 1]) / (mas[myn][min]);
        for (int i = 1; i < st; i++)
        {
            r = (mas[i][k - 1]) / (mas[i][min]);
            if (z>r) myn = i;
        }
        cout << "эта строка ведущая " << mas[myn][k - 1] << endl;
        cout << "строка" << myn;
        cout << endl << "***********************************" << "\n";
        cout << "коэффицент" << mas[myn][min] << endl;

        //деление на выбранный элемент
        double u = 0;
        u = mas[myn][min];//для деления на коэффициент
        for (int j = 0; j < k; j++)
        {
            mas[myn][j] = mas[myn][j] / u;
        }
        cout << endl;

        //вывод массива
        cout << endl << "***********************************" << endl;
        cout << endl;
        for (int i = 0; i < l; i++)
        {
            for (int j = 0; j < k; j++)
            {
                cout << " " << mas[i][j] << " ";
            }
            cout << " " << endl;
        }


        //из элеметов соответствующих строк вычитаем элементы найденной нам строки
        double p = 0;
        for (int i = 0; i < l; i++)
        {
            p = mas[i][min];
            if (i != myn)
            {
                for (int j = 0; j < k; j++)
                {
                    mas[i][j] = mas[i][j] - mas[myn][j] * p;
                }
            }
        }


        //вывод массива
        cout << endl << "***********************************" << endl;
        cout << endl;
        for (int i = 0; i < l; i++)
        {
            for (int j = 0; j < k; j++)
            {
                cout << " " << mas[i][j] << " ";
            }
            cout << " " << endl;
        }

        cout << endl << "***********************************" << endl;
        //cout<<"целевая функция равняется"<<mas[n-1][k-1]<<"\n";
        for (int j = 0; j < k; j++)
        {
            if (mas[l - 1][j]>0)
                kpol++;
        }
        // cout<<"kpol="<<kpol<<"\n";если в последней строчке  положительных числа столько, сколько было x(+1 своб.член),то мы нашли решение
    }
    cout << "решение оптимально,целевая функция равняется" << mas[l - 1][k - 1] << "\n";
    int ooo = 0; bool b = true;
    while (bEndFlag)
    {

        if (vec_is_int(mas, k - 1))
            bEndFlag = false;
        else
        {

            ooo = 0;
            for (int i = 0; i<2; i++)
            {
                int w = k - 1;
                if (mas[i][w] != 0)
                {
                    double xr = mas[i][w] - (float)((int)mas[i][w]),
                        xz = mas[ooo][w] - (float)((int)mas[ooo][w]);
                    if (abs(xr)>abs(xz))
                        ooo = i;
                }
            }
            k++;
            for (int i = 0; i < l; i++)
            {
                mas[i].resize(k); //Выделение памяти для каждой строки по k-столбцов
            }
            vector<double> q(k);
            for (int j = 0; j < k - 1; j++)
            {
                q[j] = -mas[ooo][j] + floor(mas[ooo][j]);
            }
            q[k - 1] = 1;
            mas.push_back(q); swap(mas[l - 1], mas[l]);
            for (int i = 0; i <= l; i++)
            {
                swap(mas[i][k - 1], mas[i][k - 2]);
            }
            if (b)
            {
                b = false;
                for (int i = 0; i < k; i++)
                {
                    mas[l][i] = -mas[l][i];
                }
            }
            l++;
            //вывод массива
            cout << endl << "***********************************" << endl;
            cout << endl;
            for (int i = 0; i < l; i++)
            {
                for (int j = 0; j < k; j++)
                {
                    if (abs(mas[i][j]) < eps)
                        mas[i][j] = 0;
                    cout << " " << mas[i][j] << " ";
                }
                cout << " " << endl;
            }

            cout << endl << "***********************************" << endl;
            //system("pause");
            vector<double> O(k - 1);


            int myn = -1;
            for (int i = 0; i < l - 1; i++)
                if (mas[i][k - 1]<-eps)
                {
                    myn = i; break;
                }

            for (int i = 0; i < l - 1; i++)
            {
                if (mas[i][k - 1]<-eps && mas[i][k - 1]<mas[myn][k - 1])
                    myn = i;
            }
            for (int j = 0; j < k - 1; j++)
            {
                if (mas[myn][j]<-eps)
                {
                    O[j] = mas[l - 1][j] / mas[myn][j];
                }
                else
                {
                    O[j] = 999999999999999999;
                }
            }min = 0;
            for (int j = 0; j < k - 1; j++)
                if (abs(O[j])>eps && O[j]<O[min]) min = j;
            cout << " ведущий " << min << " | " << O[min] << endl;
            double u = 0;
            u = mas[myn][min];//для деления на коэффициент

                              //cout << " ведущий " << min << " | " << myn << endl;
                              //из элеметов соответствующих строк вычитаем элементы найденной нам строки
            double p = 0;
            vector<vector<double>> temp(l);
            for (int i = 0; i < l; i++)
                temp[i].resize(k);
            for (int i = 0; i < l; i++)
            {
                p = mas[i][min];
                for (int j = 0; j < k; j++)
                {
                    if (i != myn)
                    {
                        temp[i][j] = mas[i][j] - (mas[myn][j] * p / u);
                    }
                    else
                    {
                        temp[i][j] = mas[i][j] / u;
                    }
                }

            }
            mas = temp;
            //вывод массива
            //cout << endl << "***********************************" << endl;
            //cout << endl;
            //for (int i = 0; i < l; i++)
            //{
            //  for (int j = 0; j < k; j++)
            //  {
            //      cout << " " << mas[i][j] << " ";
            //  }
            //  cout << " " << endl;
            //}
        }
    }
    double x1 = -17, x2 = -17;
    for (int i = 0; i < l; i++)
    {
        if (mas[i][0] == 1)
            x1 = mas[i][k - 1];
        if (mas[i][1] == 1)
            x2 = mas[i][k - 1];

    }
    cout << endl << endl << "x1: "<< x1 << "x2: "<< x2;
    system("pause");
    return 0;
}