寻找最大面积的k个子集中的n个。

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。那么我是否缺少了一个点？

- Michael.leaves77

---

我相信这只是我的问题，但当你写下“[...]它是这些点的面积之和减去它们之间的公共区域”时，我不太明白你的意思。一般来说，一个点并没有面积。如果你能用一个简单的示例图形为我绘制出来，我相信这个问题会立刻变得更加清晰！ - Nelewout

@N.Wouda 我能理解这可能会让人感到困惑，我没有解释得很清楚。 我添加了一张图以便澄清，并更新了我的意思。 - Michael.leaves77

@FelixG 因为即使我们有4个点（n），我们仍然只能使用k个点来找到最大面积。在这种情况下，k是2。 - Michael.leaves77

@Michael.leaves77 好的，明白了。所以你需要找到能够产生最大值的 k 个区域的组合。 - Felix G

@WeatherVane 是的，这正是我的描述所实现的。 - Tom Karzes

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。希望在图中能够理解。

根据我们假设没有被支配的点，我们总是会有这样一个弱下降的图形。因此，预排序解决了“计算两次区域”的整个问题！

让我们将其转化为动态规划算法。考虑一个由标记为{p_1，p_2，...，p_n}的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` 时，每个点的矩形区域。初始情况和更新方程式足以解决问题。我估计以下代码的时间复杂度为 `O(n^2 * k)`。在有序集合中应用二分查找可以在 `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。

- Nelewout

---

我本不想说什么，因为你已经做了很多，但是我现在很难正确理解这个问题。我想重新翻开一本 Python 书。 - Michael.leaves77

@Michael.leaves77 我明天可能会发布C实现，不应该太难。递归是重要的部分，我相信这些都是正确的。希望你能根据我给出的说明自己实现。 - Nelewout

我不明白为什么我们需要如此复杂的面积计算。我认为我的例程符合 OP 的意图，并且每次迭代都可以在 O(1) 中计算出面积，无需缓存。O(n^2 * k) 的朴素实现。 - גלעד ברקן

@גלעדברקן 好的，说得好！我一直在追踪子集，但那比所需的更复杂。现在我已经更新为只跟踪区域表格，这样就不需要重新计算了。谢谢！ - Nelewout

Answer 2

据我所知，您和我都使用相同的方法来计算面积，以及整体概念，但我的代码似乎返回了正确的结果。也许审查它可以帮助您找到差异。

JavaScript 代码：

function f(pts, k){
  // Sort the points by x
  pts.sort(([a1, b1], [a2, b2]) => a1 - a2);

  const n = pts.length;
  let best = 0;
  
  // m[k][j] represents the optimal
  // value if the jth point is chosen
  // as rightmost for k points
  let m = new Array(k + 1);
  
  // Initialise m
  for (let i=1; i<=k; i++)
    m[i] = new Array(n);
  for (let i=0; i<n; i++)
    m[1][i] = pts[i][0] * pts[i][1];
    
  // Build the table
  for (let i=2; i<=k; i++){
    for (let j=i-1; j<n; j++){
      m[i][j] = 0;
      for (let jj=j-1; jj>=i-2; jj--){
        const area = (pts[j][0] - pts[jj][0]) * pts[j][1];
        m[i][j] = Math.max(m[i][j], area + m[i-1][jj]);
      }
      best = Math.max(best, m[i][j]);
    }
  }

  return best;
}

var pts = [
  [0.376508963445, 0.437693410334],
  [0.948798695015, 0.352125307881],
  [0.176318878234, 0.493630156084],
  [0.029394902328, 0.951299438575],
  [0.235041868262, 0.438197791997]
];

var k = 3;

console.log(f(pts, k));

- גלעד ברקן