问答题 凸多边形是指多边形的任意两点的连线均落在多边形的边界或者内部。相邻的点连线落在多边形边上，称为边，不相邻的点连线落在多边形内部，称为弦。假设任意两点连线上均有权重，凸多边形最优三角剖分问题定义为:求将凸多边形划分为不相交的三角形集合，且各三角形权重之和最小的剖分方案。每个三角形的权重为三条边权重之和。

假设N个点的凸多边形，点编号为V1, V2, .. Vn，若在Vk处将原凸多边形划分为一个三角形V1VkVn，两个子凸多边形V1,V2,...,Vk和Vk, Vk+1, .....Vn。到一个最优的剖分方案，则该最优剖分方案应该包含这两个子凸多边形的最优剖分方案。用m[i][j]表示点Vi-1,Vi….Vj构成的凸多边形的最优剖分方案的权重，s[i][j]记录剖分该凸多边形的k值。

则:

其中，W(V_i-1,V_kV_j)=W_i-1,k+W_k,j+W_j,i-1为三角形V_i-1V_kV_j的权重，W_i-1,W_k,j,W_j,i-1分别为该三角形三条边的权重。

求解凸多边形的最优剖分方案，即求解最小剖分的权重及对应的三角形集。

C代码

#includestdio.h>

#define N 6//凸多边形规模

int m[N+1][N+1];//m[i][j]表示多边形V_i-1到V_j最优三角剖分的权值

int s[N+1][N+1];//s[i][j]记录多边形V_i-1到V_j最优三角剖分的k 值

int w[N+1][N+1];//凸多边形的权重矩阵，在main函数中输入

/*三角形的权重a,b,c，三角形的顶点下标*/

int get_triangle_weight(int a, int b, int c){

     return W[a][b]+W[b][c]+W[c][a];

}

/*求解最优值*/

void triangle_partition(){

    int i,r,k,j;

    int temp;

    /*初始化*/

    for(i=1;i=N;i++){

        m[i][j]=0;

}

/*自底向上计算m,S*/

for(r=2; ( 1 ); r++){ /*r为子问题规模*/

     for(i=1; K=N-r+1; i++){

        ( 2 )

        m[i][j]=m[i][j] + m[i+1][j] +get_triangle_weight(i-1,i,j);  /*k=j*/

        S[i][j]=i;

        for(k=i+1; k