ナップサック問題

ナップサック問題（ナップサックもんだい、英: Knapsack problem）は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、n 種類の品物（各々、価値 v_i、重量 w_i）が与えられたとき、重量の合計が W を超えない範囲で品物のいくつかをナップサックに入れて、その入れた品物の価値の合計を最大化するには入れる品物の組み合わせをどのように選べばよいか」という整数計画問題である。同じ種類の品物を1つまでしか入れられない場合（x_i ∊ {0, 1}）や、同じ品物をいくつでも入れてよい場合（x_i は0以上の整数）など、いくつかのバリエーションが存在する。

ナップサック問題

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

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

定義

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

${\displaystyle {\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}}}$ 

ここで、${\displaystyle x_{i}}$  はナップサックへ入れる品物の個数を表している。

0-1 ナップサック問題

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

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

${\displaystyle {\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}}}$ 

解法について

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

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

${\displaystyle 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}}}$ 

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

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

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

array ${\textstyle V[0\ldots n,0\ldots W]}$ ;

${\displaystyle n\leftarrow |I|}$ 

for ${\displaystyle w\leftarrow 0}$  to ${\displaystyle W}$  do　${\displaystyle V[0,w]\leftarrow 0}$ 　end for

for ${\displaystyle i\leftarrow 1}$  to n do　${\displaystyle V[i,0]\leftarrow 0}$ 　end for

for ${\displaystyle i\leftarrow 1}$  to n do

　 for ${\displaystyle w\leftarrow 0}$  to ${\displaystyle W}$  do

　　　 if ${\displaystyle w_{i}>w}$  then　${\displaystyle V[i,w]\leftarrow V[i-1,w]}$ 

　　　　　　　　　else　${\displaystyle V[i,w]\leftarrow \max(V[i-1,w],V[i-1,w-w_{i}]+v_{i})}$ 

　　　end if

　end for

end for

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)
}

類似の問題

→詳細は「ナップサック問題のリスト（英語版）」を参照

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

多目的ナップサック問題

今、（ナップサック内に詰めた品物の総価値の最大化のような）単一の目的関数の代わりに、複数の目的関数が与えられた問題について考える。例として、経済的目標に加えて環境あるいは社会的な目標についても同時に取り組むことが考えられる。このような事例はポートフォリオや物流ロジスティクス最適化において発生することが多い^[1][2]。

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

多次元ナップサック問題

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

多次元ナップサック問題は単純なナップサック問題と比べても難しい問題とされており、ベクトルの次元数 ${\displaystyle D=2}$  においても、P${\displaystyle =}$ NP でない限り、EPTAS（英語版）は存在しないことが知られている^[3]。しかしながら、重みベクトルが疎な問題に対しては効率良く解くことができるアルゴリズムが知られている^[4]。ここで重みベクトルが疎な問題の定義として、${\displaystyle m<D}$  を満たす集合 ${\displaystyle J=\{1,2,\ldots ,m\}}$  が与えられているとし、ある ${\displaystyle \exists z>m}$  が存在し、各品物 ${\displaystyle i}$  が ${\displaystyle \forall j\in J\cup \{z\},\ w_{ij}\geq 0}$ 、${\displaystyle \forall y\notin J\cup \{z\},w_{iy}=0}$  を満たすように重みベクトルが与えられているとする。このような問題例は、中継ノードを持つ無線ネットワークにおけるパケットのスケジューリング問題で用いられている^[4]。またこのアルゴリズムは疎な多次元選択ナップサック問題に対しても適用することができる^[4]。

複数ナップサック問題

今、複数のナップサックが存在していると仮定する。各ナップサックに詰められる容量は異なっていると想定する。複数ナップサック問題はオペレーションズリサーチにおいて詰め込み問題やスケジューリング問題で応用されており、多項式時間近似スキームの存在が知られている^[5]。また複数ナップサック問題はビンパッキング問題に類似した問題である。両者の違いについてはビンパッキング問題は選択したアイテムはすべて同じビンに詰めなければならないのに対し、複数ナップサック問題は選択したアイテムは一部のみをナップサックに詰めることも許容されていることが挙げられる。

二次ナップサック問題

二次ナップサック問題は目的関数が二次のナップサック問題であり、制約条件はバイナリあるいは線形の制約が与えられる問題である ^[6]。二次ナップサック問題は1980年に Gallo、Hammer、Simeone によって提案された問題である^[7]。しかしながら、1975年には Witzgall によって考察されていたことが知られている^[8]。

幾何的

幾何的ナップサック問題は長方形を形どったナップサック内にそれぞれ異なった価値を持った長方形を形どった品物を詰めることを考え、ナップサック内に詰めるアイテムの総価値が最大となるように詰める問題である^[9]。

オンライン

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

