3

簡単な概要

ナップザック問題について調べてみました

http://en.wikipedia.org/wiki/Knapsack_problem

それが私のプロジェクトに必要なものであることはわかっていますが、プロジェクトの複雑な部分は、メインの袋の中に複数の袋が必要になることです。

すべての「バッグ」を収納できる大きなナップザックは、x 個の「バッグ」しか持ち運べません (例として 9 個としましょう)。各バッグには異なる値があります。

  • 重さ
  • 料金
  • サイズ
  • 容量

など、これらの値はすべて整数です。0から100までと仮定しましょう。

内側のバッグにもタイプが割り当てられ、プログラム入力には同じタイプの複数が与えられますが、外側のバッグ内にはそのタイプの 1 つしか存在できません。

メイン バッグが保持できる最大重量を割り当てる必要があり、小さいバッグの他のすべてのプロパティは重み付けされた値でグループ化する必要があります。

例

アウターバッグ:

  • 小さめのバッグなら9個収納可能
  • 体重が98以下 [ギブオアテイク5]
  • 各タイプを 1 つ保持する必要があり、一度に各タイプを 1 つだけ保持できます。

インナーバッグ:

  • コスト、100% で加重
  • サイズ、加重 67%
  • 容量、加重 44%

プログラムには複数のバッグの入力が与えられ、小さなバッグの組み合わせを大きなバッグに入れる必要があります。入力に応じて複数のソリューションがあり、プログラムは最適なソリューションを出力します。

私がこれにアプローチするための最良の方法は何だと思いますか。

JavaまたはC#でプログラミングします。PHP でプログラムしたいのですが、Web サーバーにとってアルゴリズムが非常に非効率的ではないかと心配しています。

あなたが与えることができる助けをありがとう

-ザック

4

2 に答える 2

2

さて、ナップザックは NP 困難なので、これも NP 困難になると確信しています (そうでない場合は、外側のバッグ 1 つだけでこれを行うことでナップザックを解決できます)。おそらく、すべての組み合わせを検索する以上のことはできません。だからあなたが望むプログラムの概要は次のようになります

 for each possible combination
 do
   if current combination is better than best previous
      save current combination as best so far
   fi
 od

実行時間は指数関数的になります。ただし、動的計画法を使用して近い解を得ることができるように思えます。

于 2009-04-23T18:19:00.820 に答える
0

論理プログラミングにPrologを使用することを検討してください。モノ (.NET)のP#を含む複数の実装があります。学習曲線は少しありますが、慣れれば、この種の問題解決にはほぼ独歩です。

お役に立てれば。乾杯！

P#へのリンク

于 2009-04-23T20:27:17.157 に答える