ナップサック問題のソースを表示

{{出典の明記|date=2016年9月}}
[[画像:Knapsack.svg|thumb|right|ナップサック問題]]
'''ナップサック問題'''（ナップサックもんだい、{{Lang-en-short|Knapsack problem}}）は、[[計算複雑性理論]]における計算の難しさの議論の対象となる問題の一つで、{{Mvar|n}} 種類の品物（各々、価値 {{Math|''v''<sub>''i''</sub>}}、重量 {{Math|''w''<sub>''i''</sub>}}）が与えられたとき、重量の合計が {{Mvar|W}} を超えない範囲で品物のいくつかを[[リュックサック|ナップサック]]に入れて、その入れた品物の価値の合計を最大化するには入れる品物の組み合わせをどのように選べばよいか」という[[整数計画問題]]である。同じ種類の品物を1つまでしか入れられない場合（{{Math|''x''<sub>''i''</sub> ∊ {0, 1}}}）や、同じ品物をいくつでも入れてよい場合（{{Mvar|''x''<sub>''i''</sub>}} は0以上の整数）など、いくつかのバリエーションが存在する。

[[決定問題]]としてのナップサック問題は、「{{Math|''W'', ''v''<sub>''i''</sub>, ''w''<sub>''i''</sub>}} のほかに価値の合計の目標 {{Mvar|V}} が与えられたとき、重量の合計が {{Mvar|W}} 以内でナップサック内の品物の価値の合計が {{Mvar|V}} 以上になるような品物の選び方が存在するか」を判定することである。
全ての品物について {{Math|1=''v''<sub>''i''</sub> = ''w''<sub>''i''</sub>}} である場合は、[[部分和問題]]と等価であるため、ナップサック問題は部分和問題の一般化である。ナップサック問題は、（部分和問題もそうであるが）[[NP困難]]と呼ばれる問題のクラスに属する。なお、部分和問題は同時に[[NP完全問題|NP完全]]（[[NP]]かつNP困難）と呼ばれるクラスにも属する。

