问题描述
我需要拿出一个算法切割木板以最小的浪费左。切割机切割直线;它不能中途停下来如旋转90°，然后继续。
I need to come up with an algorithm for cutting wooden boards with minimum waste left. The cutting machine cuts in straight lines; it can't stop halfway to e.g. turn 90° and continue.
示例：
我有一个木板，尺寸为280厘米x207厘米，需要尽量减少浪费切割过程后。照片
Example:
I have a wooden board with dimensions 280cm x 207cm and need to minimize the waste after the cutting process.
我有表宽度和长度的下集。
I have the following set of table widths and lengths.
宽度
140
140
140
197
197
30,5
30,5
Width
140
140
140
197
197
30,5
30,5
长度
33
33
33
33
33
33
33
Length
33
33
33
33
33
33
33
我想用贪婪算法，因为长度总是相同的。任何想法？
I am thinking about using "Greedy algorithm" since the length is always the same.Any ideas?
推荐答案
这是二维装箱，这是NP难的变种。一个常见的逼近它是排序件通过宽度，然后开始从最小的剩余板仍足以切割件。了解更多关于这一点，更复杂的算法，在 HTTP：//cgi.csc.liv .ac.uk /〜EPA / surveyhtml.html
This is a variant of 2D bin packing, which is NP hard. A common approximation to it is sorting the pieces by width and then start cutting out pieces from the smallest remaining board that still suffices. Read more about this and more complex algorithms at http://cgi.csc.liv.ac.uk/~epa/surveyhtml.html
这篇关于有效的木板切割算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！