6

私が考えていた、

ナップサック問題のバリエーションを作りたかったのです。

さまざまな重み/値を持つアイテムを使用した元の問題を想像してみてください。

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

例えば。Item1 [5kg、$ 600、電子] Item2 [1kg、$ 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];
}

それは私がこれまでに持っているものです、それがこれを解決するたびにそれがいるグループからすべての対応するアイテムを削除するようにそれを追加する必要があります。

4

2 に答える 2

3

私自身の質問に対する答えを見つけようとしているあなたの質問に気づきました。あなたが述べた問題は、多肢選択式ナップサック問題と呼ばれるよく知られたよく研究された問題です。あなたがグーグルであらゆる種類の情報を見つけることができれば、私はこの本をお勧めすることもできます：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に適合させようとしないように注意します。このアプローチでは、各グループのアイテム数が増えるにつれてパフォーマンスが許容できないほど低下するソリューションにつながる可能性があります。

于 2011-10-16T12:25:23.043 に答える
0

c
[i]：i番目の要素のカテゴリ
V [i、w、S]：Sの各カテゴリから最大1つのアイテムを含むようなナップザックの最大値

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 != {}`
于 2011-10-09T16:28:27.407 に答える