Han、Kawase、Makino は非重み型除去不可能オンラインナップサック問題に対する 競合比が 2 のランダムアルゴリズムを提案し、最良のアルゴリズムとして知られている^[10]。重み型除去可能オンラインナップサック問題に対しては競合比 2 のアルゴリズムおよびランダムアルゴリズムにおける競合比の下界が ~1.368 であることと、決定性アルゴリズムにおいて定数の競合比を持つアルゴリズムは存在し得ないことが証明されている。非重み型除去可能オンラインナップサック問題に対しては競合比 10/7 のアルゴリズムおよび 競合比の下界が 1.25 であることが知られている。

オンラインナップサック問題に対する研究は他にも数多く知られている^[11][12][13]。

脚注

[脚注の使い方]

1. ^ Chang, T. J., et al. Heuristics for Cardinality Constrained Portfolio Optimization. Technical Report, London SW7 2AZ, England: The Management School, Imperial College, May 1998
2. ^ Chang, C. S., et al. "Genetic Algorithm Based Bicriterion Optimization for Traction Substations in DC Railway System." In Fogel [102], 11-16.
3. ^ Kulik, A.; Shachnai, H. (2010). “There is no EPTAS for two dimensional knapsack”. Inf. Process. Lett. 110 (16): 707–712. doi:10.1016/j.ipl.2010.05.031. https://www.cs.technion.ac.il/~hadas/PUB/multi_knap.pdf. 
4. ^ ^{a b c} Cohen, R. and Grebla, G. 2014. "Multi-Dimensional OFDMA Scheduling in a Wireless Network with Relay Nodes". in Proc. IEEE INFOCOM'14, 2427–2435.
5. ^ Chandra Chekuri and Sanjeev Khanna (2005). “A PTAS for the multiple knapsack problem”. SIAM Journal on Computing 35 (3): 713–728. doi:10.1137/s0097539700382820. 
6. ^ Wu, Z. Y.; Yang, Y. J.; Bai, F. S.; Mammadov, M. (2011). “Global Optimality Conditions and Optimization Methods for Quadratic Knapsack Problems”. J Optim Theory Appl 151 (2): 241–259. doi:10.1007/s10957-011-9885-4. 
7. ^ Gallo, G.; Hammer, P. L.; Simeone, B. (1980). “Quadratic knapsack problems”. Combinatorial Optimization. Mathematical Programming Studies. 12. pp. 132–149. doi:10.1007/BFb0120892. ISBN 978-3-642-00801-6 
8. ^ Witzgall, C. (1975). “Mathematical methods of site selection for Electronic Message Systems (EMS)”. NASA Sti/Recon Technical Report N (NBS Internal report) 76: 18321. Bibcode: 1975STIN...7618321W. 
9. ^ Galvez, Waldo; Grandoni, Fabrizio; Ingala, Salvatore; Heydrich, Sandy; Khan, Arindam; Wiese, Andreas (2021). “Approximating Geometric Knapsack via L-packings”. ACM Trans. Algorithms 17 (4): 33:1–33:67. arXiv:1711.07710. doi:10.1145/3473713. https://doi.org/10.1145/3473713. 
10. ^ Han, Xin; Kawase, Yasushi; Makino, Kazuhisa (2015-01-11). “Randomized algorithms for online knapsack problems”. Theoretical Computer Science 562: 395–405. doi:10.1016/j.tcs.2014.10.017. ISSN 0304-3975. https://www.sciencedirect.com/science/article/pii/S0304397514007798. 
11. ^ Han, Xin; Kawase, Yasushi; Makino, Kazuhisa (2014-09-01). “Online Unweighted Knapsack Problem with Removal Cost” (英語). Algorithmica 70 (1): 76–91. doi:10.1007/s00453-013-9822-z. ISSN 1432-0541. https://link.springer.com/article/10.1007/s00453-013-9822-z. 
12. ^ Han, Xin; Kawase, Yasushi; Makino, Kazuhisa; Guo, He (2014-06-26). “Online removable knapsack problem under convex function”. Theoretical Computer Science. Combinatorial Optimization: Theory of algorithms and Complexity 540-541: 62–69. doi:10.1016/j.tcs.2013.09.013. ISSN 0304-3975. 
13. ^ Han, Xin; Kawase, Yasushi; Makino, Kazuhisa; Yokomaku, Haruki (2019-09-22), Online Knapsack Problems with a Resource Buffer, arXiv:1909.10016 

関連項目

• 計算複雑性理論
• 最適化問題
• 複雑性クラス - NP完全、NP困難
• ビンパッキング問題
• Merkle-Hellmanナップサック暗号

外部リンク

• MAXIMUM KNAPSACK
• Dynamic programming 0-1 Knapsack problem
• The Knapsack Problem