孟子及csdn高手们，一个算法问题请教思路，数学算法，可能有点难度
一个矩形1000*2000要取
208*200 14张
208*962 2张
208*862 3张
如何剪裁才能共需标准的矩形几个，如何剪裁才能更省标准版的材料呢
这是其一，还有就是我的这些板类型不固定
这个有可能是
208*200 14张
208*962 2张
208*862 3张
208*860 3张
等等可能很多类型
挠了一上午头，来这里透透气，大家给个思路
--------------------编程问答-------------------- 更省标准版的材料,的标准是什么呢？
--------------------编程问答-------------------- 标准版的材料呢是1000*2000 矩形板 --------------------编程问答-------------------- 貌似可以采用取大优先的原则(以宽为标准),宽度最大的先取. --------------------编程问答-------------------- 说错了,应该是以高为标准,先从最高的板材取起,然后以次类推.(中间不够取的部分用判断就可以了)
--------------------编程问答--------------------
up!! --------------------编程问答-------------------- 长宽都建数组，索引对应，长或宽取大优先，再把多余从小到大循环，得出符合要求的最大值.只说说自己的一点想法，希望高手来赐教一下 --------------------编程问答-------------------- 可以这么裁吗?
-------------------------
| | |
| | |
| |---------------|
|-------| |
| | |
-------------------------
还是必须象裁玻璃那样必须一刀从头到尾? --------------------编程问答-------------------- 有个参照物 好办 ^_^ --------------------编程问答-------------------- up!!
--------------------编程问答-------------------- 有时一个典型的装箱问题，
找找这方面的算法看看吧 --------------------编程问答-------------------- 你的这个是要找最优解，所以要用的是回溯法 --------------------编程问答-------------------- 顶下... --------------------编程问答-------------------- 一点点思路：不区分矩形的长和高，依次取你要切取的矩形的其中一条边的长度相加，如果计算出的结果越接近1000*2000 或者2000*1000,即为最佳方案。
比如计算出的结果为：
一条边：100 200 300 200 200
另一条边200 400 600 300 500
对应的四个矩形就是1（100，200）2（200,400）3（...）4（...）
那么以任何一边做为高，另一边则是宽来切取 --------------------编程问答-------------------- mark --------------------编程问答-------------------- 其实就是板材切割的最优算法问题
大家多给些指点 --------------------编程问答-------------------- 有个算法与数据结构版。 --------------------编程问答-------------------- http://forum.csdn.net/SList/ST_Arithmetic/ --------------------编程问答-------------------- 世界性难题？？ --------------------编程问答-------------------- 不出丑了 帮顶 --------------------编程问答-------------------- csdn
人呢 --------------------编程问答-------------------- 难道都只会增删改查
那太没有编程的意思了吧 --------------------编程问答-------------------- UP --------------------编程问答-------------------- 通过回溯找最优解,数据结构中有很多类似的东东,最短路径,迷宫通路什么的,都可以参考一下 --------------------编程问答-------------------- 好难，不会 --------------------编程问答-------------------- 是求使得浪费的材料最少的最优方案吗？
一个矩形1000*2000
要取
208*200 , 208*962 , 208*862
首先看看下面这两个哪个值小，便取个开始割。
1000-(208*x1+200*x2+962*x3+862*x3)=y1 (其中y1>=0)
2000-(208*x1+200*x2+962*x3+862*x3)=y2 (其中y2>=0)
如果y1<y2，刚从边长为1000这条边开始，否则从2000那条边开始。
按照求出的x1,x2,x3变量的值，进行切割。然后再按照割完后的边，求出以那边为一边。另一条边可变的最优个数。
--------------------编程问答-------------------- 哈哈，开会了，搬个板凳慢慢看。mark --------------------编程问答--------------------
想想觉得应该两种都算下，然后进行对比，选出损失最小的。
1000-(208*x1+200*x2+962*x3+862*x3)=y1 (其中y1>=0) 求出使得y2最小值时的x1,x2,x3
2000-(208*x1+200*x2+962*x3+862*x3)=y2 (其中y2>=0) 求出使得y2最小值时的x1,x2,x3
--------------------编程问答-------------------- 头几天看到了一个取木材的.今天看到个裁纸的....应该差不多吧. --------------------编程问答-------------------- ding --------------------编程问答-------------------- 凡是“最xxxxx”的这类问题，只有极少数可以使用贪心策略简单地找到结果，大多都是非人力所能想清楚的问题。我建议你，先尽量找最快、内存最大的计算机用傻瓜办法查找结果。 --------------------编程问答-------------------- 下棋策略不需要考虑“最”，也就是不穷举所有可能的棋局，而只要看3不或者看5不然后使用一个“形势判断”函数来简单指引就行了。“最xxxxxx”这类问题，往往不允许人为进行抽象，看上去目标最简单让人以为凭着一点耐心就能找到解答，其实最骗人。
真正生产环境，不应该求最优解，而应该根据老工人的经验做法求得次优解。这就不是数学教授擅长解答的问题。 --------------------编程问答--------------------
谢谢sp123
不过还是没有思路 --------------------编程问答--------------------
这样可以的 --------------------编程问答--------------------
就是给定的标准矩形1000*2000
--------------------编程问答-------------------- 友情帮顶 --------------------编程问答--------------------
有什么好的思路没 --------------------编程问答-------------------- 貌似lz是学算法的,lz最近所提的问题都与算法相关;
这个问题和你上次提的一个取直型材料的算法差不多,不过是高和宽的究举算法(复杂度高一点,原理是一样的). --------------------编程问答-------------------- 13楼正解
--------------------编程问答-------------------- 二维线性规划问题,找运筹学 --------------------编程问答-------------------- 学习 --------------------编程问答-------------------- ding --------------------编程问答-------------------- ding!~
补充：.NET技术 , ASP.NET
