我有一个你可以想象的场景:
从100像素宽,1000像素高的图像开始.除了该图像,您还有一组该图像的裁剪部分.每个部分宽100像素,高100像素.该部分中包含的图像部分各不相同.例如,您可能有一个从最顶部(像素0)开始,然后一个在垂直像素3处开始,然后一个在垂直像素9处开始,依此类推.
我需要做的是找到一种方法来查看那些较小的图片集,并选出最小数量的部分,这些部分可以让我覆盖原始图像.
几个笔记:
任何人都能指出我在正确的方向吗？我可以做这种蛮力......但我认为有更好的方法.
抱歉，我不明白为什么这个问题是 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 硬度。