0

多重制約ナップザック問題

私はそのような例を持っていますが、理解しようとしているだけです.O（n * logn）の貪欲なアルゴリズムとO（n2）の貪欲なアルゴリズムの違いは何ですか？私は本当に開始する方法がわからない助けてください! 私はそれを並べ替えるか、何か違うものにする必要があります:( ? (利益と重量の比率は降順でも昇順でもなく、完全にランダムです) p = (p1; : : : ; pn) = (24; 17; 95; 103; 41; 39; 22; 1) w = (w1; : : : ;wn) = (20; 15; 39; 41; 27; 23; 18; 2)

4

1 に答える 1

0

そうです、O(n log n) アルゴリズムは、(利益 / 重量) で降順に並べ替えてから、重量制限までできるだけ多くのオブジェクトを取得することです。もちろん、ソートアルゴリズムは O(n log n) でなければなりません。

素朴な (O(n^2)) アルゴリズムは、(利益/重量) 比率が最も高いアイテムのリストを繰り返し検索し、それを取得することです。これは、事実上、選択ソートを行うことと同じであることに注意してください。

于 2013-04-29T21:17:35.370 に答える