Goで0-1ナップサック問題を解く
ナップサック？ナップザック？どちらも見かけるような気がします．
英語ではKnapsack（nˈæpsæk）なのでサックなような気がします．
目的・理由
最近仕事でナップサック問題で解決出来る問題と遭遇した．
仕事全体の中では非常に小さい問題ではあったがアルゴリズムが直接役に立ったことを大変嬉しく思っており，記念に初めて記事を書く．
Goで書くのはGoを書きたいというささやかで非常に素朴なアピールである．
想定読者
未来のわたし
ナップサック問題とは
ナップサック問題には制約によって様々な解法パターンがあるが今回の対象となるのは，もっともオーソドックスな0-1ナップサック問題と呼ばれるケース．
以下に簡単な問題設定を記載する．
容量$W$のナップサック1つと，$N$個の荷物$a_i (1\le i\le N)$がある．
各荷物には重さ$w_i$と価値$v_i$が設定されており，$N$個の荷物からいくつかを選びナップサックに詰め込んでいく．
ただし，ナップサックに入れる荷物の重さの総和は容量$W$以下とならなければならない．
上記の条件を満たすとき一度にナップサックに詰め込める価値の総和の最大値を求める．
各荷物については
- ナップサックに入れる
- ナップサックに入れない
の2通りであるから，0-1ナップサック問題と呼ばれる．これは組合わせ最適化の問題でもある．
これを全通り試そうとすると$2^N$通りのパターンがあり，ナイーブに実装すると$N=40$程度でも現実的な時間では解くことはできない.そこで以下の擬似多項式時間で解くことが可能な動的計画法がよく使われる．
動的計画法による解法
ナップサック問題は多くの場合動的計画法で解かれる．詳細は後回しにするが，先に結果を述べる.
$a_0$から$a_i (0\le i\le N)$までを使って（荷物$a_0$は荷物なしを意味する）容量$j$のナップサックに荷物を詰め込むとき詰め込める価値の総和の最大値を$dp_{i, j} (1\le i\le N, 0\le j \le W)$であるとする．このとき，$dp_{i, j}$は以下の式で与えられる．この$dp_{N, W}$が求めたいナップサック問題の解，容量Wのナップサックに詰め込める価値の総和の最大値である．
\begin{aligned}
dp_{i, j} = \begin{cases}
&\mathrm{max}(dp_{i-1, j}, dp_{i-1, j-w_i}+v_i)\hspace{20px} &(i\gt0, j \ge w_i)\\
& dp_{i-1, j} &(i\gt0, j \lt w_j)\\
& 0 &(i=0)
\end{cases}
\end{aligned}\\
上記の式では，問題サイズを小さくした部分問題の解を記録しそれを利用して解を求めている．
これをもう少しみていく．
${dp}_{i, j}$は荷物$a_i$まで使って容量$j$のナップサックに詰め込める価値の総和の最大値である．
このとき容量$j$のナップサックに荷物$a_{i}$を入れることを考える．
$w_i > j$であるならば，荷物$a_i$を入れることはできないため，入れられる価値の総和の最大値は$a_1$から$a_{i-1}$を使って容量$j$のナッサックにいれられる価値の最大値($=dp_{i-1,j}$)と等しい．
一方で$w_i \le j$である場合は，$a_i$を入れるか入れないかの2パターンが存在しどちらかがこの場合における最大値となる．
まず，入れないときは先ほどと同様に$a_1$から$a_{i-1}$を用いて得られる最大値が値となる．つまり$dp_{i-1, j}$となる．
入れる場合は，$j-w_i$の容量のナップサックに$a_1$から$a_{i-1}$を使ってナップサックに入れられる価値の最大値に$a_i$の価値$v_i$を足したものが値となる．つまり$dp_{i-1, j-w_i} + v_i$となる．
これら2つの値を比較して価値が大きいものを選ぶことになる．
これらを数式にすると上述の更新式になる．初期値として，$i=0$つまり荷物を全く使わないで得られる価値を初期条件としてやると求めたい$dp_{i,j}$を更新式を辿っていけば求めることができる．
計算量としては，時間計算量および空間計算量ともに$\mathrm{O}(NW)$ となる．
空間計算量については，長さ$M+1$の配列2つを再利用すれば$\mathrm{O}(W)$とすることも可能になる．
実装
ちょうどAtCoderのDPまとめコンテストに0-1ナップサック問題があったので，コードの検証および入手力形式はこちらに準じることにした．
このコードでACを取れること確認した．
package main
import (
"fmt"
"math"
)
// mathパッケージのMaxはfloat型しかないためint用にラップしておく
func max(lhs, rhs int) int {
return int(math.Max(float64(lhs), float64(rhs)))
}
func main() {
var (
N, M int64
)
// 入力
fmt.Scanf("%d %d", &N, &M)
values, weights := make([]int64, N), make([]int64, N)
for i := 0; i < N; i++ {
fmt.Scanf("%d %d", &weights[i], &values[i])
}
// 32bitだとオーバーフローする場合があるので64bit
// Goはデフォルトで0で初期化される.
dp := make([][]int64, N+1)
for i := 0; i < N+1; i++ {
dp[i] = make([]int64, M+1)
}
// 動的計画法部分
// 緩和式にしたがって値を更新していく
for i := 1; i <= N; i++ {
for j := int64(0); j <= M; j++ {
dp[i][j] = dp[i-1][j]
if j >= weights[i-1] {
dp[i][j] = max(dp[i][j], dp[i-1][j-weights[i-1]]+values[i-1])
}
}
}
// 出力
fmt.Println(dp[N][M])
}
ちょっとした応用
今までの問題は容量W以下で価値を最大化する問題であったが，更新式を少し変更してやることで重さがちょうどWでもっとも価値が高い組み合わせというものも探せる．最大部分和集合問題を混ぜたような形になる．
$dp_{i, j}$を
dp_{i, j} = \left\{
\begin{array}{ll}
-1 & ((i, j) \neq (0, 0)) \\
0 & ((i, j) = (0, 0)) \\
\end{array}
\right.
で初期化してやり，更新式を以下の様に変更してやると$i$番目までの荷物を用いて重さがちょうど$j$の時の価値の総和の最大値を求めることができる．
dp_{i, j} = \left\{
\begin{array}{ll}
dp_{i-1, j} & (j \lt w_i\ \mathrm{and}\ dp_{i-1, j}\ge 0\ \mathrm{and}\ dp_{i-1, j-w_i}\lt 0) \\
dp_{i-1, j-w_i} + v_i & (j \lt w_i\ \mathrm{and}\ dp_{i-1, j}\lt 0\ \mathrm{and}\ dp_{i-1, j-w_i}\ge 0) \\
\mathrm{max}(dp_{i-1, j}, dp_{i-1, j-w_i}+v_i) & (j \lt w_i\ \mathrm{and}\ dp_{i-1, j}\ge 0\ \mathrm{and}\ dp_{i-1, j-w_i}\ge 0) \\
\end{array}
\right.
この式だと$dp_{N, W}=-1$の場合もある（すなわちどのような組み合わせを使ってもちょうど$W$の重さにならない）．
この場合の問題設定としては価値が一番大事な要素ではなく，総計重量と容量の差が小さいことが一番大事で同じ重さを実現する組み合わせの中でどれを選ぶかを価値の総和に基づいて判断するような形になる．
こちらもGoで実装してみる．ここではどの組み合わせになるのかを確認するためのトレースバックも追加している．
package main
import "fmt"
import "math"
func max(lhs, rhs int64) int64 {
return int64(math.Max(float64(lhs), float64(rhs)))
}
// Route トレースバック用のpair
type Route struct {
x, y int
}
func main() {
var (
N, M int
)
fmt.Scanf("%d %d", &N, &M)
values, weights := make([]int64, N), make([]int, N)
for i := 0; i < N; i++ {
fmt.Scanf("%d %d", &weights[i], &values[i])
}
dp := make([][]int64, N+1)
// トレースバック用のテーブル
trace := make([][]Route, N+1)
for i := 0; i < N+1; i++ {
dp[i] = make([]int64, M+1)
trace[i] = make([]Route, M+1)
}
// 初期化
for i := 0; i <= N; i++ {
for j := 1; j <= M; j++ {
dp[i][j] = -1
}
}
dp[0][0] = 0
// traceにはどこの(i, j)から来たかの情報を保持させる
for i := 1; i <= N; i++ {
for j := 0; j <= M; j++ {
if dp[i-1][j] >= 0 {
dp[i][j] = dp[i-1][j]
trace[i][j] = Route{i - 1, j}
}
if j >= weights[i-1] && dp[i-1][j-weights[i-1]] >= 0 && dp[i][j] < dp[i-1][j-weights[i-1]]+values[i-1] {
dp[i][j] = dp[i-1][j-weights[i-1]] + values[i-1]
trace[i][j] = Route{i - 1, j - weights[i-1]}
}
}
}
// 出力
fmt.Println(dp[N][M])
// DPテーブルの確認
fmt.Println(dp)
pnt := Route{N, M}
routes := []Route{}
res := []int{}
// トレースバック
for pnt.x != 0 {
routes = append(routes, pnt)
pre := pnt
pnt = trace[pnt.x][pnt.y]
// 異なる重さのところから値が来ている場合は荷物iを追加したとき
if pre.y != pnt.y {
res = append(res, pre.x)
}
}
fmt.Println(routes)
// 重さがWになるときのベストな荷物の組み合わせの出力
fmt.Println(res)
}
終わりに
Goを書きたいといったが，競技プログラミングでGoを使うのは中々骨が折れるなと感じた．暗黙の型変換を少しもしてくれないので，forループのj:=0がint32型だとint64型の数値との比較j>weits[i-1]ですらキャストをしないといけないのは，競技プログラミングみたいなのだと多少面倒臭い．
一方で業務で使うのには安心感があるだろうなという直観も生えた．