求一个排列算法,或者解决的思路!若干矩形拼凑成一个矩形,不能重叠,如何排列可以使最终面积最小?使用场景假设,有若干图片,40-100图片数量不一定每个图片的大小尺寸可能不相同,图片排列

Question

求一个排列算法,或者解决的思路!若干矩形拼凑成一个矩形,不能重叠,如何排列可以使最终面积最小?
使用场景假设,
有若干图片,40-100图片 数量不一定
每个图片的大小尺寸可能不相同 ,
图片排列行数列数不限制,但是不能重复;
如何取得最终合成的图片的矩形面积是最小面积的 排列方法;
希望提供数学上的解题思路或者实现过程,
对了 参与排列的矩形 不用考虑旋转的情形,假设矩形或者图片 可以移动 但是无法旋转

Answer 1

1. 计算宽度之和、高度之和,如果宽度和较大则先处理2.1,否则先处理2.2
2.1. 按照宽度从小到大排列,宽度相同的矩形拼成更大的矩形
2.2. 按照高度做相同的处理
3. 重复以上步骤,直到没有宽、高相同的矩形
1. 计算宽度之和、高度之和,如果宽度和较大则先处理2.1,否则先处理2.2
2.1. 按照宽度从小到大排列,找出两个矩形,使得拼接后的“矩形”面积中空缺部分最小（较可能是宽度相差较小的两个矩形）.
2.2. 按照高度做相同的处理
3. 重复以上步骤,直到只剩下一个矩形（最终解）
以上两段其实是一个意思：尽量用较小的“面积损失”最大限度的减少待处理矩形数.只是第一段是特例,也就是无“面积损失”的拼接.
不过,一般来说,这不会是最优解.