一道算法题。求高手!重谢
时间:2011-12-04
来源:互联网
是一个关于利用率问题的题目
在一个大矩形里 切割 一个 或者 多个规格 的小矩形 ,怎么样切大矩形的利用率是最高的 。
在一个大矩形里 切割 一个 或者 多个规格 的小矩形 ,怎么样切大矩形的利用率是最高的 。
作者: luoyehanfei 发布时间: 2011-12-04
我用js写了一段代码 来分页这个题目的需求。大家可以看下,不喜勿喷。 求优良的算法。。。。。。。。。。。。。。JScript code
//算法 问题:一张纸按照指定的一个或多个规格分切,怎么样利用率最大 ? //重点1 :规格分为1个或者多个 //重点2 : 如果是多规格 ,有没有指定没种规格最少需要多少呢 ?还是直接按照最优的切出来就行 ? /**********函数体************/ //需要准备的参数 ?1 纸张对象 (对象具备宽高属性) // 2 要切的纸张规格对象 ? 因为具备多种规格,此对象为数组。 // (每个数组的成员为一个对象 具备宽高属性 另,具备一个最少切割数属性) // oldobj设置 x y属性 //objpar的每个成员有x y 和 conts 属性 x y 表示宽高 conts 表示最少切割数 //分析: 所切矩形面积之和 function Cutpager(oldobj, objpar) { //首先我们获取原始纸张的宽和高 var owidth = oldobj.x; var oheight = oldobj.y; var par = new Array();//此数组用来记录刚好切完的单个最优规格。 //首先我们确定下 如果切完的规格刚好为0.那么此种算法肯定利用率就最大。我们先来一个循环 var iszerno = 0;//记录是否有最小切割数不能为0的 。此时的0是记录有几个最少切割数不能为0的。 for (var i = 0; i < objpar.length; i++) { //在进行此项操作的时候我们必须要判断,判断对象的最小切割数是不是0,如果规定了必须最少切多少个,肯定不能这样算。 if (objpar[i].conts != 0) { //如果当前对象最小切割输 iszerno++; } } //当循环体执行完毕的时候我们就知道是否有不为0的了。 if (iszerno == 0) { //如果所有的规格并没有规定最少应该切多少个。 //执行第一种排查 将每个规格的元素逐个排查,看能否刚好切割完大的矩形,那么我们就只切这一种纸了。 //这里我们应该做一个正则表达式 来判断一个为正整数的数组 ,还是执行循环。 //循环规格数组 for (var i = 0; i < objpar.length; i++) { //这里应该把当前规格直接与大的矩形想对比 以 owidth*oheight/(objpar[i].x*objpar[i].y) 判断此值是否为正整数 if ((owidth * oheight) % (objpar[i].x * objpar[i].y) == 0) { par.push(objpar[i]); } } } else if (iszerno == 1) { //这里要考虑规格当中如果只有一种有最少要求切割数。那么它也可以当作唯一的规格来切割。 } else { //这里当然就是最少有2个规格都是有最少需要切割的数量,此时,要进行更为复杂算法。 } }
作者: luoyehanfei 发布时间: 2011-12-04
问题本身是NP的,只能找些近似的方法,当然矩形数量不多的情况系可以考虑枚举
作者: litaoye 发布时间: 2011-12-04
引用 2 楼 litaoye 的回复:
问题本身是NP的,只能找些近似的方法,当然矩形数量不多的情况系可以考虑枚举
问题本身是NP的,只能找些近似的方法,当然矩形数量不多的情况系可以考虑枚举
把大矩形 和 所要切的规格当作参数传入 。它们既然都有尺寸和数字,应该是能求出最优良的切法的吧。
作者: luoyehanfei 发布时间: 2011-12-04
规格不多的话可以枚举,如果有几十个,恐怕就很难算了。
引用 3 楼 luoyehanfei 的回复:
引用 2 楼 litaoye 的回复:
问题本身是NP的,只能找些近似的方法,当然矩形数量不多的情况系可以考虑枚举
把大矩形 和 所要切的规格当作参数传入 。它们既然都有尺寸和数字,应该是能求出最优良的切法的吧。
引用 2 楼 litaoye 的回复:
问题本身是NP的,只能找些近似的方法,当然矩形数量不多的情况系可以考虑枚举
把大矩形 和 所要切的规格当作参数传入 。它们既然都有尺寸和数字,应该是能求出最优良的切法的吧。
作者: litaoye 发布时间: 2011-12-04
相关阅读 更多
热门阅读
-
office 2019专业增强版最新2021版激活秘钥/序列号/激活码推荐 附激活工具
阅读:74
-
如何安装mysql8.0
阅读:31
-
Word快速设置标题样式步骤详解
阅读:28
-
20+道必知必会的Vue面试题(附答案解析)
阅读:37
-
HTML如何制作表单
阅读:22
-
百词斩可以改天数吗?当然可以,4个步骤轻松修改天数!
阅读:31
-
ET文件格式和XLS格式文件之间如何转化?
阅读:24
-
react和vue的区别及优缺点是什么
阅读:121
-
支付宝人脸识别如何关闭?
阅读:21
-
腾讯微云怎么修改照片或视频备份路径?
阅读:28