ナップザックの問題と？

Question

よし概要

私はナップザック問題

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

に見ていると私はそれは私が私のプロジェクトのために必要なものですけど、私のプロジェクトの複雑な部分は、私は複数必要ということでしょう主袋の中に袋を入れる。

すべての「バッグ」を保持する大きなナップザックは、「バッグ」をx個だけ持ち運ぶことができます（例として9と言うことができます）。各バッグには異なる値があります。

• 重
• コスト
• サイズ
• 容量

というように、これらの値の全てが整数です。 0-100と仮定します。

インナーバッグにもタイプが割り当てられ、そのタイプはアウトサイドバッグ内に1つしかない場合がありますが、プログラム入力には同じタイプの複数が与えられます。

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

---

例

外袋：

• は9つの小さな袋
• 98を超えない重量を保持することができます
• [5側のいずれかを与えるか、または取る]それぞれのいずれかを保持する必要がありますタイプは、一度に各タイプのうちの1つだけを保持することができます。

インナーバッグ：

• コスト、100％
• サイズで加重、67％
• 能力で加重、44％

---

プログラムで加重複数の袋の入力が与えられ、次に小さい袋の組み合わせを試してlaに入ります入力に応じて複数のソリューションがあり、プログラムは私にとって最高のソリューションを出力します。

私はこれに接近するための最善の方法があると思います。

私はJavaまたはC＃でプログラミングします。私はPHPでそれをプログラムしたいと思うが、私はアルゴリズムがWebサーバにとって非常に非効率的であることを恐れている。あなたは

-Zack

Answer 1

オーケーを与えることができます任意の助け

おかげで、うまく、ナップサックは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 

ようになりたいプログラムの概要と実行時間は指数関数的になります。しかし、dynamic programmingで近似解を得ることができるように聞こえます。

Answer 2

論理プログラミングにはPrologを使用することを検討してください。モノ（.NET）上にP#を含む複数の実装があります。少し勉強の曲線ですが、それに慣れてしまうと、この種の問題解決のためにはそれ自体がリーグになります。

これが役に立ちます。乾杯！ P#