我需要拿出一个算法切割木板以最小的浪费左。切割机切割直线;它不能中途停下来如旋转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