dynamic - ナップザック (多基準)

Question

重量 w がv1 と v2 の 2 つの値を持ち、容量が m のナップザックがあるとします。重量が容量 m を超えない v1 と v2 の合計値を見つけるにはどうすればよいですか?

Answer 1

さて、あなたの問題は次のように定義されています。最初のいくつか (サンプル値を含む変数定義):

int N = 4; // number of items to choose from
int m = 6; // maximum weight in knapsack

// weight for an item[i] to be summed up, upper limited = m
int weight[N] = {5,2,4,3}; 

// two values for each items:
int values[2][N] = {
  {1,3,5,2},
  {6,3,2,4}
};

ナップザックには、ナップザック内のすべてのアイテムの重量の合計が重量「m」を超えないように、アイテムを詰めることができます。各項目に 2 つの値があります。この問題は次のように考えることができます。

彼女と一緒に飛行機で休暇に行きたいです。そして、1 つのスーツケース (=ナップザック) と N 個のアイテムから選択できます。各アイテムには重量があり、重量の合計が高すぎない場合があります (たとえば、エアラインの重量制限は 25 kg でスーツケースは 1 kg であるため、アイテムの制限として m=24 kg があります)。各アイテムには 2 つの値があります。値[1][N]は、私にとっての値です（ツアーでナップザックにアイテムnを入れるため）。値[2][N]は、好みが異なる私のガールフレンドの値です。また、すべてのアイテムをナップザックに一度だけ入れることができ、ナップザックの全体的な価値は、私にとっての価値の合計に彼女にとっての価値の合計を加えたものであると仮定します。

この問題は、値リストを追加するだけで、標準のナップザック問題に簡単に変換できます。したがって、アイテムは全体的な値を取得し (たとえば、私と彼女が一緒の場合)、1 つのアイテムに対して 1 つの値しかありません。

int value[N] = {(1+6),(3+3),(5+2),(2+4)};

あるいは単に：

int value[N] = {7, 6, 7, 5};

これで、各項目に 1 つの値しかありません。これは通常のナップザックの問題です。

通常のナップザック問題を最適に解く方法は、Wikipedia に記載されています。http://en.wikipedia.org/wiki/Knapsack_problemを見てください-- 英語が母国語でない場合は、あなたの言語のバージョンも見てください (メニューから言語を選択してください)。

さらにサポートが必要な場合は、お尋ねください。