#include<iostream>

#include <iomanip>

#define pnum 5 //pnum=總點數減1 
 int d[pnum+1][pnum+1]={{0,10,20,30,40,50},{12,0,18,30,25,21},{23,19,0,5,10,15},
 {34,32,4,0,8,16},{45,27,11,10,0,18},{56,22,16,20,12,0}};//費用數組
 int road[pnum+2];
 int curpoint ;//計算路徑用 
using namespace std;
class mylist
{
public:
	
	int s[pnum];
	int num;
public:
	void delk(int k);//減小集合,計算路徑用 
	int getdata(int i);
	void setdata(int j,int data);
	    
};
 int min(int *p,int length) {//計算數組里的最小值
 int mindata,pos;            //并返回返回該值的序號在curpoint中
 mindata=1000;
 pos=0;
 while(pos<length)
 {
   if(*p<mindata)
   {
    mindata=*p;   
    curpoint=pos;
    }
   p++;     
   pos+=1;
 }    
 return mindata;
}

void mylist::delk(int k)  //最后計算路徑時逐步減小集合逆向計算路徑
{
	int i;
	int position;
	for(i=0;i<=num-1;i++)
	{
		if(s[i]==k)
		{
			position=i;
			break;
		}
	}
	if(i<(num-1))
	{
		for(i=position;i<(num-1);i++)
		{
			s[i]=s[i+1];
		}
	}
	num=num-1;
}
int mylist::getdata(int i)
{
     return s[i];
}
void mylist::setdata(int j,int data)
{
     s[j]=data;
}
int tsp(mylist &mls,int k )   //遞歸子程序計算最小費用
{
	int b[pnum],i,j;
	mylist mls2;
    if(mls.num==1)
	{
		return d[0][k];
	}
	else
	{   j=0;
		for(i=0;i<mls.num;i++) //把mls-k賦給mls，從而利用算法的公式計算 
		{
            if((mls.getdata(i))!=k)
            {
             mls2.setdata(j,mls.getdata(i));
             j++;
            }
            else
            {
            }
        }
        mls2.num=mls.num-1; //把mls-k賦給mls2 
		
        for(i=0;i<mls2.num;i++)
		{
            j=mls2.getdata(i);        //TSP的遞推公式
			b[i]=tsp(mls2,j)+d[j][k]; //使用mls2避免在引用中的修改				
		}                            
		return min(b,mls2.num);

   } 
}
int main()
{
    int a[pnum],i;//a[pnum]存放引用TSP后的各條路徑費用
	int result; 
	mylist ml;
	ml.num=pnum;
	for(i=0;i<ml.num;i++)
	ml.setdata(i,i+1);
	for(i=0;i<pnum;i++)  //計算最后到i節的費用
	{
		a[i]=tsp(ml,i+1)+d[i+1][0];
	}
	
	result=min(a,ml.num);
	road[pnum+1]=0;
	road[pnum]=curpoint+1;
	for(i=pnum-1;i>=1;i--)
	{
     tsp(ml,road[i+1]);//得到連接road[i]的節點的序號 
	 ml.delk(road[i+1]);//得到tsp程序中的mls2進行下一步計算  
	 road[i]=ml.getdata(curpoint);//分析min函數的curpoint, 
    }							  //得到當前子集的最后通過點ml.getdata(curpoint)
	road[0]=0;
	cout<<"**動態規劃球旅行商問題**"<<endl;
	cout<<setw(10)<<"耗費矩陣："<<endl;
	cout<<setw(25)<<"{0,10,20,30,40,50}"<<endl;
	cout<<setw(25)<<"{12,0,18,30,25,21}"<<endl;
	cout<<setw(25)<<"{23,19,0,5 ,10,15}"<<endl;
	cout<<setw(25)<<"{34,32,4,0 ,8 ,16}"<<endl;
	cout<<setw(25)<<"{45,27,11,10,0,18}"<<endl;
	cout<<setw(25)<<"{56,22,16,20,12,0}"<<endl;

	cout<<"最低耗費量 ："<<result<<endl;
	cout<<"最低耗費路徑 :";
	for(i=0;i<(pnum+2);i++)
	cout<<road[i]+1<<"->";
	cout<<endl;
	return 0;
	
}