动态规划-凸多边形最优三角形（权值和）

参考b站讲解链接->凸多边形最优三角形

1.算法概述

  给定一个具有N个顶点的多边形，每个顶点都有一个权值。我们的目标是将该多边形划分为若干个不相交的凸三角形，并使这些凸三角形的权值和最小。

2.算法实现

   定义一个名为minScoreTriangulationPlan的函数来计算多边形的最小权值和。该函数采用分治的思想，具体实现如下：

double minScoreTriangulationPlan(double a[], int l, int r)
{
    if (r - l < 2)   // 当点数小于3时，无法构成三角形，返回0
    {
        return 0;
    }
    if (r - l == 2)  // 当点数等于3时，可以构成一个三角形，返回权值和
    {
        return a[l] + a[l + 1] + a[r];
    }
    else  // 当点数大于3时，需要遍历求解最小权值和
    {
        double minScore;
        int biaoji = l + 1;  // 记录权值和最小的点索引
        for (int i = l + 1; i < r; i++)
        {
            double left = minScoreTriangulationPlan(a, l, i);     // 左边的权值和，递归调用得到
            double mid = a[l] + a[i] + a[r];                      // 中间直接计算权值
            double right = minScoreTriangulationPlan(a, i, r);    // 右边的权值和，递归调用得到
            double sum = left + mid + right;                      // 当前划分方式下的权值和
 
            if (i == l + 1)
            {
                minScore = sum;  // 记录初始最小权值和
            }
            minScore = min(sum, minScore);   // 更新最小权值和
            if (minScore == sum)
            {
                biaoji = i;   // 更新最小权值和对应的点索引
            }
        }
        cout << "第" << l + 1 << "(" << a[l] << ")" << "区域到"
             << r + 1 << "(" << a[r] << ")" << "区域，"
             << "最小连点为" << biaoji + 1 << "(" << a[biaoji] << ")" << endl;
        return minScore;   // 返回最小权值和
    }
}

3.算法使用

  在主函数中，通过用户输入来获取多边形的点数和各个顶点的权值，并调用minScoreTriangulationPlan函数来计算最小权值和。最后，将结果输出给用户。

int main()
{
    cout << "请输入多边形的点数：" << endl;
    int N;
    cin >> N;
    double a[N];
    for (int i = 0; i < N; i++)
    {
        cout << "请输入第" << i + 1 << "点的权值：" << endl;
        cin >> a[i];
    }
    double minScore = minScoreTriangulationPlan(a, 0, N - 1);
    cout << "多边形构成凸三角形最小的权值和为：" << minScore << endl;
 
    return 0;
}

4.算法解释

  首先，判断多边形的点数。如果点数小于3，即无法构成三角形，直接返回0。

   如果点数等于3，那么这三个点可以构成一个三角形，并返回它们的权值和。
   对于点数大于3的情况，通过循环遍历所有的划分方式，递归计算左右两侧的最小权值和，并计算当前划分下的权值和。同时，我们记录使得权值和最小的划分方式，并将其对应的点索引保存下来。

   最后，输出权值和最小的划分方式，并返回最小权值和。

5.运行结果

 

6.完整代码

#include<iostream>
#include<cmath>
 
using namespace std;
 
// 计算多边形分割后的最小权值和
double minScoreTriangulationPlan(double a[], int l, int r)
{
// 当点数小于3，无法构成三角形，返回0
if (r - l < 2)
{
return 0;
}
// 当点数等于3，可以构成一个三角形，返回权值和
if (r - l == 2)
{
return a[l] + a[l + 1] + a[r];
}
// 当点数大于3，需要遍历求解最小权值和
else
{
double minScore;
int biaoji = l + 1; // 记录权值和最小的点索引
for (int i = l + 1; i < r; i++)
{
double left = minScoreTriangulationPlan(a, l, i);     // 左边的权值和，递归调用得到
double mid = a[l] + a[i] + a[r];                      // 中间直接计算权值
double right = minScoreTriangulationPlan(a, i, r);    // 右边的权值和，递归调用得到
double sum = left + mid + right;                      // 当前划分方式下的权值和
 
        // 更新最小权值和
        if (i == l + 1)
        {
            minScore = sum;
        }
        minScore = min(sum, minScore);
        if (minScore == sum)
        {
            biaoji = i;
        }
    }
    cout << "第" << l + 1 << "(" << a[l] << ")" << "区域到"
         << r + 1 << "(" << a[r] << ")" << "区域，"
         << "最小连点为" << biaoji + 1 << "(" << a[biaoji] << ")" << endl;
    return minScore;
}
}
 
int main()
{
cout << "请输入多边形的点数：" << endl;
int N;
cin >> N;
double a[N];
for (int i = 0; i < N; i++)
{
cout << "请输入第" << i + 1 << "点的权值：" << endl;
cin >> a[i];
}
double minScore = minScoreTriangulationPlan(a, 0, N - 1);
cout << "多边形构成凸三角形最小的权值和为：" << minScore << endl;
 
return 0;
}