サーチ…


備考

ナップザック問題またはリュックサック問題は、 コンビナトリアル最適化の問題である。それぞれが重みと値を持つ一連のアイテムが与えられている場合、合計重量が所定の制限値以下で、合計値ができるだけ大きいように、コレクションに含めるアイテムの数を決定します。それは固定サイズのナップザックに制約されている人が直面する問題からその名前を引き出し、最も価値のあるアイテムで埋めなければならない。

この問題は、資金制約があり、 コンビナトリアルコンピュータサイエンス複雑性理論暗号応用数学毎日のファンタジースポーツなどの分野で研究されているリソース配分でしばしば発生します。

ナップザックの問題は、1897年にさかのぼる初期の作品で1世紀以上にわたって研究されてきました。「ナップザック問題」という名前は、数学者Tobias Dantzig (1884-1956)の初期の作品にさかのぼり、あなたの荷物に過大な負担をかけることなく、貴重なものや有用なものを梱包してください。

0-1ナップザック問題

あなたがあなたのナップザックと重量と価値を持ついくつかのアイテムを運ぶことができる総重量を考えれば、それらの値の合計が最大であるようにそれらのアイテムをどのように取ることができますか?あなたが運ぶことができる総重量を超えていませんか? 0-1は、アイテムを選択するか、選択しないかを示します。また、私たちは各項目を1つずつ持っています。つまり、商品を分割することはできません。 0-1のナップザック問題でなければ、それはアイテムを分割することができれば、そこに欲張りな解決策があることを意味します。これは部分的なナップザック問題と呼ばれます

今のところ、手元の問題に集中しましょう。たとえば、ナップザックの容量が7であるとします。私たちは4つの項目があります。その重みと値は次のとおりです。

+----------+---+---+---+---+
|   Item   | 1 | 2 | 3 | 4 |
+----------+---+---+---+---+
|  Weight  | 1 | 3 | 4 | 5 |
+----------+---+---+---+---+
|   Value  | 1 | 4 | 5 | 7 |
+----------+---+---+---+---+

1つのブルートフォース方法は、可能なすべてのアイテムの組み合わせをとることです。次に、合計重量を計算し、ナップザックの能力を超えて除外し、最大値を与えるものを見つけ出すことができます。 4つのアイテムについて、( 4! - 1 )= 23の可能な組み合わせをチェックする必要があります(アイテムのないものを除く)。アイテムの数が増えると、これはかなり面倒です。ここで、私たちが気付くことができるいくつかの側面は、

  • 私たちは、より少ないアイテムを取って、それらのアイテムを使って得ることのできる最大値を計算し、それらを組み合わせることができます。ですから、私たちの問題はサブ問題に分けることができます。
  • 我々はアイテム{1,2}の組み合わせを計算する場合、我々は、{1、2、3}を計算するとき、我々はそれを使用することができます。
  • 重みを最小にして値を最大にすると、最適解を見つけることができます。

これらの理由から、動的プログラミングを使用して問題を解決します。私たちの戦略は:新しいアイテムが来るたびにアイテムを選択できるかどうかをチェックし、最大値を与えるアイテムを選択します。ここでアイテムを選択すると、値はアイテムの値に加えて、容量から値を減算することによって得られる値と、残りの重量に対して得ることができる最大値となります。アイテムを選択しないと、アイテムを含めずに最大値を示すアイテムが選択されます。私たちの例でそれを理解しようとしましょう:

2次元配列表を取ります 。ここで、列の数はアイテム+ 1を取ることによって得られる最大値になります。行の数はアイテムの数と同じになります。私たちの配列は次のようになります:

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+

われわれの便宜のために、各項目の重みと価値を配列に組み込んだ。これらは配列の一部ではないことを覚えておいてください。これは計算目的のみのためです。これらの値をテーブル配列に格納する必要はありません。

最初の列は0で埋められています 。つまり、アイテムを選択することができないため、アイテムが何であっても最大容量が0であれば、最大値は0になりますテーブル[0] [1]から始めましょう。 表[1] [1]を記入するとき、最大容量が1で、最初の項目のみを持っているかどうかを尋ねます。最大値は何ですか?私たちができることは、アイテムを選ぶことによって1になります。 Table [0] [2]は、最大容量が2で、最初のアイテムしか持たない場合、最大値は1です。 Table [0] [3]Table [0] [4]Table [0] [5]Table [0] [6]Table [0] [7]についても同様です。私たちは私たちだけに値1を与える一つの項目を、持っているためです。各アイテムの数量は1つだけなので、 1つのアイテムからナップザックの容量をどのように増やしても、 1が最善の価値です。だから私たちの配列は次のようになります:

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+

