货郎挡.cpp

算法的几个程序 排序 货郎档 二分法

#include<iostream.h>
const int N=5;
int matrix[N][N]={0,10,35,30,20,
	          5,0, 9, 10,15,
	          6,13,0, 12,10,
		  8,8, 9, 0 ,25,  
                  10,35,4,12,0 };

int g(int i,bool v[])   //递归求最优路线长度
{
	bool flag=true;
	for(int j=0;j<N;j++)
	{
		flag&=v[j];
	}
    if(flag)
		return matrix[i][0];     //全部遍历过了则返回当前结点到1的长度
	int min=99999;                 //设置监视哨 
	int cost,node;
	for(j=1;j<N;j++)
	{
		if(v[j]==true) continue;    //跳过已遍历的结点
		v[j]=true;					//当前结点
		cost=matrix[i][j]+g(j,v);	//递归调用
		if(min>cost)
		{
			min=cost;				//保存最小路径长度
			node=j;
		}
		v[j]=false;
	}
	return min;
}
int J(int i,bool v[])   //求最优路线结点
{
	bool flag=true;
	for(int j=0;j<N;j++)
	{
		flag&=v[j];
	}
    if(flag) return i;		//全部遍历过了则返回当前结点
	int min=99999;			//设置监视哨
	int cost,node;
	for(j=1;j<N;j++)
	{
		if(v[j]==true) continue;	//跳过已遍历的结点
		v[j]=true;					//当前结点
		cost=matrix[i][j]+g(j,v);	//递归调用
		if(min>cost)
		{
			min=cost;
			node=j;					//保存结点
		}
		v[j]=false;
	}
	return node;
}

void main()
{
	bool v[N]={false,false,false,false};
	v[0]=true;
	int min=99999;
	int cost,node;
	for(int i=1;i<N;i++)
	{
		v[i]=true;
		cost=matrix[0][i]+g(i,v);
		if(min>cost)
		{
			min=cost;
			node=i;
		}
		v[i]=false;
	}
	cout<<"最短路径长度为:"<<min<<endl;

	int path[10];
	int index=0;
	path[index]=node;
	index++;
	int nextNode;
    v[node]=true;
	nextNode=J(node,v);
	while(node!=nextNode)
	{
		path[index]=nextNode;
		index++;
		node=nextNode;
		v[node]=true;
		nextNode=J(node,v);
	}
	path[index]='\0';
	cout<<"最优周游路线为:"<<"1 ";
	for(i=0;path[i]!='\0';i++) 
		cout<<path[i]+1<<" ";
	cout<<"1"<<endl;
}