解法として、[[動的計画法]]を用いた[[擬多項式時間アルゴリズム]]や [[多項式時間近似スキーム#決定的|FPTAS]] の存在が知られており、実用的にはほぼ最適な解が得られる。

== 定義 ==
<math>I=\{1,2,\cdots,N\}</math> を品物の集合とし、各品物 <math>i \in I</math> の重みを<math>w_i</math>、価値を <math>v_i</math>、品物の重量の合計の上限を <math>W</math> とするとき、次のようにあらわされるものをナップサック問題という。

: <math>
  \begin{array}{lll}
    \max & \sum_{i \in I}v_i x_i & \\
    \mathrm{s.t.} & \sum_{i \in I} w_i x_i \leq W & \\
    & x_i \in \mathbb{N} & (\forall i \in I)
  \end{array}
  </math>

ここで、<math>x_i</math> はナップサックへ入れる品物の個数を表している。

== 0-1 ナップサック問題 ==
ナップサック問題において <math>x_i \in \mathbb{N}</math> という制約を <math>x_i \in \{0, 1\}</math> と制限した問題を '''0-1 ナップサック問題''' という。元のナップサック問題では重量の合計がW以下であれば各品物はいくつでも入れることができたが、この問題の場合は1つまでである。

問題は次のように書かれる。

: <math>
  \begin{array}{lll}
    \max & \sum_{i \in I}v_i x_i & \\
    \mathrm{s.t.} & \sum_{i \in I} w_i x_i \leq W & \\
    & x_i \in \{0,1\} & (\forall i \in I)
  \end{array}
  </math>

=== 解法について ===
この問題は、もしも全数探索を行えば「品物を選ぶ・選ばない」の2通りの選択肢を品物の個数分だけ試すことになり、その計算量は <math>O(2^{|I|})</math> になる。しかし、効率の良い[[貪欲法]]による解法が知られており、ここではその解法を示す。

この問題における漸化式は

: <math>
  V(i, w) =
    \begin{cases}
      0 & \text{if } i = 0 \text{ or } w = 0 \\
      V(i - 1, w) & \text{if } w_i > w \\
      \max(V(i-1, w), V(i - 1, w - w_i) + v_i) & \text{otherwise}
    \end{cases}
  </math>

となる。ここで {{Math|''V''(''i'', ''w'')}} の値は重量の合計がｗ以下である場合に、添字がi以下の品物を使って実現できる価値の合計の最大値を表す。この式は

*「1つも品物を選べない」あるいは「最大重量が <math>0</math>」であるときには、詰め込める品物がないので選ばれた品物の価値の合計を <math>0</math> とする
* 品物 <math>i</math> の重さが <math>w</math> を超えている場合は、品物 <math>i</math> は追加できないから、価値の合計は品物の添字の上限が1つ前までのものの価値の最大値になる
* 品物 <math>i</math> の重さが <math>w</math> を越えていない場合には、品物 <math>i</math> を追加しない場合と追加をする場合の価値の最大値の両方のうちで、小さくない方の値にする

ということを表している。擬似コードは次の通り。価値の合計の最大値は {{Math|''V''({{!}}''I''{{!}}, ''W'')}} として得られる。さらに選んだ品物の列挙をするにはコードの追加が要る。

array <math display="inline">V[0\ldots n,0\ldots W]</math>;

<math>n \leftarrow |I|</math>

for <math>w \leftarrow 0</math> to <math>W</math> do　<math>V[0, w] \leftarrow 0</math>　end for

for <math>i \leftarrow 1</math> to n do　<math>V[i, 0] \leftarrow 0</math>　end for

for <math>i \leftarrow 1</math> to n do   

　 for <math>w \leftarrow 0</math> to <math>W</math> do     

　　　 if <math>w_i > w</math> then　<math>          V[i, w] \leftarrow V[i - 1, w]</math>   

　　　　　　　　　else　<math>V[i, w] \leftarrow \max(V[i-1,w], V[i - 1, w - w_i] + v_i)</math> 

　　　end if 

　end for

end for

[[Groovy]] でトップダウンの動的計画法（メモ化再帰）を使ったコードは以下の通り。

<syntaxhighlight lang="groovy">
@Memoized int m(int i, int j) {
    i == 0 ? 0 : Math.max(m(i - 1, j), c[i] <= j ? m(i - 1, j - c[i]) + p[i] : 0)
}
</syntaxhighlight>

== 類似の問題 ==
{{Main|{{仮リンク|ナップサック問題のリスト|en|List of knapsack problems}}}}

ナップサック問題にはクラシカルなナップサック問題から派生した様々な類似の問題が存在している。類似のナップサック問題は品物、目的関数、ナップサックの値を変更したものから考えられている。

=== 多目的ナップサック問題 ===
今、（ナップサック内に詰めた品物の総価値の最大化のような）単一の目的関数の代わりに、複数の目的関数が与えられた問題について考える。例として、経済的目標に加えて環境あるいは社会的な目標についても同時に取り組むことが考えられる。このような事例はポートフォリオや物流ロジスティクス最適化において発生することが多い<ref>Chang, T. J., et al. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.6698&rep=rep1&type=pdf Heuristics for Cardinality Constrained Portfolio Optimization].
Technical Report, London SW7 2AZ, England: The Management School, Imperial College, May 1998</ref><ref>Chang, C. S., et al. "[https://scholarbank.nus.edu.sg/handle/10635/72660 Genetic Algorithm Based Bicriterion Optimization for Traction Substations in DC Railway System]." In Fogel [102], 11-16.</ref>。

また例として、クルーズ船を経営しているとする。そしてクルーズ船に有名な芸能人を何人か呼ぶことを検討しているとする。運航しているクルーズ船は乗客を 1t まで収容することができ、芸能人を呼び寄せるための費用を100000円未満に抑える必要がある。呼び寄せる候補の芸能人にはそれぞれ体重、人気度（集客力）、費用が異なっていると想定する。上記の例では、複数の目的関数が与えられていると考えることができ、呼び寄せた芸能人の人気度の総和を最大化することとそれにかかる費用をできるだけ抑えることを同時に考慮しなければならない。

=== 多次元ナップサック問題 ===
今、ナップサックに詰める品物 <math>i</math> について D-次元ベクトルの重み <math>\overline{w_i}=(w_{i1},\ldots,w_{iD})</math> およびナップサックの容量を表した D-次元ベクトル <math>(W_1,\ldots,W_D)</math> が与えられているとする。多次元ナップサック問題の目的としてはナップサックに詰めた各品物の各重みの総和がナップサックの容量 <math>W_d</math> をそれぞれ超えない中で詰めた品物の総価値を最大にするような詰め方を考える問題である。

多次元ナップサック問題は単純なナップサック問題と比べても難しい問題とされており、ベクトルの次元数 <math>D=2</math> においても、P<math>=</math>NP でない限り、{{仮リンク|EPTAS|en|EPTAS}}は存在しないことが知られている<ref>{{cite journal |last1=Kulik |first1=A. |last2=Shachnai |first2=H. |author2-link=:en:Hadas Shachnai |year=2010 |title=There is no EPTAS for two dimensional knapsack |url=https://www.cs.technion.ac.il/~hadas/PUB/multi_knap.pdf |journal=Inf. Process. Lett. |volume=110 |issue=16 |pages=707–712 |doi=10.1016/j.ipl.2010.05.031 |citeseerx=10.1.1.161.5838 }}</ref>。しかしながら、重みベクトルが疎な問題に対しては効率良く解くことができるアルゴリズムが知られている<ref name=CohenGrebla>Cohen, R. and Grebla, G. 2014. [http://wimnet.ee.columbia.edu/wp-content/uploads/2013/03/paper_short.pdf "Multi-Dimensional OFDMA Scheduling in a Wireless Network with Relay Nodes"]. in ''Proc. IEEE INFOCOM'14'', 2427–2435.</ref>。ここで重みベクトルが疎な問題の定義として、<math>m<D</math> を満たす集合 <math>J=\{1,2,\ldots,m\}</math> が与えられているとし、ある <math> \exists z>m</math> が存在し、各品物 <math>i</math> が <math>\forall j\in J\cup \{z\},\ w_{ij}\geq 0</math>、<math>\forall y\notin J\cup\{z\}, w_{iy}=0</math> を満たすように重みベクトルが与えられているとする。このような問題例は、中継ノードを持つ無線ネットワークにおけるパケットのスケジューリング問題で用いられている<ref name=CohenGrebla/>。またこのアルゴリズムは疎な多次元選択ナップサック問題に対しても適用することができる<ref name=CohenGrebla/>。

=== 複数ナップサック問題 ===
今、複数のナップサックが存在していると仮定する。各ナップサックに詰められる容量は異なっていると想定する。複数ナップサック問題はオペレーションズリサーチにおいて詰め込み問題やスケジューリング問題で応用されており、[[多項式時間近似スキーム]]の存在が知られている<ref>{{Cite journal |last=Chandra Chekuri and Sanjeev Khanna |date=2005 |title=A PTAS for the multiple knapsack problem |journal=SIAM Journal on Computing |volume=35 |issue=3 |pages=713–728 |citeseerx=10.1.1.226.3387 |doi=10.1137/s0097539700382820 }}</ref>。また複数ナップサック問題は[[ビンパッキング問題]]に類似した問題である。両者の違いについてはビンパッキング問題は選択したアイテムはすべて同じビンに詰めなければならないのに対し、複数ナップサック問題は選択したアイテムは一部のみをナップサックに詰めることも許容されていることが挙げられる。

=== 二次ナップサック問題 ===
二次ナップサック問題は目的関数が二次のナップサック問題であり、制約条件はバイナリあるいは線形の制約が与えられる問題である
<ref name="QKP">{{cite journal | title = Global Optimality Conditions and Optimization Methods for Quadratic Knapsack Problems |author1=Wu, Z. Y. |author2=Yang, Y. J. |author3=Bai, F. S. |author4=Mammadov, M. | journal = J Optim Theory Appl | year = 2011 | volume = 151 |issue=2 | pages = 241&ndash;259 | doi = 10.1007/s10957-011-9885-4 |s2cid=31208118 }}</ref>。二次ナップサック問題は1980年に Gallo、Hammer、Simeone によって提案された問題である<ref>{{cite book | chapter = Quadratic knapsack problems |author1=Gallo, G. |author2=Hammer, P. L. |author3=Simeone, B. | title = Combinatorial Optimization |series= Mathematical Programming Studies | year = 1980 | volume = 12 | pages = 132&ndash;149 | doi = 10.1007/BFb0120892 |isbn=978-3-642-00801-6 }}</ref>。しかしながら、1975年には Witzgall によって考察されていたことが知られている<ref>{{cite journal | title = Mathematical methods of site selection for Electronic Message Systems (EMS) | author = Witzgall, C. | journal = NASA Sti/Recon Technical Report N | publisher = NBS Internal report | year = 1975| volume = 76 | page = 18321 | bibcode = 1975STIN...7618321W }}</ref>。

=== 幾何的 ===
幾何的ナップサック問題は長方形を形どったナップサック内にそれぞれ異なった価値を持った長方形を形どった品物を詰めることを考え、ナップサック内に詰めるアイテムの総価値が最大となるように詰める問題である<ref>{{Cite journal|last1=Galvez|first1=Waldo|last2=Grandoni|first2=Fabrizio|last3=Ingala|first3=Salvatore|last4=Heydrich|first4=Sandy|last5=Khan|first5=Arindam|last6=Wiese|first6=Andreas|date=2021|title=Approximating Geometric Knapsack via L-packings|url=https://doi.org/10.1145/3473713|pages=33:1–33:67|doi=10.1145/3473713|journal = ACM Trans. Algorithms|volume=17 |issue=4 |arxiv=1711.07710}}</ref>。

=== オンライン ===
オンラインナップサック問題はナップサックに詰める品物が一つ一つ与えられるような問題である。各品物が順番に与えられたとき、その品物をナップサックに詰めるか詰めないかを決定するような問題である。オンラインナップサック問題は二つの問題に分類でき、一つは除去不可能オンラインナップサック問題で、一度ナップサックに詰めた品物はそれ以降除去することができない問題であり、二つ目は除去可能オンラインナップサック問題で、ナップサックに詰めた品物を後から除去すること可能な問題である。

Han、Kawase、Makino は非重み型除去不可能オンラインナップサック問題に対する 競合比が 2 のランダムアルゴリズムを提案し、最良のアルゴリズムとして知られている<ref>{{Cite journal |last1=Han |first1=Xin |last2=Kawase |first2=Yasushi |last3=Makino |first3=Kazuhisa |date=2015-01-11 |title=Randomized algorithms for online knapsack problems |url=https://www.sciencedirect.com/science/article/pii/S0304397514007798 |journal=Theoretical Computer Science |volume=562 |pages=395–405 |doi=10.1016/j.tcs.2014.10.017 |issn=0304-3975}}</ref>。重み型除去可能オンラインナップサック問題に対しては競合比 2 のアルゴリズムおよびランダムアルゴリズムにおける競合比の下界が ~1.368 であることと、決定性アルゴリズムにおいて定数の競合比を持つアルゴリズムは存在し得ないことが証明されている。非重み型除去可能オンラインナップサック問題に対しては競合比 10/7 のアルゴリズムおよび 競合比の下界が 1.25 であることが知られている。 

オンラインナップサック問題に対する研究は他にも数多く知られている<ref>{{Cite journal |last1=Han |first1=Xin |last2=Kawase |first2=Yasushi |last3=Makino |first3=Kazuhisa |date=2014-09-01 |title=Online Unweighted Knapsack Problem with Removal Cost |url=https://link.springer.com/article/10.1007/s00453-013-9822-z |journal=Algorithmica |language=en |volume=70 |issue=1 |pages=76–91 |doi=10.1007/s00453-013-9822-z |issn=1432-0541}}</ref><ref>{{Cite journal |last1=Han |first1=Xin |last2=Kawase |first2=Yasushi |last3=Makino |first3=Kazuhisa |last4=Guo |first4=He |date=2014-06-26 |title=Online removable knapsack problem under convex function |journal=Theoretical Computer Science |series=Combinatorial Optimization: Theory of algorithms and Complexity |volume=540-541 |pages=62–69 |doi=10.1016/j.tcs.2013.09.013 |issn=0304-3975|doi-access=free }}</ref><ref>{{Citation |last1=Han |first1=Xin |title=Online Knapsack Problems with a Resource Buffer |date=2019-09-22 |arxiv=1909.10016 |last2=Kawase |first2=Yasushi |last3=Makino |first3=Kazuhisa |last4=Yokomaku |first4=Haruki}}</ref>。

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

==関連項目==
*[[計算複雑性理論]]
*[[最適化問題]]
*[[複雑性クラス]] - [[NP完全]]、[[NP困難]]
*[[ビンパッキング問題]]
*[[Merkle-Hellmanナップサック暗号]]

==外部リンク==
*[http://www.nada.kth.se/~viggo/wwwcompendium/node211.html MAXIMUM KNAPSACK]
*[http://cse.unl.edu/~goddard/Courses/CSCE310J/Lectures/Lecture8-DynamicProgramming.pdf Dynamic programming 0-1 Knapsack problem]
*[https://www.utdallas.edu/~scniu/OPRE-6201/documents/DP3-Knapsack.pdf The Knapsack Problem]

{{デフォルトソート:なつふさつくもんたい}}
[[Category:計算複雑性理論]]
[[Category:数学に関する記事]]
[[Category:組合せ最適化]]
[[Category:数学の問題]]