動的計画法

蟻本を読んで動的計画法を学んだので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に対しては解けません。