从具有最大面积的 n 个子集中找出 k 个

Question

我有点n，必须找到k点 ( k <= n)之间的最大联合面积。所以，它是这些点面积的总和减去它们之间的公共面积。

] 1

假设我们有n=4, k=2。如上图所示，面积是从每个点到原点计算的，最终面积是 B 面积与 D 面积之和（只计算它们相交的面积一次）。没有一点被支配

我已经实现了一个自底向上的动态编程算法，但它在某处有错误。这是打印出最佳结果的代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct point {
    double x, y;
} point;
struct point *point_ptr;

int n, k;
point points_array[1201];
point result_points[1201];

void qsort(void *base, size_t nitems, size_t size,
           int (*compar)(const void *, const void *));

int cmpfunc(const void *a, const void *b) {
    point *order_a = (point *)a;
    point *order_b = (point *)b;
    if (order_a->x > order_b->x) {
        return 1;
    }
    return -1;
}

double max(double a, double b) {
    if (a > b) {
        return a;
    }
    return b;
}

double getSingleArea(point p) {
    return p.x * p.y;
}

double getCommonAreaX(point biggest_x, point new_point) {
    double new_x;
    new_x = new_point.x - biggest_x.x;
    return new_x * new_point.y;
}

double algo() {
    double T[k][n], value;
    int i, j, d;
    for (i = 0; i < n; i++) {
        T[0][i] = getSingleArea(points_array[i]);
    }
    for (j = 0; j < k; j++) {
        T[j][0] = getSingleArea(points_array[0]);
    }
    for (i = 1; i < k; i++) {
        for (j = 1; j < n; j++) {
            for (d = 0; d < j; d++) {
                value = getCommonAreaX(points_array[j - 1], points_array[j]);
                T[i][j] = max(T[i - 1][j], value + T[i - 1][d]);
            }
        }
    }
    return T[k - 1][n - 1];
}

void read_input() {
    int i;
    fscanf(stdin, "%d %d\n", &n, &k);
    for (i = 0; i < n; i++) {
        fscanf(stdin, "%lf %lf\n", &points_array[i].x, &points_array[i].y);
    }
}

int main() {
    read_input();
    qsort(points_array, n, sizeof(point), cmpfunc);
    printf("%.12lf\n", algo());
    return 0;
}

输入：

5 3
0.376508963445 0.437693410334
0.948798695015 0.352125307881
0.176318878234 0.493630156084
0.029394902328 0.951299438575
0.235041868262 0.438197791997

其中第一个数字等于n，第二个k和以下几行分别是每个点的x和y坐标，结果应该是：0.381410589193,

而我的是0.366431740966. 所以我错过了一点？

Answer 1

这是一个巧妙的小问题，感谢您的发帖！在剩下的部分中，我将假设没有点被支配，也就是说，不存在任何点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。我希望它在图表中有意义：

根据我们假设不存在支配点的情况，我们将始终得到这样一个弱递减的数字。因此，预排序解决了“两次计算区域”的整个问题！

让我们把它变成动态规划算法。考虑一组n标记为 的点{p_1, p_2, ..., p_n}。设d[k][m]为大小子集的最大面积，k + 1其中子(k + 1)集中的第 - 个点为点p_m。显然，如果m不能选择作为(k + 1)第 -th 点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是每个点的矩形区域。初始情况和更新方程足以解决问题。我估计以下代码为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根据需要找到了 的最佳结果。