把第 i 个长方形放下时,只需在两种朝向里选一种:
限制是高度 ≤m。显然每个长方形彼此独立,总长度就是各自选择后的宽度之和,因此问题可分解为对每个 i 局部做最优选择。
对单个长方形的最优宽度 wi:
小美有 n 个长方形,第 i 个长方形的两条边长分别为 xi,yi ;
小美拥有一个仅包含第一象限的平面直角坐标系;
小美希望将这 n 个长方形按顺序(可以旋转)放置在 x 轴上,不允许重叠,并且每个长方形放置后的高度不超过 m ,保证 max(min(xi,yi))≦m ;