#include?
using?namespace?std;

const?int?N?=?7;//凸多邊形邊數+1
int?weight[][N]?=?{{022355}{201523}{210224}{352062}{121601}{434210}};//凸多邊形的權

int?MinWeightTriangulation（int?nint?**tint?**s）;
void?Traceback（int?iint?jint?**s）;//構造最優解
int?Weight（int?aint?bint?c）;//權函數

int?main（）
{
	int?**s?=?new?int?*[N];
????int?**t?=?new?int?*[N];
????for（int?i=0;i????{
????????s[i]?=?new?int[N];
????????t[i]?=?new?int[N];
????}
????cout<<“此多邊形的最優三角剖分值為：“<????cout<<“最優三角剖分結構為：“<????Traceback（15s）;?//s[i][j]記錄了Vi-1和Vj構成三角形的第3個頂點的位置

????return?0;
}

int?MinWeightTriangulation（int?nint?**tint?**s）
{
????for（int?i=1;?i<=n;?i++）
????{
????????t[i][i]?=?0;
????}
????for（int?r=2;?r<=n;?r++）?//r為當前計算的鏈長（子問題規模）
????{
????????for（int?i=1;?i<=n-r+1;?i++）//n-r+1為最后一個r鏈的前邊界
????????{
????????????int?j?=?i+r-1;//計算前邊界為r，鏈長為r的鏈的后邊界

????????????t[i][j]?=?t[i+1][j]?+?Weight（i-1ij）;//將鏈ij劃分為A（i）?*?（?A[i+1:j]?）這里實際上就是k=i

????????????s[i][j]?=?i;

????????????for（int?k=i+1;?k????????????{
????????????????//將鏈ij劃分為（?A[i:k]?）*?（A[k+1:j]）
????????????????int?u?=?t[i][k]?+?t[k+1][j]?+?Weight（i-1kj）;
????????????????if（u????????????????{
????????????????????t[i][j]?=?u;
????????????????????s[i][j]?=?k;
????????????????}
????????????}
????????}
????}
????return?t[1][N-2];
}

void?Traceback（int?iint?jint?**s）
{
????if（i==j）?return;
????Traceback（is[i][j]s）;
????Traceback（s[i][j]+1js）;
????cout<<“三角剖分頂點：V“<}

int?Weight（int?aint?bint?c）
{
?????return?weight[a][b]?+?weight[b][c]?+?weight[a][c];
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2016-12-05?18:42??2014061523王延康\
?????目錄???????????0??2016-12-05?13:22??2014061523王延康\C++\
?????目錄???????????0??2016-12-05?18:26??2014061523王延康\C++\凸多邊形最優三角剖分\
?????文件????????1848??2016-12-05?14:07??2014061523王延康\C++\凸多邊形最優三角剖分\TheOptimalTriangulation.cpp
?????文件?????1048872??2016-12-05?18:26??2014061523王延康\C++\凸多邊形最優三角剖分\TheOptimalTriangulation.exe
?????文件????????3199??2016-12-05?18:26??2014061523王延康\C++\凸多邊形最優三角剖分\TheOptimalTriangulation.o
?????目錄???????????0??2016-12-05?18:24??2014061523王延康\C++\哈夫曼編碼\
?????文件????????2477??2016-12-05?14:07??2014061523王延康\C++\哈夫曼編碼\HuffmanEncoding.c
?????文件???????29724??2016-12-05?18:24??2014061523王延康\C++\哈夫曼編碼\HuffmanEncoding.exe
?????文件????????2027??2016-12-05?18:24??2014061523王延康\C++\哈夫曼編碼\HuffmanEncoding.o
?????文件?????????661??2016-04-24?19:33??2014061523王延康\C++\哈夫曼編碼\base1.h
?????文件?????????251??2002-05-29?14:13??2014061523王延康\C++\哈夫曼編碼\base2.h
?????文件????????1880??2016-12-05?14:11??2014061523王延康\ReadMe.txt
?????目錄???????????0??2016-12-05?13:22??2014061523王延康\java\
?????目錄???????????0??2016-12-05?13:16??2014061523王延康\java\ALGO_LAB_2014061523\
?????文件?????????303??2016-12-05?10:45??2014061523王延康\java\ALGO_LAB_2014061523\.classpath
?????文件?????????395??2016-12-05?10:45??2014061523王延康\java\ALGO_LAB_2014061523\.project
?????目錄???????????0??2016-12-05?13:16??2014061523王延康\java\ALGO_LAB_2014061523\.settings\
?????文件??????????97??2016-12-05?12:52??2014061523王延康\java\ALGO_LAB_2014061523\.settings\org.eclipse.core.resources.prefs
?????文件?????????603??2016-12-05?10:45??2014061523王延康\java\ALGO_LAB_2014061523\.settings\org.eclipse.jdt.core.prefs
?????目錄???????????0??2016-12-05?13:16??2014061523王延康\java\ALGO_LAB_2014061523\bin\
?????目錄???????????0??2016-12-05?13:16??2014061523王延康\java\ALGO_LAB_2014061523\bin\algo_lab_code\
?????文件????????1927??2016-12-05?11:25??2014061523王延康\java\ALGO_LAB_2014061523\bin\algo_lab_code\ActivityArrangementProblem.class
?????文件????????3680??2016-12-05?12:51??2014061523王延康\java\ALGO_LAB_2014061523\bin\algo_lab_code\BBKnapsack.class
?????文件?????????433??2016-12-05?12:51??2014061523王延康\java\ALGO_LAB_2014061523\bin\algo_lab_code\BBnode.class
?????文件????????1058??2016-12-05?10:57??2014061523王延康\java\ALGO_LAB_2014061523\bin\algo_lab_code\BinarySearch.class
?????文件?????????738??2016-12-05?12:51??2014061523王延康\java\ALGO_LAB_2014061523\bin\algo_lab_code\Element.class
?????文件?????????845??2016-12-05?12:51??2014061523王延康\java\ALGO_LAB_2014061523\bin\algo_lab_code\HeapNode.class
?????文件?????????298??2016-12-05?13:11??2014061523王延康\java\ALGO_LAB_2014061523\bin\algo_lab_code\HuffmanEncoding.class
?????文件?????????941??2016-12-05?11:35??2014061523王延康\java\ALGO_LAB_2014061523\bin\algo_lab_code\Knapsack$Element.class
?????文件????????3309??2016-12-05?11:35??2014061523王延康\java\ALGO_LAB_2014061523\bin\algo_lab_code\Knapsack.class
............此處省略46個文件信息