图形最优化............绝对实用技术

关于切裁率的问题.
    材料是长、宽分别为X、Y的长方形
    产品是长、宽分别为x、y的长方形

   一般一片长方形的材料可以切割成几片同种大小的产品。
   现在有多种材料，领导让我设计一个算法，计算切割同种产品哪种材料的切裁率最高，并能切割几片。
   (如果一片面积为S材料可以切割N片面积为s的产品
    切裁率 = N*s/S*100%  )

我举个例子:
    假如现在有一个(宽)1800mm*(长)2600mm的矩形玻璃,现在要裁成(宽)400mm*(长)500mm的小矩形,那么怎么裁,才可以裁出最多.(由于不能添加图形，我就只能这样画个简图)

A:       |----------------------|   B: 　　|---------|
          |                      |    400mm |         |
    1800mm|                      |        ↑|---------|
          |                      |          → 500mm
          |                      |
       ↑ |----------------------|
      →      2600mm
(1)  如果我们将B图在A图上全部水平方向切割，那么最多能切割20片
(2)  如果我们将B图在A图上全部垂直方向切割，那么最多能切割18片
(3)  如果我们将B图在A图上三行水平方向切割一行垂直方向切割，那么最多能切割21片
(4)  如果我们将B图在A图上两行水平方向切割两行垂直方向切割，那么最多能切割22片
.
.
.
.
.

问题就是，如何通过一个最优化的算法找出这个大值(最多切出的片数)

9 个解决方案

#1

如果要切成不规则形状，就头大了。

现在不流行这个了，你看那木材，本身的材质不好，粉粹了加点胶水再做成复合板。

#2

用google搜了一下，发现这是个很大的题目，可以写论文了

#3

二维集装箱问题，也是NPC问题。
可以用google搜索一下看看 2d bin-packing

#4

二维装箱问题，NPC。
考虑一下近似最优解法吧。

#5

npc问题解法太繁了吧，先想一个近似最优，全当抛砖引玉
长方形无非横着放和竖着放两种方法。可以认为，同样方法放置的相邻长方形紧靠在一起是最省空间的方法。这样就有四种“条”：横放的长方形竖着累起来的竖条（hv)横放的长方形横着累起来的横条（hh)竖放的长方形竖着累起来的竖条（vv)竖放的长方形横着累起来的横条（vh），而相邻的两个相同类型的条也要紧靠在一起且长度相同才最节省，所以就会有两种块：横放的长方体堆成的块和竖放的长方体堆成的块。又可以认为，同一行上相同高度的两个块如果不相邻并不比他们相邻所占的面积少，所以可以把整个材料板子分为4块，左上是A块，有AW*AH个横放的长方形，右上是B块，有BW*BH个竖放的长方形，左下是C块，有CW*CH个竖放的长方形，右下是D块，有DW*DH个横放的长方形。
这样就有 X-y<AW*x+BW*y<X; X-y<CW*y+CW*x<X; Y-y<AH*y+CH*x<Y;Y-y<BH*x+DH*y<Y;
如果知道AW，AH，BH三个变量，其它变量都可以推出，因此我们只要穷举AW，AH，BH三个变量的可能情况。就可以得到最优解。
以上只是个个人想法，还有更好的方法吗？

#6

式子写错了，
X-y<AW*x+BW*y<X; X-y<CW*y+DW*x<X; Y-y<AH*y+CH*x<Y;Y-y<BH*x+DH*y<Y;
(AW*x+DW*x<X)||(AH*y+DH*y<Y); (CW*y+BW*y<X)||(CH*x+BH*x<Y );

#7

ahjoe(强哥)
现在都流行把羊皮整张粉碎了，加点胶水，再做成皮鞋

#8

二维装箱问题高级程序员考试教材最后一章算法里有

#9

该问题的求的是：
    当AW、AH、BW、BH、CW、CH、DW、DH取何值时，
    Q = AW*AH + BW*BH + CW*CH + DW*DH最大。

运用例子中的数据代入验证(半个萝卜密fixphy1985(半个菠萝蜜)):
   1) 22 =< 5*AW + 4*BW =< 26
   2) 22 =< 4*CW + 5*DW =< 26
   3) 14 =< 4*AH + 5*CH =< 18
   4) 14 =< 5*BH + 4*DH =< 18
   5) AW + DW < 26/5
   6) AH + DH < 9/2
   7) CW + BW < 13/2
   8) CH + BH < 18/5
解：
   由5)　(推出)→AW < 5.2  DW < 5.2
     6)  →AH < 4.5  DH < 4.5
     7)  →BW < 9.5  CW < 9.5
     8)  →CH < 3.6  BH < 3.6

  　⑴因为：5*AW + 4*BW =22、23、24、25、26   &&　AW < 5.2 && BW < 9.5
      所以：AW = 5 && BW = 0 || AW = 4 && BW = 1 || AW = 3 && BW = 2 ||
            AW = 2 && BW = 3、4 || AW = 1 && BW = 5 || AW = 0 && BW = 6
      → BW =< 6
    .
    .
    .
    .
    .
    .
    假设：1. AW = 5 → BW = 0 && DW = 0
          2. AH = 4 → DH = 0 && CH = 0

       MAX Q = 20

          3. AW = 5 → BW = 0 && DW = 0
          4. AH = 3 → CH = 1 && DH = 0、1、2
       MAX Q = 21
    　　　.
　　　　　.　　　　　　　　
　　　　　.
          .
          .
          .
    如此可以穷举验证.........
    不过这个方法很难用代码来实现，求更佳方法
　
　　Hylas(羽心)能将高级程序员考试教材最后一章的二维装箱算法发给我吗，谢谢！
     yys_16231033@163.com

#1