12

複数のナップザック問題を効果的に解決する擬似コードを探しています(最適化ステートメントはページの途中にあります)。この問題は NP Complete であると思いますので、ソリューションが最適である必要はなく、かなり効率的で簡単に実装できれば良いと思います。

問題はこれです：

  • 多くの作業項目があり、それぞれが完了するまでにかかる時間が異なります (ただし固定されており、既知の時間)。
  • これらの作業項目をグループに分割して、(理想的には) グループの数を最小にし、作業項目の各グループが所定の合計しきい値 (たとえば 1 時間) を超えないようにする必要があります。

私はしきい値について柔軟です。厳密に適用する必要はありませんが、近い値にする必要があります。私のアイデアは、各ビンがしきい値の 90%、80%、70% などを表すビンに作業項目を割り当てることでした。次に、90% かかるアイテムと 10% かかるアイテムを一致させることができます。

より良いアイデアはありますか？

4

2 に答える 2

11

http://www.or.deis.unibo.it/knapsack.htmlの 6.6 章「複数のナップスック問題 - 近似アルゴリズム」が必要です。テキストには疑似コード (Pascal スタイル) と Fortran 実装 (はい、古い本です) が ZIP ファイルとして含まれています。

于 2010-03-08T14:43:52.433 に答える
2

私の知る限り、この問題は NP 完全 (ウィキペディアが確認) であるため、正確に解決しようとするのはおそらくあまり意味がありません。ただし、任意の数のアプローチで十分な場合があります。貪欲、遺伝的アルゴリズム、アニーリングのシミュレート...貪欲はおそらく実装が最も簡単です。

while (time available in block greater than smallest task duration)
  find the longest fitting task
  add it

…お分かりですね。

于 2010-03-08T14:49:49.997 に答える