次のアルゴリズムの問題があります。
小数点以下 2 桁の精度で異なる長さの複数の木材を記述する顧客の注文があるとします。例: 2 * 1,50 ; 2 * 0.50 (必要な木材は 4 つ、長さ 1.50 メートルの 2 ピースと長さ 0.50 メートルの 2 ピース)。
木材の在庫数に制限はありませんが、長さは 2、3、4、5 メートルに固定されています。 顧客注文の木材は、在庫の梁から切断する必要があります。カット自体は、理想化として厚さが 0 です。 ビーム長が 5,00 メートルを超える注文はできません。
目標は、顧客の注文を完了した後に生じる木材の無駄を最小限に抑えることです。無駄の少ない解が複数ある場合、カットの少ない解が最適です。
上記の顧客注文の例では、在庫から 2.00 メートルの木材を 2 つ取り、それぞれを 0.5 メートルと 1.5 メートルの部分に切断します。したがって、アルゴリズムは無駄 = 0、2 カットを生成します。
Example 1:
Customer order: 2 * 1,50 ; 2 * 0,50
Output:
Total waste: 0
Total cuts: 2
2,00 --> 1,50 ; 0,50 waste 0
2,00 --> 1,50 ; 0,50 waste 0
Example 2:
Customer order: 2 * 2,48 ; 1 * 2,68 ; 2 * 3,12 ; 1 * 1,32; 2 * 1,33 ; 1 * 1,34
Output:
Total waste: 1,80
Total cuts: 7
4,00 --> 1,33 ; 1,33 ; 1,34 waste 0
4,00 --> 2,68 ; 1,32 waste 0
4,00 --> 3,12 ; waste 0,88
4,00 --> 3,12 ; waste 0,88
5,00 --> 2,48 ; 2,48 waste 0,04
ブルート フォース アプローチは、顧客の注文に含まれる特定の数のビームでは、パフォーマンスが非常に低くなります。
優れたアルゴリズム的アプローチのアイデアはありますか? 大きな複雑さについてのアイデアはありますか?