我面临以下问题:
给定
目标:
注意:
我正在寻找最佳作业。
我的问题:
(我可能会提起我尝试过的方法。由于我正在寻找最佳分配,因此我的启发式想法并不真正相关。目前,我还不知道如何找到最佳分配)。
最佳答案
这是加权maximum coverage problem的几何特例。一般的MCP是NP难的,我怀疑这种特殊情况也是如此,尽管与一般情况不同,它可能具有有效的多项式时间近似方案。但是,您需要一个最佳解决方案,因此,我建议的第一件事是将链接的Wikipedia文章中的整数线性编程公式提供给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
的权重j
,并且集合S_i
都可以覆盖L
正方形宽度的点。 x_i
的含义是是否选择设置S_i
。 y_j
的含义是是否覆盖点j
。构造S_i
s的最简单三次算法是枚举其左下顶点的x坐标等于某个点的坐标,而y坐标等于某个(可能是其他)点的坐标的正方形,因为每个其他正方形都可以向上滑动并/或在不牺牲覆盖率的情况下向右移动。关于algorithm - 给定平面上的加权点,找到U形的位置,以使封闭的总重量最大,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/18460126/