表1 [1]については、アイテム1とアイテム2を持っていて、ナップザックの最大容量が1であれば、最大値はいくらですか?アイテム12の両方を使用すると、合計重量は4になり、現在のナップザック能力を超えます。したがって、項目2は選択できません。今、アイテム2を取らずにできることは何ですか?一番上の値はTable [0] [1]で、最大容量が1で2番目のアイテムを選択しなかった場合に得られる最大値を含んでいます。 Table [1] [2]では、 2weight [2]よりも小さいので、それは2番目のアイテムの重みです。アイテムを取ることはできません。したがって、現在のアイテムの重量が最大の容量よりも大きい場合、そのアイテムは使用できません。この場合、topから値を取ります。これは、アイテムを除外できる最大値を表します。

if weight[i] > j
    Table[i][j] := Table[i-1][j]
end if

今の表[1] [3]の最大容量は現在の重量と等しいので、2つの選択肢があります。

  • 私たちはアイテムを選び、このアイテムを取った後、他の残りのアイテムから得られる最大値でその値を追加します。
  • このアイテムは除外できます。

2つの選択肢の中から、最大の価値を得ることができるものを選択します。アイテムを選択すると、このアイテムの値+このアイテムを取った後の残りのアイテムの最大値= 4 + 0 = 4が得られます。 ウェイト配列から4 (アイテムの値)を取得し、 0 (このアイテムを取った後の残りのアイテムから得ることができる最大値)は、上記の1つのステップと3つのステップに戻ります。それはTable [0] [0]です。どうして?アイテムを取ると、残りの容量は3 - 3 = 0になり、残りのアイテムは最初のアイテムになります。さて、 Table [0] [0]が容量を0にして最初のアイテムしか持っていなかった場合に得られる最大値を保存していることを思い出してください。ここでアイテムを選択しないと、取得できる最大値は1ステップ上の値、つまり1です。今、我々はこれら2つの値の最大取る(4、1)および表を設定する[1] [2] = 4。 表[1] [4]では、 4であるため、最大ナップザック能力は3より大きく、現在のアイテムの重さ、2つのオプションがあります。我々は、MAX( 重量[2] + 表[0] [4-重量[2]、 表[0] [4])= MAX( 重量[2] +表[0] [1]、 表[0]を取ります[4])= MAX(4 + 1、1)= 5。

if weight[i] <= j
    w := weight[i]
    Table[i][j] := max(w + Table[i][j-w], Table[i-1][j])
end if

これらの2つの公式を使用して、 テーブル配列全体に値を設定できます。私たちの配列は次のようになります:

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 | 1 | 1 | 4 | 5 | 5 | 5 | 5 |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 | 1 | 1 | 4 | 5 | 6 | 6 | 9 |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 | 1 | 1 | 4 | 5 | 7 | 8 | 9 |
+-------+--------+---+---+---+---+---+---+---+---+

ここで、配列[3] [7]に挿入した最後の値には、必要な最大値が含まれています。これは、 4つのアイテムがあり、ナップザックの最大容量が7だった場合に得られる最大値です。

ここでは、最初の行であっても、重さはナップザックの能力よりも大きくなることを覚えておく必要があります。最初の行を塗りつぶしている間に値をチェックするための別の制約を維持する必要があります。あるいは、単に別の行をとり、最初の行のすべての値を0に設定することができます 。疑似コードは次のようになります。

Procedure Knapsack(Weight, Value, maxCapacity):
n := Item.size - 1
Table[n+1][maxCapacity+1]
for i from 0 to n
    Table[i][0] := 0
end for
for j from 1 to maxCapacity
    if j >= Weight[0]
        Table[0][j] := Weight[0]
    else
        Table[0][j] := 0
    end if
end for
for i from 1 to n
    for j from 1 to maxCapacity
        if Weight[i] >= j                                            //can't pick the item
            Table[i][j] := Table[i-1][j]        
        else                                                        //can pick the item
            w := Weight[i]
            Table[i][j] := max(w + Table[i-1][j-w], Table[i-1][j])
        end if
    end for
end for
Return Table[n][maxCapacity]

このアルゴリズムの時間複雑度はO(n*maxCapacity)であり、ここでnは項目の数であり、 maxCapacityはナップザックの最大容量である。

これまでの例では、最大の価値を見出しました。 1つの質問はまだ残っています。実際の商品とは何ですか?私たちはテーブル配列の値を調べて、私たちが取ったアイテムを見つけ出します。私たちは2つの戦略に従います:

  • いずれのアイテムについても、上記の位置から値が来ている場合、現在のアイテムは取得しませんでした。私たちは上記の1つのステップに進みます。
  • 値が上記の位置から来ていない場合、私たちはアイテムを取った。だから、xは現在のアイテムの重みです。

疑似コードは次のようになります。

Procedure printItems(Table, maxCapacity, Value):
i := Item.size - 1
j := maxCapacity
while j is not equal to 0
    if Table[i][j] is equal to Table[i-1][j]
        i := i - 1
    else
        Print: i
        j := j - weight[i]
        i := i - 1
    end if
end while

私たちの例を遡ると、次のようになります:

後退アレイ

これから、最大値を得るために項目23を取ることができると言うことができます。



Modified text is an extract of the original Stack Overflow Documentation
ライセンスを受けた CC BY-SA 3.0
所属していない Stack Overflow