Algorithm for Optimal Cutting.

[Andreech]

Привет.
Вот такая задачка.

/***************************************/

You have to cut out of linear bars of standard length (L), N pieces, each one length Ln.
The cutter eat a thickness T.
A rough request for the number of bars needed is: X = Integer( Σ(Ln+T) ) + 1
The objective is to find the sequence of the cuts to minimise X.

Hint:
add (L1+T), (L2+T), …. to fill a bar then take a next bar and so on… at the end you get a value for X

start again adding (L1+T) , (L3+T), (L4+T), and so on…
then (L1+T), (L4+T), (L5+T), …
at the end

The computing process should consider all the possible combination and at the end choose the combination that minimise X.

The result should be the ordered list of elements to be obtained to minimise X.

/***************************************/

С Уважением,
Андрей Шакиров.

[Lisa]

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><HR>Originally posted by Andreech:
<STRONG>Привет.
Вот такая задачка.

/***************************************/

You have to cut out of linear bars of standard length (L), N pieces, each one length Ln.
The cutter eat a thickness T.
A rough request for the number of bars needed is: X = Integer( Σ(Ln+T) ) + 1
The objective is to find the sequence of the cuts to minimise X.

Hint:
add (L1+T), (L2+T), …. to fill a bar then take a next bar and so on… at the end you get a value for X

start again adding (L1+T) , (L3+T), (L4+T), and so on…
then (L1+T), (L4+T), (L5+T), …
at the end

The computing process should consider all the possible combination and at the end choose the combination that minimise X.

The result should be the ordered list of elements to be obtained to minimise X.

/***************************************/

С Уважением,
Андрей Шакиров.</STRONG><HR></BLOCKQUOTE>

По-моему это очень известная cutting-stock problem про которую написано немало статей. [img:1d3aee0720]images/smiles/icon_smile.gif[/img:1d3aee0720]
Решается с помощью линейного программирования и всевозможных heuristics для получения целочисленного решения.

[Andreech]

Привет.
Спасибо за ответ.

А напишите адреса сайтов, где можно почитать про эту задачку.
Спасибо.

С Уважением,
Андрей Шакиров.

[Lisa]

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><HR>Originally posted by Andreech:
<STRONG>Привет.
Спасибо за ответ.

А напишите адреса сайтов, где можно почитать про эту задачку.
Спасибо.

С Уважением,
Андрей Шакиров.</STRONG><HR></BLOCKQUOTE>

Напишите мне, я вам поищу ссылок на статьи. Или так расскажу, смотря какое вам решение нужно.