Блог

Я написал код, который дает наименьшую стоимость для массива, в котором хранится длина путей из каждого города в каждый город. Я использовал рекурсию в своем коде. Пользователь выбирает первый город, из которого продавец начинает свой тур. Продавец должен посетить каждый город один раз и вернуться в город, из которого он начал. Мой код дает правильную стоимость, но я понятия не имею, как получить путь, который дает наименьшую стоимость. Должен ли я использовать некоторые дополнительные массивы? Я не знаю, когда добавить город к пути. Какая-нибудь помощь?

 void Dynamic::dynamic(Array array) {  int start;  size = array.getSize();  s = size;  path = new int[size 1];        cout lt;lt; "Which city we start from?" lt;lt; endl;  cin gt;gt; start;  int* cities = new int[size];  for (int i=0; ilt;size 1; i  )  {  cities[i] = i;    }        int cost = g(array, size-1, cities, start, start, s);    coutlt;lt;"Minimum cost: " lt;lt; cost lt;lt; endl;  cout lt;lt; "Path:" lt;lt;endl;    for (int i=size; igt;=0; i--)  {  cout lt;lt; path[i] lt;lt; "t";  }    cout lt;lt; "n";   }  int Dynamic::g(Array amp; array, int level, int* tab, int city, int start, int z) {  if (levelgt;0)  {     int minimum = INF;      int position;  bool exists = false;  int k = z;    for (int i=0; ilt;z; i  )  {    if (tab[i] == city)  {  position = i;  exists = true;  }  }    int* tmp;    if (exists == true)    {  k = z-1;  tmp = new int [k];  for (int i=0; ilt;position; i  )  {  tmp[i] = tab[i];  }    for (int i=position; ilt;k; i  )  {  tmp[i] = tab[i 1];  }  }    else  {  tmp = new int [k];  for (int i=0; ilt;k; i  )  {  tmp[i] = tab[i];  }  }      for (int i=0; ilt;k; i  )  {        int c = array[city][tmp[i]];    int* t = new int [k-1];  for(int j=0; jlt;i; j  )  {  t[j] = tmp[j];  }     for (int j=i; jlt;k-1; j  )  {  t[j] = tmp[j 1];  }      int a = g(array, level-1, t, tmp[i], start, k-1);    int result = c   a;    if (minimumgt; result)  {  minimum = result;        }      }    return minimum;  }    if (level == 0)  {    return array[city][start];  } }