＋设为首页 ＋添加到收藏夹
玻璃店里给用户划玻璃的时候一般要遵循以下原则：
1、每一块玻璃母板的大小是一样的，
2、根据用户提供的尺寸，从母板上划下所需的玻璃
3、特殊的是：用玻璃刀划玻璃时，必须要一划到底，中间不能停，更不能拐弯，也就是说肯定划下来的都是矩形玻璃
请问：如果已知母板大小和用户所需玻璃的大小和数量如何划最省料？
多谢了！！！
按你那么描述，用户需要的玻璃最初应该是矩形的，那么这个问题就成了大矩形套小矩形问题了。
可以用一种逐步累加的方法，即先确定第一块玻璃， 然后在此基础上不断的增加其他块，，直到所有的小玻璃块都得到满足，在这里应该用广度搜索算法求最优解
我写了一个，不过卖了。还有一个塑钢、铝合金型材的切割下料的优化程序，也卖了。
一个塑钢行业的软件，没有免费下的！
程序分成两部分：排列组合，使用单纯型处理数据，最后校验数据，然后补齐数据。
排列组合我那个时候没有研究GA的问题，纯粹完全穷举，如果需要切割的玻璃有一块特别小，就不要指望几个小时可以出结果了！
一般情况1小时之内，可以出结果。
用动态规划
参考下面这本书P486,元件折叠问题
书名: 数据结构算法与应用-C++语言描述
原书名: Data Structures, Algorithms, and Applications in C++
原出版社 Mcgraw-Hill
作者: Sartej Sahni
译者: 汪诗林等
书号: 7-111-07645-1
页码: 536
定价: ￥49.00
丛书名 计算机科学丛书
出版社: 机械工业出版社
出版日期: 2000-1-1
原文如下
15.2.6 元件折叠
在设计电路的过程中，工程师们会采取多种不同的设计风格。其中的两种为位－片设计和标准单元设计。在前一种方法中，电路首先被设计为
一个元件栈。每个元件Ci 宽为wi ，高为hi ，而元件宽度用片数来表示。线路是按片来连接各元件的，即连线可能连接元件Ci 的第j片到
元件Ci+1 的第j 片。如果某些元件的宽度不足j 片，则这些元件之间不存在片j 的连线。当图1 5 -
10a 的位－片设计作为某一大系统的一部分时，则在V L SI ( Very Large Scale Integrated) 芯片上为
它分配一定数量的空间单元。分配是按空间宽度或高度的限制来完成的。现在的问题便是如何
将元件栈折叠到分配空间中去，以便尽量减小未受限制的尺度。由于其他尺度不变，因此缩小一个尺度等价于缩小面积。
可用折线方式来折叠元件栈，在每一折叠点，元件旋转1 8 0°。在图15-10b 的例子中，一
个1 2元件的栈折叠成四个垂直栈，折叠点为C6 , C9 和C1 0。折叠栈的宽度是宽度最大的元件所需
的片数。在图15-10b 中，栈宽各为4，3，2和4。折叠栈的高度等于各栈所有元件高度之和的
最大值。在图15-10b 中栈1的元件高度之和最大，该栈的高度决定了包围所有栈的矩形高度。
实际上，在元件折叠问题中，还需考虑连接两个栈的线路所需的附加空间。如，在图1 5 -
10b 中C5 和C6 间的线路因C6 为折叠点而弯曲。这些线路要求在C5 和C6 之下留有垂直空间，以便
能从栈1连到栈2。令ri 为Ci 是折叠点时所需的高度。栈1所需的高度为
h1+h2+h3++h4+h5+r6，栈2所需高度为h6+h7+h8+r6+r9
在标准单元设计中，电路首先被设计成为具有相同高度的符合线性顺序的元件排列。假设
此线性顺序中的元件为C1，⋯，Cn，下一步元件被折叠成如图1 5 - 11所示的相同宽度的行。在
此图中， 1 2个标准单元折叠成四个等宽行。折叠点是C4，C6 和C11。在相邻标准单元行之间，
使用布线通道来连接不同的行。折叠点决定了所需布线通道的高度。设li 表示当Ci 为折叠点时
所需的通道高度。在图1 5 - 11的例子中，布线通道1的高度为l4，通道2的高度为l6，通道3的高
度为l11。
位－片栈折叠和标准单元折叠都会引出一系列的问题，这些问题可用动态规划方法来解决。
1. 等宽位－片元件折叠
定义r1 = r(n+1) =0。由元件Ci 至Cj 构成的栈的高度要求为
li+l(i+1)+....+ ri+r(j+1) + 1。设一个位－片设计中
所有元件有相同宽度W。首先考察在折叠矩形的高度H给定的情况下，如何缩小其宽度。设Wi
为将元件Ci 到Cn 折叠到高为H的矩形时的最小宽度。若折叠不能实现，取
Wi =∞。注意到W1 可能是所有n 个元件的最佳折叠宽度。
当折叠Ci 到Cn 时，需要确定折叠点。现假定折叠点是按栈左到栈右的顺序来取定的。若
第一点定为Ck+ 1，则Ci 到Ck 在第一个栈中。为了得到最小宽度，从Ck+1 到Cn 的折叠必须用最优
化方法，因此又将用到最优原理，可用动态规划方法来解决此问题。当第一个折叠点k+ 1已知
时，可得到以下公式：
Wi =w+ Wk + 1
由于不知道第一个折叠点，因此需要尝试所有可行的折叠点，并选择满足式的折
叠点。令h s u m(i,k)=hi+h(i+1)+...+hj。因k+ 1是一个可行的折叠点，因此h s u m(i, k) +ri +rk+1 一定不会超过H。
根据上述分析，可得到以下动态规划递归式：
Wi=w+min{W(k+1)|hsum(i,k)+ri+r(k+1)<=H,i<=k<=n} (15-10)
这里Wn+1 =0，且在无最优折叠点k+ 1时Wi 为∞。利用递归式，可通过递归计算Wn , Wn- 1
⋯, W2 , W1 来计算Wi。Wi 的计算需要至多检查n-i+ 1个Wk+ 1，耗时为O (n-k)。因此计算所有Wi 的
时间为O (n2 )。通过保留式每次所得的k 值，可回溯地计算出各个最优的折叠点，其
时间耗费为O (n)。
现在来考察另外一个有关等宽元件的折叠问题：折叠后矩形的宽度W已知，需要尽量减小
其高度。因每个折叠矩形宽为w，因此折叠后栈的最大数量为s=W / w。令Hi, j 为Ci , ⋯, Cn 折叠成
一宽度为jw 的矩形后的最小高度， H1, s 则是所有元件折叠后的最小高度。当j= 1时，不允许任
何折叠，因此：
Hi,1 =h s u m(i,n) +ri , 1≤i≤n
另外，当i=n 时，仅有一个元件，也不可能折叠，因此：
Hn ,j=hn+rn , 1≤j≤s
在其他情况下，都可以进行元件折叠。如果第一个折叠点为k+ 1，则第一个栈的高度为
h s u m(i,k) +ri +rk+ 1。其他元件必须以至多(j- 1 ) *w 的宽度折叠。为保证该折叠的最优性，其他元件
也需以最小高度进行折叠，即：
Hi,j=max{hsum(i,k)+ri+r(k+1),Hk+1,j-1}
因为第一个折叠点未知，因此必须尝试所有可能的折叠点，然后从中找出一个使式
的右侧取最小值的点，该点成为第一个折叠点。所得递归式为：
Hi,j=min[max{hsum(i,k)+ri+r(k+1),Hk+1,j-1}] i<=k<n
Wi =w+ Wk + 1
由于不知道第一个折叠点，因此需要尝试所有可行的折叠点，并选择满足式的折
叠点。令h s u m(i,k)=
k å
j = i
hj。因k+ 1是一个可行的折叠点，因此h s u m(i, k) +ri +rk+1 一定不会超过H。
根据上述分析，可得到以下动态规划递归式：
这里Wn+1 =0，且在无最优折叠点k+ 1时Wi 为∞。利用递归式，可通过递归计算Wn , Wn- 1
⋯, W2 , W1 来计算Wi。Wi 的计算需要至多检查n-i+ 1个Wk+ 1，耗时为O (n-k)。因此计算所有Wi 的
时间为O (n2 )。通过保留式每次所得的k 值，可回溯地计算出各个最优的折叠点，其
时间耗费为O (n)。
现在来考察另外一个有关等宽元件的折叠问题：折叠后矩形的宽度W已知，需要尽量减小
其高度。因每个折叠矩形宽为w，因此折叠后栈的最大数量为s=W / w。令Hi, j 为Ci , ⋯, Cn 折叠成
一宽度为jw 的矩形后的最小高度， H1, s 则是所有元件折叠后的最小高度。当j= 1时，不允许任
何折叠，因此：
Hi,1 =h s u m(i,n) +ri , 1≤i≤n
另外，当i=n 时，仅有一个元件，也不可能折叠，因此：
Hn ,j=hn+rn , 1≤j≤s
在其他情况下，都可以进行元件折叠。如果第一个折叠点为k+ 1，则第一个栈的高度为
h s u m(i,k) +ri +rk+ 1。其他元件必须以至多(j- 1 ) *w 的宽度折叠。为保证该折叠的最优性，其他元件
也需以最小高度进行折叠，即：
因为第一个折叠点未知，因此必须尝试所有可能的折叠点，然后从中找出一个使式
的右侧取最小值的点，该点成为第一个折叠点。所得递归式为：
可用迭代法来求解Hi, j ( 1≤i≤n, 1≤j≤s)，求解的顺序为：先计算j=2 时的H i, j，再算j= 3，
⋯，以此类推。对应每个j 的Hi, j 的计算时间为O (n2 )，所以计算所有H i, j 的时间为O(s n2 )。通过
保存由式计算出的每个k 值，可以采用复杂性为O (n) 的回溯过程来确定各个最优的
折叠点。
2. 变宽位－片元件的折叠
首先考察折叠矩形的高度H已定，欲求最小的折叠宽度的情况。令Wi 如式所示，
按照与式相同的推导过程，可得：
Wi = m i n {w m i n(i, k) +Wk+1 | h s u m(i,k)+ ri +rk+ 1≤H, i≤k≤n}
其中Wn+1=0且w m i n(i,k)= m in
i≤j≤k
{wj }。可用与式一样的方法求解式，所需时间
为O(n2 )。
当折叠宽度W给定时，最小高度折叠可用折半搜索方法对超过O(n2 )个可能值进行搜索来
实现，可能的高度值为h(i,j)+ri +rj + 1。在检测每个高度时，也可用式来确定该折叠的
宽度是否小于等于W。这种情况下总的时间消耗为O (n2 l o gn)。
3. 标准单元折叠
用wi 定义单元Ci 的宽度。每个单元的高度为h。当标准单元行的宽度W 固定不变时，通过
减少折叠高度，可以相应地减少折叠面积。考察Ci 到Cn 的最小高度折叠。设第一个折叠点是
Cs+ 1。从元件Cs+1 到Cn 的折叠必须使用最小高度，否则，可使用更小的高度来折叠Cs+1 到Cn，从
而得到更小的折叠高度。所以这里仍可使用最优原理和动态规划方法。
令Hi , s 为Ci 到Cn 折叠成宽为W的矩形时的最小高度，其中第一个折叠点为Cs+ 1。令
w s u m(i, s)=w1+w2+...+ws
可假定没有宽度超过W的元件，否则不可能进行折叠。对于Hn,n 因为只有一
个元件，不存在连线问题，因此Hn, n =h。对于H i, s注意到如果w s u m(i, s )＞W，不
可能实现折叠。若w s u m(i,s)≤W，元件Ci 和C j + 1 在相同的标准单元行中，该行下方布线通道的
高度为ls+ 1。因而：
Hi, s = Hi+1, k
当i=s＜n 时，第一个标准单元行只包含Ci 。该行的高度为h 且该行下方布线通道的高度为
li+ 1。因Ci+ 1 到Cn 单元的折叠是最优的，可得：
Hi,i=min{Hi+1,k}+l(i+1)+h
i<k<=n
为了寻找最小高度折叠，首先使用式和来确定Hi, s 。最
小高度折叠的高度为m in｛H1 , s｝。可以使用回溯过程来确定最小高度折叠中的折叠点。
