(29)Go动态规划经典思想-01背包问题

方法1：暴力解法 //
每件物品可以放进包，也可以不放进包，时间复杂度O((2^n)*n)

方法2：动态规划
对于每件物品，都有2种选择，放进包和不放进包，分别计算这两种情况哪种包内的价值更大，取最大值
其状态如下图

根据上图状态可知，容积c和i构成数据对，可以定义一个二维数组来存储相应价值，如下图：

func max(v1, v2 int) int {
    if v1 > v2 {
        return v1
    }
    return v2
}

方法1：记忆化搜索
// 时间复杂度O(n*c)
// 空间复杂度O(n*c)
func knapsack2(w, v []int, c int) int {
    n := len(w)
    if n == 0 {
        return 0
    }

    // (n*(c+1))二维数组
    // memo[i][j]: 将[0...i]号物品,填充容量为j的背包的最大价值
    memo := make([][]int, n)
    for i := 0; i < n; i++ {
        memo[i] = make([]int, c+1)
    }
    return bestValue2(w, v, n-1, c, n, memo)
}

// 将[0...index]号物品,填充容积为C的背包的最大价值
func bestValue2(w, v []int, index, c, n int, memo [][]int) int {
    // 递归终止条件
    if index < 0 || c < 0 {
        return 0
    }

    // 如果计算过价值,直接返回该价值
    if memo[index][c] != 0 {
        return memo[index][c]
    }

    // 计算[0...index]物品放进容量c背包的最大价值

    // 2种情况
    // 情况1: index号物品不放进背包
    res := bestValue2(w, v, index-1, c, n)

    // 情况2: 如果背包有足够的空间,index号物品放进背包
    if c >= w[index] {
        res = max(res, v[index]+bestValue1(w, v, index-1, c-w[index], n))
    }

    // 存储结果
    memo[index][c] = res
    return res
}

根据状态方程得知,memo[i]行价值依赖memo[i-1]行结果,因此可以先求0行结果,
再求1行结果,一步步扩大,最终求出[0...n-1]行所有价值
方法2：动态规划
// 时间复杂度O(n*c)
// 空间复杂度O(n*c)
func knapsack3(w, v []int, c int) int {
    n := len(w)
    if n == 0 {
        return 0
    }

    // (n*(c+1))二维数组
    // memo[i][j]: 将[0...i]号物品,填充容量为j的背包的最大价值
    memo := make([][]int, n)
    for i := 0; i < n; i++ {
        memo[i] = make([]int, c+1)
    }

    // 第0行的情况: 将[0...0]物品存进容量为c的背包
    if w[0] <= c {
        for i := w[0]; i <= c; i++ {
            memo[0][i] = v[0]
        }
    }

    // 第[1...length-1]行的情况
    for i := 1; i < n; i++ {
        // [0...i]物品,j空间
        for j := 0; j <= c; j++ {
            // 2种情况
            // 情况1: index号物品不放进背包
            memo[i][j] = memo[i-1][j]

            // 情况2: 如果背包有足够的空间,index号物品放进背包
            if j >= w[i] {
                memo[i][j] = max(memo[i][j], v[i]+memo[i-1][j-w[i]])
            }
        }
    }
    return memo[n-1][c]
}

由方法2可知：第i行元素只依赖于i-1行元素,理论上,只需要保持两行元素即可求出最后一行价值
偶数行在memo[0],奇数行在memo[1]
方法3：动态规划优化1
// 时间复杂度O(n*c)
// 空间复杂度O(2*c)=O(c)
func knapsack4(w, v []int, c int) int {
    n := len(w)
    if n == 0 {
        return 0
    }

    memo := make([][]int, 2)
    for i := 0; i < 2; i++ {
        memo[i] = make([]int, c+1)
    }

    if w[0] <= c {
        for i := w[0]; i <= c; i++ {
            memo[0][i] = v[0]
        }
    }

    for i := 1; i < n; i++ {
        i1 := i % 2       // 本行
        i2 := (i - 1) % 2 // 上一行
        for j := 0; j <= c; j++ {
            memo[i1][j] = memo[i2][j]
            if j >= w[i] {
                memo[i1][j] = max(memo[i1][j], v[i]+memo[i2][j-w[i]])
            }
        }
    }
    return memo[(n-1)%2][c]
}

由方法3可知：i行素只参考i-1行上方和左边的元素，因此可以从右向左刷新 i 行内容
可以只用一行大小为c+1的数组完成动态规划
方法4：动态规划优化2
// 时间复杂度O(n*c)
// 空间复杂度O(c+1)
func knapsack5(w, v []int, c int) int {
    length := len(w)
    if length == 0 {
        return 0
    }

    // memo[c]: 区间[0...index]的物品,填充容积c的背包的最大价值
    // 空间(c+1)
    memo := make([]int, c+1)

    // 第0行的情况: 将[0...0]物品存进容量为c的背包
    if w[0] <= c {
        for i := w[0]; i <= c; i++ {
            memo[i] = v[0]
        }
    }

    for i := 1; i < length; i++ {
        // i个物品,j空间,当j<w[i]时,小于w[i]值均不变,可以提前结束判断
        for j := c; j >= w[i]; j-- {
            memo[j] = max(memo[j], v[i]+memo[j-w[i]])
        }
    }
    return memo[c]
}

测试4种实现方法的性能：
func main() {
    w := []int{1, 2, 3}
    v := []int{6, 10, 12}
    t := time.Now()
    fmt.Println(knapsack2(w, v, 5))
    fmt.Println("记忆化搜索花费时间", t.Sub(time.Now()))
    fmt.Println("========")

    t = time.Now()
    fmt.Println(knapsack3(w, v, 5))
    fmt.Println("动态规划1花费时间", t.Sub(time.Now()))
    fmt.Println("========")

    t = time.Now()
    fmt.Println(knapsack4(w, v, 5))
    fmt.Println("动态规划2花费时间", t.Sub(time.Now()))
    fmt.Println("========")

    t = time.Now()
    fmt.Println(knapsack5(w, v, 5))
    fmt.Println("动态规划2花费时间", t.Sub(time.Now()))
}

// 测试结果
22
记忆化搜索花费时间 -102.325µs
========
22
动态规划1花费时间 -13.581µs
========
22
动态规划2花费时间 -1.596µs
========
22
动态规划2花费时间 -1.346µs

继下一篇《(30)Go动态规划背包思想求解问题》https://www.jianshu.com/p/2f32ad93ee3e

有bug欢迎指出