最大化覆盖范围、最小化项目使用的算法？

Question

我有一个场景，您可以这样设想:

从 100 像素宽 x 1000 像素高的图像开始。除了该图像之外，您还有一组该图像的裁剪部分。每个部分的宽度为 100 像素，高度为 100 像素。该部分中包含的图像部分有所不同。例如，您可能有一个从最顶部(像素 0)开始的一个，然后是垂直像素 3 的一个，然后是垂直像素 9 的一个，依此类推。

我需要做的是找到一种方法来查看那些较小的图片集，并挑选出最少数量的部分，这些部分将给我提供原始图像的最大覆盖范围。

一些注意事项:

1. 图片的内容并不重要。它真正匹配重要的坐标。
2. 重建时图像中永远不会有间隙，但可能没有足够的碎片到达底部。
3. 各部分之间会有很多重叠。事实上，在某些情况下，两个部分之间只会有一个或两个(垂直)像素的差异。

谁能给我指明正确的方向？我可以使用这种蛮力...但我认为有更好的方法。

Answer 1

抱歉，我不明白为什么这个问题是 NP 难的。

一般的想法是，您将通过选择“最佳”部分，即

• 覆盖图片底部的最大部分
• 如果找不到一个(因为没有部分覆盖最后一行像素)，只需选择最靠近底部的那个。
• 冲洗并重复

首先对部分进行排序。您会得到类似于 (0,1,3,10,...,988,999) 的内容，其中 0 对应于从顶部像素开始的部分。 (而999对应的只占一行)

假设您的原始图像是 100xN。最初，N=1000。

设 n 是最能覆盖原始图像末尾的图像的索引:即 n 是该列表中满足 n+100>=N 的最小数字。如果没有这个数字，n 就是最大的数字。

如果您的排序列表是 (0,1,...899, 900, 901,..,999) 那么 n=900

如果您的排序列表是 (0,1,...899, 905, 910,..,999) 那么 n=905

如果你的排序列表是 (0,1,...,888,898,) 那么 n=898

然后重新开始 N=n(你已经删除了原始图像底部的一部分)(当然，从排序列表中删除所有“>=n”的部分)

我认为设置固定高度的部分(100 像素)可以消除 NP 硬度。