ナップザック問題の変形に対する動的プログラミングアルゴリズムの作成

Question

私は考えていたので、

ナップザック問題を変形したいと思っていました。

さまざまな重み付け/値を持つアイテムで、元の問題を想像してください。

私のバージョンは、通常の重み付け/値とともに「グループ」値を含みます。

例えば、 アイテム1 [5キロ、$ 600電子] アイテム2、私が確認するために、ナップザック問題をコーディングする方法を今[1キロ、$ 50食品]

、このようなアイテムのセットを持つ、その1つの項目の最大値から各「グループ」が選択されます。

注：

1. あなたは、各グループ内の複数の項目
2. あなたはまだ値
3. 最大化、重量を最小限に抑えているがありますが、そのグループ
4. から項目を選択する必要はありませんグループの量は、その値と共に事前定義されています。

私はこの段階でコードの草稿を書いています。私は動的アプローチを採用しました。私は定期的なナップザック問題のダイナミックなソリューションの背後にあるアイデアを理解していますが、これらの「グループ」を組み込むためにこのソリューションを変更するにはどうすればよいですか？私は、今のところ持って、それはそれはそれは、これを解決するたびにあるグループから対応するすべての項目を削除するようにそれを追加するために必要なものだ

KnapSackVariation(v,w,g,n,W) 
{ 
    for (w = 0 to W) 
    V[0,w] = 0; 
    for(i = 1 to n) 
    for(w = 0 to W) 
     if(w[i] <= w) 
      V[i,w] = max{V[i-1, w], v[i] + V[i-1, w-w[i]]}; 
     else 
      V[i,w] = V[i-1, w]; 
    return V[n,W]; 
} 

。 i番目の要素
V [I、W、S]のカテゴリ：

Answer 1

は
C [I]を想定し、それは S

内の各カテゴリから最大つの項目に含まれているように、ナップザックの最大値

Recursive Formulation 
V[i,w,S] = max(V[i-1,w,S],V[i,w-w[i],S-{c[i]}] + v[i]) 
Base Case 
V[0,w,S] = -`infinity if w!=0 or S != {}` 

Answer 2

あなたの質問に気づき、自分の質問に対する回答を見つけようとしました。あなたが述べた問題は、よく知られており、よく研究された問題であり、複数選択ナップザック問題と呼ばれています。グーグルであれば、あらゆる種類の情報を見つけることができますし、この本をお勧めします：http://www.amazon.co.uk/Knapsack-Problems-Hans-Kellerer/dp/3642073115/ref=sr_1_1?ie=UTF8&qid=1318767496&sr=8-1、これは章全体をこの問題に捧げています。 MCKPの定式化では、各グループから1つのアイテムを選択する必要があります。ただし、利益と重量= 0の各グループにダミーアイテムを追加することで、そのバージョンの問題をあなたのバージョンに簡単に変換することができ、同じアルゴリズムが機能します。私は、MCKPにバイナリナップザック問題のコードをいくつか調整しないように注意します。このアプローチは、各グループの項目の数が増えるにつれてパフォーマンスが許容できなくなるソリューションにつながる可能性があります。