ナップサック問題 ナップサック問題 （ナップサックもんだい、Knapsack problem）は、計算複雑性理論 における計算の難しさの議論の対象となる問題の一つで、n 種類の品物（各々、価値 v i w i W を超えない範囲で品物のいくつかをナップサック に入れて、その入れた品物の価値の合計を最大化するには入れる品物の組み合わせをどのように選べばよいか」という整数計画問題 である。同じ種類の品物を1つまでしか入れられない場合（x i x i
決定問題 としてのナップサック問題は、「W , v i w i V が与えられたとき、重量の合計が W 以内でナップサック内の品物の価値の合計が V 以上になるような品物の選び方が存在するか」を判定することである。
全ての品物について v i w i 部分和問題 と等価であるため、ナップサック問題は部分和問題の一般化である。ナップサック問題は、（部分和問題もそうであるが）NP困難 と呼ばれる問題のクラスに属する。なお、部分和問題は同時にNP完全 (NP かつNP困難)と呼ばれるクラスにも属する。
解法として、動的計画法 を用いた擬多項式時間アルゴリズム や FPTAS の存在が知られており、実用的にはほぼ最適な解が得られる。
I
=
{
1
,
2
,
⋯
,
N
}
{\displaystyle I=\{1,2,\cdots ,N\}}
i
∈
I
{\displaystyle i\in I}
w
i
{\displaystyle w_{i}}
v
i
{\displaystyle v_{i}}
W
{\displaystyle W}
max
∑
i
∈
I
v
i
x
i
s
.
t
.
∑
i
∈
I
w
i
x
i
≤
W
x
i
∈
N
(
∀
i
∈
I
)
{\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}}}
ここで、
x
i
{\displaystyle x_{i}}
ナップサック問題において
x
i
∈
N
{\displaystyle x_{i}\in \mathbb {N} }
x
i
∈
{
0
,
1
}
{\displaystyle x_{i}\in \{0,1\}}
0-1 ナップサック問題 という。元のナップサック問題では重量の合計がW以下であれば各品物はいくつでも入れることができたが、この問題の場合は1つまでである。
問題は次のように書かれる。
max
∑
i
∈
I
v
i
x
i
s
.
t
.
∑
i
∈
I
w
i
x
i
≤
W
x
i
∈
{
0
,
1
}
(
∀
i
∈
I
)
{\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通りの選択肢を品物の個数分だけ試すことになり、その計算量は
O
(
2
|
I
|
)
{\displaystyle O(2^{|I|})}
貪欲法 による解法が知られており，ここではその解法を示す。
この問題における漸化式は
V
(
i
,
w
)
=
{
0
if
i
=
0
or
w
=
0
V
(
i
−
1
,
w
)
if
w
i
>
w
max
(
V
(
i
−
1
,
w
)
,
V
(
i
−
1
,
w
−
w
i
)
+
v
i
)
otherwise
{\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 )
「1つも品物を選べない」あるいは「最大重量が
0
{\displaystyle 0}
0
{\displaystyle 0}
品物
i
{\displaystyle i}
w
{\displaystyle w}
i
{\displaystyle i}
品物
i
{\displaystyle i}
w
{\displaystyle w}
i
{\displaystyle i}
ということを表している。擬似コードは次の通り。価値の合計の最大値は V (|I |, W )
array
V
[
0
…
n
,
0
…
W
]
{\textstyle V[0\ldots n,0\ldots W]}
n
←
|
I
|
{\displaystyle n\leftarrow |I|}
for
w
←
0
{\displaystyle w\leftarrow 0}
W
{\displaystyle W}
V
[
0
,
w
]
←
0
{\displaystyle V[0,w]\leftarrow 0}
for
i
←
1
{\displaystyle i\leftarrow 1}
V
[
i
,
0
]
←
0
{\displaystyle V[i,0]\leftarrow 0}
for
i
←
1
{\displaystyle i\leftarrow 1}
for
w
←
0
{\displaystyle w\leftarrow 0}
W
{\displaystyle W}
if
w
i
>
w
{\displaystyle w_{i}>w}
V
[
i
,
w
]
←
V
[
i
−
1
,
w
]
{\displaystyle V[i,w]\leftarrow V[i-1,w]}
else
V
[
i
,
w
]
←
max
(
V
[
i
−
1
,
w
]
,
V
[
i
−
1
,
w
−
w
i
]
+
v
i
)
{\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 )
}
![{\textstyle V[0\ldots n,0\ldots W]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9bdc306fa2862205af14e3b75d6f0c7206839e96)
![{\displaystyle V[0,w]\leftarrow 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c99f282cdf1084f4d8e1cc0b411c9ebaf38d6a4)
![{\displaystyle V[i,0]\leftarrow 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b211c63652e6d821b2af4583a43793fcfd9b0ec8)
![{\displaystyle V[i,w]\leftarrow V[i-1,w]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a1cfe8f67ef7bcd3f5982c6c9f112222b0c1bd9d)
![{\displaystyle V[i,w]\leftarrow \max(V[i-1,w],V[i-1,w-w_{i}]+v_{i})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/173f948549fc752048b8c18a9ee8e296ad10e4af)