圆排列问题 todo

https://blog.csdn.net/qq_37373250/article/details/81477394 #include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

const int N=4;
double minlen=10000,x[N],r[N];//分别为最小圆排列长度，每个圆心横坐标，每个圆半径
double bestr[N];//最小圆排列的半径顺序

double center(int t)//得到每个圆的圆心坐标
{
    double temp=0;
    for(int j=1;j<t;++j)//因为目标圆有可能与排在它之前的任一圆相切，故需一一判断
    {
        double xvalue=x[j]+2.0*sqrt(r[t]*r[j]);//不是r[j],是x[j],要被自己蠢哭了
        if(xvalue>temp)
            temp=xvalue;
    }
    return temp;
}
void compute()
{
    double low=0,high=0;
    for(int i=1;i<N;++i)
    {
        if(x[i]-r[i]<low)
            low=x[i]-r[i];
        if(x[i]+r[i]>high)
            high=x[i]+r[i];
    }
    if(high-low<minlen)
    {
        minlen=high-low;
        for(int i=1;i<N;++i)
            bestr[i]=r[i];
    }
}
void backtrack(int t)
{
    if(t==N)
    {
        compute();
    }
    else
    {
        for(int j=t;j<N;++j)
        {
            swap(r[t],r[j]);
            double centerx=center(t);
            if(centerx+r[t]+r[1]<minlen)
            {
                x[t]=centerx;
                backtrack(t+1);
            }
            swap(r[t],r[j]);
        }
    }
}
int main()
{
    r[1]=1,r[2]=1,r[3]=2;
    cout<<"每个圆的半径分别为：";
    for(int i=1;i<N;++i)
        cout<<r[i]<<' ';
    cout<<endl;
    backtrack(1);
    cout<<"最小圆排列长度为："<<minlen<<endl;
    cout<<"最优圆排列的顺序对应的半径分别为：";
    for(int i=1;i<N;++i)
        cout<<bestr[i]<<' ';
    cout<<endl;
    return 0;
}

同样的方法

//https://blog.csdn.net/u012319493/article/details/49205945

#include "stdio.h"
#include "math.h"
#define MAX 10

int n;  //圆的个数
float min = 10000;  //当前圆排列的最小长度
int r[MAX];  //各个圆的半径
int bestr[MAX];   //最优排列下圆的半径
float x[MAX];  //各个圆的圆心

void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}

//计算当前圆排列的长度
void compute()
{
    int i;
    float low = 0;  //圆位于原点右侧
    float heigh = 0;
    for(i=1; i<=n; i++)
    {
        if(x[i]-r[i]<low)  //寻找最左边的坐标，当圆位于原点左侧时才会更新
            low = x[i]-r[i];
        if(x[i]+r[i]>heigh)  //寻找最右边的坐标
            heigh = x[i]+r[i];
    }
    if(heigh-low<min)  //如果当前圆排列的长度小于之前的最优值
        min =  heigh - low;  //更新
}

//计算当前所选择圆的圆心
float center(int i)
{
    int j;
    float temp = 0.0;
    float valuex;
    for(j=1; j<i; j++)
    {
        valuex = x[j] + 2.0*sqrt(r[j]*r[i]);  //寻找当前层下最右边的圆心
        if(valuex>temp)
            temp = valuex;
    }
    return temp;
}

void backtrack(int i)
{
    if(i>n)  //如果到最后一个圆
    {
        compute();  //计算当前圆排列的最小长度
        int  j;
        for(j=1; j<=n; j++)
            bestr[j] = r[j];
    }
    else
    {
        int j;
        for(j=i; j<=n; j++)  //选择要排列的圆
        {
            swap(r[i], r[j]); //选择第j个圆
            float centerx = center(i);  //计算圆心
            if(centerx+r[i]<min)  //下界约束，当前圆的长度<最优值，才能产生最优值
            {
                x[i] = centerx;  //记录圆心
                backtrack(i+1);  //搜索下一层
            }
            swap(r[i], r[j]);  //返回上一层
        }
    }
}

void circle(int n1, int r1[])
{
    n = n1;
    int i;
    for(i=1; i<=n; i++)
        r[i] = r1[i];
    backtrack(1);
}

int main()
{
    int n1 = 3;
    int r1[]={0, 1, 1, 2};
    circle(n1, r1);
    printf("圆的个数为：%d\n", n);
    printf("半径分别为：\n");
    int i;
    for(i=1; i<=n; i++)
        printf("%d ", r1[i]);
    printf("\n");
    printf("最优排列下，圆的半径为：\n");
    for(i=1; i<=n; i++)
        printf("%d ", bestr[i]);
    printf("\n");
    printf("最小长度为：%.3f\n", min);
    return 0;
}