5-10 圆排列问题(回溯)

给定n个大小不等的圆c1, c2,…, cn，现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。
例如，当n=3，且所给的3个圆的半径分别为1，1，2时，这3个圆的最小长度的圆排列如图所示。其最小长度为2+4√2
在这里插入图片描述

二、分析

在这里插入图片描述
求左右边界
左边界：所有圆的X坐标减去半径得到的最小值
右边界：所有圆的X坐标加上半径得到的最大值
求圆心坐标时，假定它跟前面的所有圆相切，求出圆心坐标，值最大的就是真的

在这里插入图片描述

三、代码

//5-10 圆排列问题
//排列树
//给n个圆和n个圆的半径 
#include<iostream>
#include<string.h> 
#include<cmath>
#include<algorithm> 
#define INF 0x3f3f3f3f
using namespace std; 
int n;//圆的个数 
float x[100];//当前圆排列圆心坐标 
float r[100];//当前圆排列 
float minn = INF;//当前最优值
void Print(float b[100]){for(int i=1;i<=n;i++)cout<<b[i]<<" ";cout<<endl;
}
float Center(int t){//求圆心坐标:假定它跟前面的所有圆相切，求出圆心坐标，值最大的就是真的float ans=0;for(int i=1;i<t;i++){float v=x[i]+2.0*sqrt(r[t]*r[i]);//2.0*sqrt(a*b)=sqrt(pow(a+b,2),pow(a-b,2))if(v>ans) ans=v;}return ans;
} 
void Compute(){float low=INF;//左边界：所有圆的X坐标减去半径得到的 最小值float high=0;//右边界：所有圆的X坐标加上半径得到的 最大值for(int i=1;i<=n;i++){float w=x[i]-r[i];//先计算左边界if(w<low) low=w;float v=x[i]+r[i];//在计算右边界if(v>high) high=v;} cout<<"high-low="<<high-low<<endl;if(high-low<minn) minn=high-low;//边长为右边界减左边界 }
void Swap(float &a,float &b){float t=a;a=b;b=t;
}
//排列树
void BackTrack(int t){ //第t个顶点 if(t>n){//到达叶结点Compute();Print(r);return;}else{for(int i=t;i<=n;i++){//从剩下的圆选一个放在t位置 Swap(r[t],r[i]);float centerx=Center(t);//求t的圆心坐标	if(centerx+r[t]+r[1]<minn){x[t]=centerx;BackTrack(t+1);		}Swap(x[t],x[i]);}	}	
} 
int main(){int t;//边数 int x,y,z;cin>>n;for(int i=1;i<=n;i++){cin>>r[i];}cout<<"--------------\n"; BackTrack(1); cout<<"minn="<<minn<<endl;return 0;
}
/*
3
1 1 2
*/