アルゴリズム、ブロック積み上げ - グラフ理論

Question

私のアルゴリズムクラスでこの問題に苦しんでいます。そのグラフ理論のセクションです。私は最大の重み付きマッチングを使用すると思います。しかし、どのように二部グラフを構築するか分からない。助言がありますか？

サイズがa1×b1、nの長方形が与えられます。 。 。 、×bn。我々は 長方形の中で最も高い塔を構築したい。タワーで、幅wの矩形が幅の矩形の上にある場合 w ' そしてw≦w' が必要です。矩形を回転させることができる（すなわち、a×b矩形は、 b×矩形に変更することができる）。可能な限り高いタワーの高さを求めるO（n）アルゴリズムを与えます。 （たとえば、入力が11×11,8×2,1×10の場合、解は高さ29 = 11 + 8 + 10のタワーになります）

Answer 1

問題が正しく理解できれば、いつでもMath.max(ai,bi)を合計すると、最高のタワーの高さを見つけることができます。タワーを建てる必要はないので、それはO(n)です。それ以外の場合は、O(nlogn)（長方形の高さでソート）が必要です。