一、二维矩形排样问题介绍
二维矩形排样问题可以简单理解为：给定一个矩形的材料，需要从上面切割出多个尺寸不同的小矩形，应该如何切割才可以使得材料的利用率最高。
二、方法介绍
小编觉得求解该问题的有以下关键步骤：
1、如何生成小矩形的可放置位置
小编通过实时更新已放小矩形最顶端的红线来生成新的位置，即下图的p1,p2,p3,p4。小编通过链表的方式来存储这些红线，即存储p的x,y坐标和线的长度。
当将一个矩形的左下角放到p4中时，若R4的宽等于l4的长度，或者很接近于l4的长度时（可以用当前所存在小矩形的最小边来判断，若l4的长度减去R4的宽小于最小边，则无需生成线l5），我直接将l4上移到R4顶端;否则，将l4的长等于R4的宽，并生成新的线l5。（注意，这里的小矩形的宽指的是平行于x轴的边的长度）
当选择的位置无法放入任何一个矩形时，我直接将该位置的线直接移动到与相邻两线中较矮的一条线同高的位置，若相邻的线只有一根时，直接移动到高线的高度即可。（注意：移动之后，要将两线合并，生成一根更长的线，即生成一个更宽的位置。）
至于说第一个矩形怎么选择，小编是选择序列的第一个小矩形，这样随着序列的改变，解也会改变。而第一根红线地生成也简单，就是大矩形的最下边。
2、如何从可放置位置中选择一个可放置位置来执行当前的小矩形排布
由于小编的偷懒，便选择了最简单的方式，就是选择y最小的那个位置。
3、如何选择最适合2中所选择的可放置位置的小矩形
这里小编也是选择了最简单的方式，即评分的方式，将每个小矩形放到这个位置中，然后给它打一下分。小编的打分方式为：
(int)((小矩形的宽/位置的长度)*100)/10
对于相同最高分的矩形，小编选择序列中的第一个最高分的矩形。之所以选用上面的打分方式，实际是为了让后面的启发式算法起到更大的作用，否则面对同样的位置，肯定会优先选择宽最接近位置的长度的那个小矩形，这样解的变异能力就变差了。应用小编的方法，即不管是0.96还是0.91，最终的得分都是9分，这样随着序列的变化，解也会相应地变化。当然，这个打分方法只是最简单的一种方式，还有多种方法可以选择。比如一个矩形和空间的匹配度越越高，得分就越高，这样不只是考虑宽，还要考虑高，使用这种打分方法得到的解层与层之间会比较平整。其他的方法小编就不讲了，大家自由去想象。（注意：小矩形是可以旋转的，打分的时候最好旋转一下来打一下分，这样解更好一点）
4、如何更新解
更新解的方法也很简单，只要更新小矩形的序列即可，谈到更新序列这种东西，启发式算法再适合不过，小编使用的是禁忌搜索，当然其他启发式也是完全可以滴，大家可以多用几种方法，然后自己对比一下哈。
三、算法测试
测试所用的数据以及排样效果都在下面了，这个效果显示使用的是JavaFx技术，这个技术最适合用来做算法的验证了，解是否正确，画出图一看便知。
算例1数据： 400 400（大矩形） 59 115 26 99 68 97 41 63 99 116 21 60 79 118 113 85 86 55 33 114 76 70 27 47 117 40 30 46 60 62 87 55 21 108 60 67 82 93 44 49 84 96 89 34 47 34 94 44 117 80 91 62 112 73 37 92 50 48 113 100 24 55 56 27 103 21 61 24 116 111 51 62 67 76 95 57 113 116 63 49 44 56 52 47 33 66 102 53 117 107 40 106 109 27 79 99 40 82 98 96 105 105 94 31 97 78 50 23 86 22 39 59 54 92 37 67 81 102 58 33 113 88 117 71 20 58 65 63 20 116 114 69 117 29 99 88 90 49 35 80 84 87 79 111 97 25 115 21 82 66 79 84 71 38 68 80 57 82 30 73 102 31 68 42 109 106 40 42 24 71 95 101 39 94 100 108 102 26 57 89 108 54 92 107 38 62 38 32 115 46 68 37 106 84 55 73 48 103 107 64
算例2数据： DamRectangle bigRectangle = new DamRectangle(1, 500, 900, 1); List<DamRectangle> smallBigRectangleList = new ArrayList<>(); smallBigRectangleList.add(new DamRectangle(0, 127, 124, 2)); smallBigRectangleList.add(new DamRectangle(1, 131, 234, 1)); smallBigRectangleList.add(new DamRectangle(2, 142, 127, 10)); smallBigRectangleList.add(new DamRectangle(3, 23, 29, 4)); smallBigRectangleList.add(new DamRectangle(4, 43, 27, 2)); smallBigRectangleList.add(new DamRectangle(5, 48, 128, 7)); smallBigRectangleList.add(new DamRectangle(6, 37, 63, 8)); smallBigRectangleList.add(new DamRectangle(7, 45, 40, 6)); smallBigRectangleList.add(new DamRectangle(8, 43, 27, 17)); smallBigRectangleList.add(new DamRectangle(9, 48, 78, 7)); smallBigRectangleList.add(new DamRectangle(10, 37, 35, 4)); smallBigRectangleList.add(new DamRectangle(11, 37, 40, 6)); smallBigRectangleList.add(new DamRectangle(12, 43, 43, 7)); smallBigRectangleList.add(new DamRectangle(13, 48, 27, 16)); smallBigRectangleList.add(new DamRectangle(14, 37, 123, 8)); smallBigRectangleList.add(new DamRectangle(15, 42, 40, 10));
