Это небольшая аккуратная задача, спасибо за сообщение! В остальном я предполагаю, что ни одна точка не является преобладающей , то есть нет точек c, таких, что существует точка d с c.x < d.x и c.y < d.y. Если да, то использование c никогда не является оптимальным (почему?), Поэтому мы можем спокойно игнорировать любые доминирующие точки. Ни один из ваших примеров не является доминирующим.
Ваша проблема демонстрирует оптимальную подструктуру: как только мы решили, какой элемент должен быть включен в первую итерацию, у нас снова возникнет та же проблема с k - 1 и n - 1 (удаляем выбранный элемент из набора допустимых точек). Конечно, отдача зависит от выбранного набора - мы не хотим пересчитывать площади дважды.
Я предлагаю предварительно отсортировать все точки по их значению x в порядке возрастания. Это гарантирует, что значение выбранных точек может быть вычислено как кусочно-размерные области. Я проиллюстрирую это на примере: предположим, у нас есть три точки (x1, y1), ..., (x3, y3) со значениями (2, 3), (3, 1), (4, .5). Тогда общая площадь, покрытая этими точками, составит (4 - 3) * .5 + (3 - 2) * 1 + (2 - 0) * 3. Надеюсь, это имеет смысл на графике:
По нашему предположению, что нет доминирующих точек, у нас всегда будет такая слабо убывающая цифра. Таким образом, предварительная сортировка решает всю проблему «подсчета площадей дважды»!
Давайте превратим это в алгоритм динамического c программирования. Рассмотрим набор n точек, помеченных {p_1, p_2, ..., p_n}. Пусть d[k][m] будет максимальной площадью подмножества размером k + 1, где (k + 1) -я точка в подмножестве - это точка p_m. Ясно, что m не может быть выбрано в качестве (k + 1) -й точки, если m < k + 1, поскольку тогда у нас будет подмножество размером меньше k + 1, что никогда не является оптимальным. У нас есть следующая рекурсия:
d[k][m] = max {d[k - 1][l] + (p_m.x - p_l.x) * p_m.y, for all k <= l < m}.
Начальные случаи, когда k = 1 - это прямоугольные angular области каждой точки. Для решения проблемы достаточно начальных случаев вместе с уравнением обновления. Я оцениваю следующий код как O(n^2 * k). Термин, возведенный в квадрат в n, вероятно, также можно уменьшить, поскольку у нас есть упорядоченная коллекция и, возможно, мы сможем применить двоичный поиск, чтобы найти лучшее подмножество за log n время, уменьшив n^2 до n log n. Я оставляю это вам.
В коде я повторно использовал мои обозначения выше, где это возможно. Это немного кратко, но, надеюсь, понятно с приведенным объяснением.
#include <stdio.h>
typedef struct point
{
double x;
double y;
} point_t;
double maxAreaSubset(point_t const *points, size_t numPoints, size_t subsetSize)
{
// This should probably be heap allocated in your program.
double d[subsetSize][numPoints];
for (size_t m = 0; m != numPoints; ++m)
d[0][m] = points[m].x * points[m].y;
for (size_t k = 1; k != subsetSize; ++k)
for (size_t m = k; m != numPoints; ++m)
for (size_t l = k - 1; l != m; ++l)
{
point_t const curr = points[m];
point_t const prev = points[l];
double const area = d[k - 1][l] + (curr.x - prev.x) * curr.y;
if (area > d[k][m]) // is a better subset
d[k][m] = area;
}
// The maximum area subset is now one of the subsets on the last row.
double result = 0.;
for (size_t m = subsetSize; m != numPoints; ++m)
if (d[subsetSize - 1][m] > result)
result = d[subsetSize - 1][m];
return result;
}
int main()
{
// I assume these are entered in sorted order, as explained in the answer.
point_t const points[5] = {
{0.029394902328, 0.951299438575},
{0.176318878234, 0.493630156084},
{0.235041868262, 0.438197791997},
{0.376508963445, 0.437693410334},
{0.948798695015, 0.352125307881},
};
printf("%f\n", maxAreaSubset(points, 5, 3));
}
Используя данные примера, которые вы предоставили, я нахожу оптимальный результат 0.381411, что и нужно.