Odmiana problemu komiwojażera - algorytm z powrotami

 
#include <iostream>
#include <stack>
#include <fstream>
#include <cmath>

using namespace std;

struct sWierzch{
    int x;
    int y;
    int waga;
    int indeks;
};

int n,m,najw_profit,aktual_profit,it,aktual_dlugosc;  //n - il wierzch, m - max dlugosc, it - zlicza iteracje
bool *czyOdwiedz;                                                // tab odwiedzin
sWierzch *W;                                                       // tab wierzcholkow
stack <sWierzch> najl_droga;
stack <sWierzch> aktual_droga;  


int odleglosc(sWierzch w1, sWierzch w2)
{
    return ( sqrt( (w1.x-w2.x)*(w1.x-w2.x) + (w1.y-w2.y)*(w1.y-w2.y) ) );
}


void TSP(sWierzch v)
{
    int u;
        it++;                                         //zliczamy iteracje - elementy stosu?
        aktual_droga.push(v);                // zapamiętujemy na stosie bieżący wierzchołek

        if(it < n)                          // jeśli brak ścieżki Hamiltona, to jej szukamy
        {

            czyOdwiedz[it] = true;            // Oznaczamy bieżący wierzchołek jako odwiedzony
            for(u = 0; u < n; u++)            // Przeglądamy sąsiadów wierzchołka v
            if(!czyOdwiedz[u] && ((aktual_dlugosc + odleglosc(v,W[u]) + odleglosc(W[u],W[0])) <= m) )       /* Szukamy nieodwiedzonego jeszcze sąsiada, sprawdzamy, czy droga bedzie miala odpowiednia dlugosc*/
            {
                aktual_profit += W[u].waga;            // Dodajemy wagę u do profitu
                aktual_dlugosc += odleglosc(v,W[u]);  //Dodajemy odleglosc od aktualnego wierzcholka do nastepnego
                TSP(W[u]);                                    // Rekurencja
                aktual_profit -= W[u].waga;            // Usuwamy wagę u z sumy
            }
            czyOdwiedz[it] = false;                    // Zwalniamy bieżący wierzchołek
        }
        else if((aktual_dlugosc + odleglosc(v,W[it]) + odleglosc(W[it],W[0])) <= m)  // Jeśli nie ma nieodwiedzonych sasiadow, a droga spelnia warunek
        {
                           // to sprawdzamy, czy aktualny profit jest najwiekszy
            if(aktual_profit > najw_profit)                    // Jeśli tak,
            {
                najw_profit = aktual_profit;                    
                najl_droga = aktual_droga;
            }

        }

        aktual_droga.pop();
        it--;                        // Usuwamy bieżący wierzchołek ze ścieżki
}


int main()
{
    int i; 

    ifstream in;

    in.open("in.txt");

    in >> n >> m;                  // Czytamy liczbę wierzchołków i ich wagi

    // Inicjalizacja

    czyOdwiedz = new bool [n];     
    W = new sWierzch [n];

    for(i = 0; i < n; i++)
    {
        czyOdwiedz[i] = false;
        W[i] = {0,0,0,0};
    }
    it = 0;

  // Odczytujemy dane wejściowe

    for(i = 0; i < n; i++)
    {
        in >> W[i].x >> W[i].y >> W[i].waga;
        W[i].indeks = i;
    }

  // Rozpoczynamy algorytm

    najw_profit  = 0;
    aktual_profit = 0;
    aktual_dlugosc = 0;

    TSP(W[0]);

    cout <<W[0].indeks<<" ";
    while(!najl_droga.empty())
    {
        cout << najl_droga.top().indeks << " ";
        najl_droga.pop();
    }
    cout << "najw_profit = " << najw_profit << "\n";


  // Sprzatamy

    in.close();

    delete [] czyOdwiedz;
    delete [] W;

    return 0;
}

#include <iostream>
#include <stack>
#include <fstream>
#include <cmath>
#include <vector>

using namespace std;

struct sWierzch{
    int x;
    int y;
    int waga;
    int indeks;
};

int n,m,najw_profit,aktual_profit,it; //n - il wierzch, m - max dlugosc
float aktual_dlugosc;
vector <bool> czyOdwiedz;                         // tab odwiedzin
vector <sWierzch> W;                             // tab wierzcholkow
stack <sWierzch> najl_droga;
stack <sWierzch> aktual_droga;              // Stosy w tablicy

