(30)Go动态规划背包思想求解问题

继上一篇后续《(29)Go动态规划经典思想-01背包问题》https://www.jianshu.com/p/5c54e32cdd49

问题1：分割等和子集 //

是一个典型的背包问题，从某地方抽取元素，填充某个值

设sum为非空集合所有元素的和，若sum%2==0且其中有部分元素的和等于sum/2，
则剩下元素和必定为sum/2

抽象成背包问题则变成：从非空集合中，选出一定元素，填充sum/2的背包,如下图示：

func min(v1, v2 uint8) uint8 {
    if v1 < v2 {
        return v1
    }
    return v2
}

方法1:记忆化搜索
// 时间复杂度O(n^c)
// 空间复杂度O(n*c)
func canPartition(nums []int) bool {
    sum := 0
    n := len(nums)
    for i := 0; i < n; i++ {
        sum += nums[i]
    }

    if sum%2 != 0 {
        return false
    }

    c := sum / 2

    // 0代表未计算,1代表已计算且为true,2代表已计算且为false
    memo := make([][]uint8, n)
    for i := 0; i < n; i++ {
        memo[i] = make([]uint8, c+1)
    }

    return tryPartion(nums, n-1, c, memo)
}

// [0...index]的数字中是否有能否刚好填充容积c的背包
func tryPartion(nums []int, index, c int, memo [][]uint8) (flag bool) {

    if index < 0 || c < 0 {
        //因为index和c都可能小于0,索引越界,这里只能直接返回,不能给memo赋值
        return false
    }

    if memo[index][c] != 0 {
        return memo[index][c] == 1
    }

    if c == 0 {
        flag = true
    } else {
        // 2种情况,只要有1种成立即可
        // 情况1: index位元素不放进c
        flag = tryPartion(nums, index-1, c, memo) ||
            // 情况1: index位元素放进c
            tryPartion(nums, index-1, c-nums[index], memo)
    }

    // 存储计算结果
    if flag {
        memo[index][c] = 1
    } else {
        memo[index][c] = 2
    }
    return
}

方法2: 动态规划--二维数组
// 时间复杂度:O(n*c)
// 空间复杂度O(n*c)
func canPartition2(nums []int) bool {
    n := len(nums)
    if n < 2 {
        return false
    }

    sum := 0
    for i := 0; i < n; i++ {
        sum += nums[i]
    }

    if sum%2 != 0 {
        return false
    }

    c := sum / 2

    // 0代表未计算,1代表已计算且为true,2代表已计算且为false
    memo := make([][]uint8, n)
    for i := 0; i < n; i++ {
        memo[i] = make([]uint8, c+1)
    }

    // i行的情况:依赖i-1行求值
    if nums[0] > c {
        return false
    } else {
        for i := 0; i <= c; i++ {
            if i == nums[0] {
                memo[0][i] = 1
            } else {
                memo[0][i] = 2
            }
        }
    }

    // 第i行的值依靠i-2行,i行的值存在i-1行
    for i := 1; i < n; i++ {
        for j := c; j >= 0; j-- {
            // 情况1
            memo[i][j] = memo[i-1][j]
            // 情况2
            if j >= nums[i] {
                memo[i][j] = min(memo[i][j], memo[i-1][j-nums[i]])
            }
        }
    }
    return memo[n-1][c] == 1
}

方法3: 动态规划--一维优化
// 时间复杂度:O(n*c)
// 空间复杂度O(c)
func canPartition3(nums []int) bool {
    n := len(nums)
    if n < 2 {
        return false
    }

    sum := 0
    for i := 0; i < n; i++ {
        sum += nums[i]
    }

    if sum%2 != 0 {
        return false
    }

    c := sum / 2

    // true表示刚好填满,false无法刚好填满
    memo := make([]bool, c+1)

    //0行情况: nums[0]>c,肯定不成立
    if nums[0] > c {
        return false
    } else {
        memo[nums[0]] = true
    }

    for i := 1; i < n; i++ {
        for j := c; j >= nums[i]; j-- {
            // 2种情况
            // 1)不添加nums[i]能不能填满;2)添加nums[i]能不能填满
            if memo[j] || memo[j-nums[i]] {
                memo[j] = true
            }
        }
    }
    return memo[c]
}

1，2，3提交leetcode，通过

有bug欢迎指出