在平面上给定带权点，找到U个正方形的位置，使得总权重尽可能大。

Question

我面临以下问题：

给定： - 在欧几里得平面上一组点集，每个点P(x,y,w)都有坐标和一个相关的正权重。 - 一组 U 个正方形，它们都有相同的边长L。

目标： - 分配（找到位置），使得所有正方形内包含的点的总权重最大化。

注意： - 正方形应该是轴对齐的。 - 正方形可以重叠，但被包含的权重不会被多次计算。

我正在寻找最优分配。

我的问题： - 这是一个已知的问题吗？（它有名字吗？之前有没有研究过？） - 有什么想法来解决它吗？

（我可能需要提到我尝试了什么。由于我正在寻找最优分配，我的启发式想法并不是很相关。此时我不知道如何找到最优分配。）

- Lior Kogan

---

请澄清您对U平方的定义。并且通过所有正方形的封闭，您并不是指这些点应该在正方形的平面内，而是包含在一些盒子的集合中，每个边都由这些轴平行的正方形构成，或与其他这样的盒子相交？ - Robert Jørgensgaard Engdahl

@RobertJørgensgaardEngdahl：U是我想要找到最佳位置的等尺寸正方形的数量。这些正方形与点在同一平面上（这是一个二维问题）。 - Lior Kogan

你能否添加一个二维程序预期执行的图像吗？ - jambono

@HighPerformanceMark：权重在区间（0，1]内，并属于有限集合（约20个值）。 - Lior Kogan

Answer 1

这是加权最大覆盖问题的几何特殊情况。一般的最大覆盖问题是NP难的，而我猜测这个特殊情况也是，尽管不同于一般情况的是，它可能有一个高效的多项式时间近似方案。然而，如果您想要最优解，我建议将链接维基百科文章中的整数线性规划公式输入LP求解器中。

maximize sum_j (w_j * y_j)
subject to
for all i, sum_i x_i <= U
for all j, sum_{i : j in S_i} x_i - y_j >= 0
for all i, x_i in {0, 1}
for all j, 0 <= y_j <= 1

每个点的权重w_j已给出，集合S_i是用宽度为L的正方形覆盖点的所有可能性。x_i的含义是是否选择集合S_i。y_j的含义是点j是否被覆盖。构建S_i的最简单的立方体算法是枚举所有正方形，其左下顶点的x坐标等于某些点的x坐标，y坐标等于某些（可能是其他）点的y坐标，因为每个其他正方形都可以向上或向右滑动而不损失覆盖面积。

- David Eisenstat

---

谢谢David。你有没有偶然间提到构建S_i的更详细描述方法的参考资料？（使用哪些数据结构等） - Lior Kogan

@LiorKogan 我手头没有参考资料，因为我刚想到这个算法。稍微详细一点，该算法是收集和排序点的x坐标，收集和排序点的y坐标，对于x坐标中的x，在y坐标中的y，扫描其他点以查看哪些属于宽度为L的正方形，其左侧具有x坐标x，底部具有y坐标y。我怀疑在这里使用数据结构会适得其反，因为解决整数程序需要一段时间。 - David Eisenstat