void TSP(sWierzch v)
{
    int u;
    cout<<"dodaje w:"<<it<<"\n";
        ++it;
        aktual_droga.push(v);                // zapamiętujemy na stosie bieżący wierzchołek

        if(it < n)                   // jeśli brak ścieżki Hamiltona, to jej szukamy
        {

            czyOdwiedz[it] = true;            // Oznaczamy bieżący wierzchołek jako odwiedzony
            for(u = 0; u < n; ++u)           // Przeglądamy sąsiadów wierzchołka v
            if(!czyOdwiedz[u] && ((aktual_dlugosc + hypot(v.x-W[u].x,v.y-W[u].y) + hypot(W[0].x-W[u].x,W[0].y-W[u].y)) <= m) )       // Szukamy nieodwiedzonego jeszcze sąsiada
            {
                aktual_profit += W[u].waga;            // Dodajemy wagę u do sumy
                aktual_dlugosc += hypot(v.x-W[u].x,v.y-W[u].y);
                TSP(W[u]);                             // Rekurencyjnie wywołujemy szukanie cyklu Hamiltona
                aktual_profit -= W[u].waga;            // Usuwamy wagę u z sumy
            }
            czyOdwiedz[it] = false;                    // Zwalniamy bieżący wierzchołek
        }
        else if((aktual_dlugosc + hypot(v.x-W[it].x,v.y-W[it].y) + hypot(W[0].x-W[it].x,W[0].y-W[it].y)) <= m)
        {
            if(aktual_profit > najw_profit)                    // Jeśli tak,
            {
                najw_profit = aktual_profit;                     // To zapamiętujemy tę sumę
                najl_droga = aktual_droga;                       // i droge
            }
            aktual_dlugosc -= hypot(W[0].x-W[it].x,W[0].y-W[it].y);
        }

        aktual_droga.pop();
        --it;                        // Usuwamy bieżący wierzchołek ze ścieżki
}


int main()
{
    int i;
    sWierzch tmp;

    ifstream in("in.txt",ios_base::in);

    in.open("in.txt");
    cout << "otworzylem in\n";

    in >> n >> m;                  // Czytamy liczbę wierzchołków i maksymalna dlugosc

  // Inicjalizacja

    W.reserve(n);
    czyOdwiedz.reserve(n);
    it = 0;

  // Odczytujemy dane wejściowe

    for(i = 0; i < n; ++i)
    {
        in >> tmp.x >> tmp.y >> tmp.waga;
        tmp.indeks = i;
        W.push_back(tmp);
    }

    cout << "Wczytalem wierzcholki\n";

  // Rozpoczynamy algorytm

    najw_profit  = 0;
    aktual_profit = 0;
    aktual_dlugosc = 0;

    TSP(W[0]);

    while(!najl_droga.empty())
    {
        cout << najl_droga.top().indeks << " ";
        najl_droga.pop();
    }
    cout << W[0].indeks << "\n";
    cout << "najw_profit = " << najw_profit << "\n";

    cout << "sprzatam\n";

    in.close();

    return 0;
}
 

struct Bajzel
  {
   int n,m,najw_profit,aktual_profit,it; //n - il wierzch, m - max dlugosc
   float aktual_dlugosc;
   vector <bool> czyOdwiedz;                         // tab odwiedzin
   vector <sWierzch> W;                             // tab wierzcholkow
   stack <sWierzch> najl_droga;
   stack <sWierzch> aktual_droga;              // Stosy w tablicy
  };
 
