神马品牌网成都电信40元宽带包月:求一个最大利用率算法（或者给个好思路）
来源：百度文库 编辑：神马品牌网 时间：2024/05/03 06:33:45
在制造线路板时，会购买不同尺寸的覆铜板比如：40*48（Inch）、42*48（Inch）......，每制作一款线路板，先拼成一个较大的尺寸的PNL用于生产。问题是：在覆铜板中选择一个能够在上面剪成若干个PNL，且是的这个覆铜板达到最高的利用率。
可能我上面说的不怎么明白，下面我就打个比方：现在有200*300mm、300*400mm、250*280mm的长方形白纸，现在要从这些纸上剪36*42mm的长方形50个、60*80mm的长方形30个。怎样剪白纸的利用率最高？有时还会有更多中尺寸的白纸，要剪更多种规格的长方形（一般不超过5种）。
请各位赐教！谢谢！！！
可能我上面说的不怎么明白，下面我就打个比方：现在有200*300mm、300*400mm、250*280mm的长方形白纸，现在要从这些纸上剪36*42mm的长方形50个、60*80mm的长方形30个。怎样剪白纸的利用率最高？有时还会有更多中尺寸的白纸，要剪更多种规格的长方形（一般不超过5种）。
请各位赐教！谢谢！！！
这个可以考虑用背包算法来解决。原理是每次都用最大值来组合，形成用最少的数目来达到最大的数据。比如8毛钱，人民币有5毛，2毛，1毛组成，那8毛钱用什么样的组合达到用最少数量的纸币呢？算法是这样，采取能取到的值的最大值（只要不超过总值），即5毛一张，接着剩下3毛的余额，采用能取到的最大值，即2毛，接着就是1毛，共3张纸币就解决了。