基于给定矩形集构建目标近似矩形的Ruby算法优化需求

问题明确 #

给定目标尺寸sizeX、sizeY，以及一组不可旋转、可重复使用的矩形（每个矩形为[宽度, 高度]格式），需要组合出矩形rectX×rectY，满足两个核心优先级：

1. 总差值abs(sizeX - rectX) + abs(sizeY - rectY)最小
2. 差值相同时，使用的矩形数量最少

示例输入：sizeX=130，sizeY=240，rectangles=[[100,100],[100,150],[50,100],[50,50]]

核心优化方向 #

1. 收缩搜索范围，优先找最优解 #

• 先锁定最小差值边界：从差值0开始向上枚举，一旦找到存在可行组合的差值，就只在该差值范围内寻找最少矩形数的解，避免无意义的大范围搜索。
• 预生成维度候选值：对X、Y两个维度，分别用动态规划生成所有可组合出的尺寸，上限设为目标尺寸 + 最大矩形边长（避免无限生成），比如X维度的候选值包括所有矩形宽度的正整数倍、以及不同矩形宽度的和（拼接后的总宽度）。

2. 剪枝与优先搜索策略 #

• 用BFS替代DFS：优先搜索使用矩形数量少的组合，从1个矩形开始尝试，一旦找到满足最小差值的组合，直接返回结果，无需继续搜索更多矩形的情况。
• 跳过重复状态：用哈希表记录已处理过的[当前宽度, 当前高度, 已用矩形数]状态，若后续遇到相同尺寸但矩形数更多的状态，直接跳过。
• 提前终止无效分支：如果当前组合的总差值已经大于当前找到的最小差值，或者已用矩形数超过当前最优解的数量，直接剪枝该分支。

3. 动态规划（DP）实现方案 #

用哈希表存储DP状态，dp[[w, h]]表示凑出w×h矩形所需的最少矩形数，初始化所有值为无穷大：

• 初始状态：对每个矩形[rw, rh]，设置dp[[rw, rh]] = 1；同时对其倍数尺寸（如k*rw × rh、rw × k*rh，k≥2），直接设置dp[[k*rw, rh]] = k、dp[[rw, k*rh]] = k。
• 状态转移：对每个已有的w1×h1和w2×h2，生成两种拼接后的尺寸：
  • 横向拼接：(w1+w2) × max(h1, h2)，更新dp[[w1+w2, max(h1,h2)]]为min(当前值, dp[[w1,h1]] + dp[[w2,h2]])
  • 纵向拼接：max(w1, w2) × (h1+h2)，同理更新对应DP值
• 结果提取：遍历所有w,h组合，计算总差值，筛选出差值最小且dp[[w,h]]最小的解。

4. 预处理筛选有效矩形 #

• 剔除冗余矩形：如果存在矩形A[rw1, rh1]和矩形B[rw2, rh2]，满足rw2 ≥ rw1且rh2 ≥ rh1，则矩形A可以直接排除——用B能更快凑出目标尺寸，且数量更少。
• 优先候选矩形：针对目标尺寸，优先保留接近sizeX或sizeY的矩形，减少初始差值。

5. Ruby代码结构优化 #

• 用哈希表替代二维数组存储DP状态，节省空间（大部分尺寸无法凑出，无需占用内存）。
• 预先生成所有单矩形的倍数尺寸，避免重复计算。
• BFS时用队列存储待处理状态，每个状态包含[当前宽度, 当前高度, 已用矩形数]，每次出队处理时生成新的拼接状态。

示例输入的最优解参考 #

针对sizeX=130、sizeY=240，最优组合为：
用[100,150]和[100,100]纵向拼接，得到100×250，总差值abs(130-100)+abs(240-250)=40，仅使用2个矩形。

内容的提问来源于stack exchange，提问作者Esteban Vernet