void TSP(sWierzch v,Bajzel &b)
{ ...

            for(u = 0; u < n; ++u)           // Przeglądamy sąsiadów wierzchołka v
            if(...

Bajzel b;
in >> b.n >> b.m; 
b.W.reserve(n);
...
n.najw_profit=0;
...
TSP(b.W[0],b);

#include <iostream>
#include <stack>
#include <fstream>
#include <cmath>
#include <vector>

using namespace std;

struct sWierzch{
    int x;
    int y;
    int waga;
    int indeks;
};

struct sDeklar{
    int n,m,najw_profit,aktual_profit,it; //n - il wierzch, m - max dlugosc
    float aktual_dlugosc;
    vector <bool> czyOdwiedz;                         // tab odwiedzin
    vector <sWierzch> W;                             // tab wierzcholkow
    stack <sWierzch> najl_droga;
    stack <sWierzch> aktual_droga;              // Stosy w tablicy
};

void TSP(sWierzch v, sDeklar &d)
{
    int u;
    cout<<"dodaje w:"<<d.it<<"\n";
        ++d.it;                                 //ilosc wierzcholkow/iteracji
        d.aktual_droga.push(v);                // zapamiętujemy na stosie bieżący wierzchołek

        float odl_od_ost_do_pierw = 0;   
        odl_od_ost_do_pierw = hypot( d.W[0].x-d.W[d.it].x, d.W[0].y-d.W[d.it].y ); //odl od ostatniego wierzcholka na stosie do pierwszego

        if(d.it < d.n)                   // jeśli brak ścieżki Hamiltona, to jej szukamy
        {
            d.czyOdwiedz[d.it] = true;            // Oznaczamy bieżący wierzchołek jako odwiedzony
            for(u = 0; u < d.n; ++u)            // Przeglądamy sąsiadów wierzchołka v
            {
                float do_nast = 0;
                do_nast = hypot( v.x-d.W[u].x, v.y-d.W[u].y );

                if(!d.czyOdwiedz[u] && ((d.aktual_dlugosc + do_nast + hypot( d.W[0].x-d.W[u].x, d.W[0].y-d.W[u].y )) <= d.m) )       // Szukamy nieodwiedzonego jeszcze sąsiada i spr, czy dlugosc trasy do aktualnego wierzcholka + dlugosc trasy do nastepnego wierzcholka + dlugosc trasy od nastepnego do poczatkowego miesci sie w zakresie
                {
                    d.aktual_profit += d.W[u].waga;            // Dodajemy wagę nastepnego wierzcholka u do sumy
                    d.aktual_dlugosc += do_nast;
                    TSP(d.W[u],d);                             // Rekurencyjnie wywołujemy szukanie cyklu Hamiltona
                    d.aktual_profit -= d.W[u].waga;            // Usuwamy wagę u z sumy
                }
            }
            d.czyOdwiedz[d.it] = false;                    // Zwalniamy bieżący wierzchołek
        }
        else if((d.aktual_dlugosc + hypot( v.x-d.W[d.it].x, v.y-d.W[d.it].y ) + odl_od_ost_do_pierw) <= d.m)
        {
            if(d.aktual_profit > d.najw_profit)                    // Jeśli tak,
            {
                d.najw_profit = d.aktual_profit;                     // To zapamiętujemy tę sumę
                d.najl_droga = d.aktual_droga;                       // i droge
            }
            d.aktual_dlugosc -= odl_od_ost_do_pierw;
        }

        d.aktual_droga.pop();
        --d.it;                                             // Usuwamy bieżący wierzchołek ze ścieżki
}


int main()
{
    int i;
    sWierzch tmp;
    sDeklar d;

    ifstream in("in.txt",ios_base::in);

    in.open("in.txt");
    cout << "otworzylem in\n";

    in >> d.n >> d.m;                  // Czytamy liczbę wierzchołków i maksymalna dlugosc

  // Inicjalizacja

    d.W.reserve(d.n);
    d.czyOdwiedz.reserve(d.n);
    d.it = 0;

  // Odczytujemy dane wejściowe

    for(i = 0; i < d.n; ++i)
    {
        in >> tmp.x >> tmp.y >> tmp.waga;
        tmp.indeks = i;
        d.W.push_back(tmp);
    }

    cout << "Wczytalem wierzcholki\n";

  // Rozpoczynamy algorytm

    d.najw_profit  = 0;
    d.aktual_profit = 0;
    d.aktual_dlugosc = 0;
    cout << "costam\n";
    TSP(d.W[0],d);

    while(!d.najl_droga.empty())
    {
        cout << d.najl_droga.top().indeks << " ";
        d.najl_droga.pop();
    }
    cout << d.W[0].indeks << "\n";
    cout << "najw_profit = " << d.najw_profit << "\n";

    cout << "sprzatam\n";

    in.close();

    return 0;
}