ETS.rar_ETS_site:www.pudn.com_推销员问题

#include<iostream> using namespace std; #define max 10 int n; int array[max]; //存储每次生成的排列 int map[max][max]; int Selected[max]; int TotalCost=-1; //交换数组中元素 void Swap(int array[], int k, int i) { int temp = array[k]; array[k] = array[i]; array[i] = temp; } //生成全排列 void Permutate(int array[], int k) { //产生array[k:n]的所有排列 if(k==n) {//只剩一个元素 int temp = 0; for(int i=0; i<n-1; i++) { if(map[i][(i+1)%n]==0) break; temp+=map[array[i]][array[(i+1)]%n]; } if(i==n-1 && (TotalCost==-1||(TotalCost!=-1&&temp<TotalCost))) { TotalCost = temp; for(i=0; i<n; i++) Selected[i] = array[i]; } } else //还有多个元素，递归产生排列 for(int i=k; i<n; i++) { Swap(array,k,i); Permutate(array,k+1); Swap(array,k,i); } } int main() { cout<<"Please input the number of cities(not greater than 10):"<<endl; cin>>n; for(int i=0; i<n; i++) { array[i] =i; for(int j=0; j<n; j++) cin>>map[i][j]; } Permutate(array,0); if(TotalCost!=-1) { cout<<"the selected route is:"; for(int i=0; i<n-1; i++) cout<<Selected[i]<<"->"; cout<<Selected[n-1]<<endl; cout<<"the minimum cost is:"<<TotalCost<<endl; } else cout<<"no solution"<<endl; return 0; }