動的計画法

蟻本を読んで動的計画法を学んだのでGo言語で復習してみます。

ナップサック問題

重さと価値がそれぞれw_i, v_iであるようなn個の品物があります。これらの品物から、重さの総和がWを超えないように選んだときの、価値の総和の最大値を求めなさい。

n = 4
(w, v) = {(2, 3), (1, 2), (3, 4), (2, 2)}
W = 5

7

全探索

まずは全探索で解いてみます。

package main

import "fmt"

var (
	n, W int
	w, v []int
)

func main() {
	// 入力は省略
	fmt.Println(rec(0, W))
}

func rec(i, j int) (res int) {
	if i == n {
		// 品物なし
		res = 0
	} else if j < w[i] {
		// 重量オーバー
		res = rec(i+1, j)
	} else {
		// 品物を入れるか入れないか試す
		if rec(i+1, j) < rec(i+1, j-w[i])+v[i] {
			res = rec(i+1, j-w[i]) + v[i]
		} else {
			res = rec(i+1, j)
		}
	}
	return
}

2回の分岐が全ての深さで行われるので計算量はO(n^2)です。これでは大きなnに対しては解けません。

探索のメモ化

全探索ではrec(3,2)を複数回実行する場面がありました。なので同じ処理を省力できるように実行結果をメモします。

package main

import "fmt"

var (
	n, W int
	w, v []int
	dp   [][]int //メモ化テーブル
)

func main() {
	// 入力は省略
	dp = make([][]int, n+1)
	for i := 0; i <= n; i++ {
		for j := 0; j <= W; j++ {
			dp[i] = append(dp[i], -1)
		}
	}
	fmt.Println(rec(0, W))
}

func rec(i, j int) (res int) {
	if dp[i][j] >= 0 {
		return dp[i][j]
	}
	if i == n {
		// 品物なし
		res = 0
	} else if j < w[i] {
		// 重量オーバー
		res = rec(i+1, j)
	} else {
		// 品物を入れるか入れないか試す
		if rec(i+1, j) < rec(i+1, j-w[i])+v[i] {
			res = rec(i+1, j-w[i]) + v[i]
		} else {
			res = rec(i+1, j)
		}
		dp[i][j] = res
	}
	return
}

メモ化をすることにより同じ引数については最初の一回しか再帰処理を行わなくなります。また引数の組み合わせは高々n*W通りしかないので計算量はO(nW)となります。

参考文献

アルゴリズム