Vik*_*h B 5 algorithm geometry
我试图解决 topcoder 领域的练习问题：http://topcoder.bgcoder.com/print.php ?id=417
根据我的理解，问题的目的是找到一个最大面积的 k 边形，给定一组点 D 并且 k<=n，n 是一个固定值。
令 D 的凸包 = C(D)
如果n=3，我已经证明可以通过假设它的顶点是C(D)的子集来构造这样的三角形。因此很容易找到 k=3 的解决方案：/sf/answers/113533941/
但是，对于 n>3，我不知道该怎么做。
这是我尝试的方法：
设|C(D)| = l 即凸包是一个 l 边形，
如果 n > li 我非常确定面积最大的 k 边形将是凸包本身，即 C(D)
如果 n < li 非常确定最大 k 边形的顶点将是 C(D) 的子集，我无法证明 k>3，而且我无法想出一种算法来解决甚至如果这是一个正确的假设。
谁能帮我解决这个问题，我的方法正确吗？你能帮我进一步进行吗？
经过几个小时的绞尽脑汁后，我找到了解决方案。
这是一个动态规划问题：
令 dp[m][o][r] 表示最大面积 r-gon，使得起始顶点为 m，结束顶点为 o（按循环顺序获取的顶点）。
那么递归关系将是：
dp[m][o][r] = max(dp[m][n][r-1] + 面积(m,n,o)), {所有 n 的最大值：m < n < o}
其中area(m,n,o)是由顶点m、n和o形成的三角形的面积
| 归档时间： |
|
| 查看次数： |
836 次 |
| 最近记录： |