0
最初はかなりシンプルに見えたが、しかし、私は効率的な解決策を見つけることができませんでした。みんな助けてくれますか？効率的なフレームカットアルゴリズム
シートは、ギャップを有するが交差しない様々な長さおよび幅の矩形（フレーム）からなる。それらの矩形を分離するストレートカット（垂直または水平）の最小量を見つけます。利用可能なボード全体を通してカットを作成する必要があります。
入力は、それぞれの左上および右下座標に続く四角形の数で構成されます。アウトプットにはカット数があり、それに続いて垂直/水平カットを表す2つの点、または解がない場合はNAが必要です。いくつかの最適解が可能であることに注意してください。
（3,3）
（0,0）（1,1）
（2,0）（3,1）
（：入力
0,2）（3,3）
出力：
（0,2）（2,2）
（1,0）（1,2）
入力：
（5,5）
（0,0）（3,1）
（4,0）（5,3）
（0,2）（1,5）
（2,4）（5,5）
出力：
感謝を見つけることができます。あなたの答えを少し修正したいのであれば、問題はCutting Stockの問題のより具体的なバージョンだと思います。 **ギロチンの問題**は、上記の問題のケースである、各シート全体に渡ってカットを作成することのみを必要としました。 – user2961443
@ user2961443：はい。これはまさに、矩形中間解決策を用いた階層的なペアワイズマージアルゴリズムがギロチン切断パターンを生成するのです。 – AnT