题目

leetcode:416

代码与解析

背包问题

carl: 背包问题01
carl:背包问题 滚动数组法

题目解析

讲解最清晰版
官方视频题解

动归五部曲

  • 确定dp数组下标及含义

在01背包中,dp[j] 表示: 容量为j的背包,所背的物品价值最大可以为dp[j]。dp[i][j]

套到本题,dp[j]表示 背包总容量是j,最大可以凑成j的子集总和为dp[j], dp[i]为每一个元素。

  • 确定递推公式
dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i])


  • dp数组初始化

这里采用二维数组,初始化的话,第一列初始化为零,每一行要看j是否大于nums[i], 装不下的话,当前格就不能装。

if j<nums[i]{
    dp[i][j] = dp[i-1][j]
}else{
    dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i])
}
  • 确定遍历顺序

遍历顺序的话,从前往后遍历,可以先遍历背包,也可先遍历物品

  • 举例推导dp数组

[
[0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 5 5 5 5 5 5 5]
[0 0 0 0 0 5 5 5 5 5 5 11]
[0 0 0 0 0 5 5 5 5 5 10 11]
]

func canPartition(nums []int) bool {
    target := sum(nums)
    if target%2 !=0{
        return false
    }
    target = target/2
    dp := make([][]int, len(nums))
    for i:=0;i<len(nums);i++{
        dp[i] = make([]int, target+1)
        dp[i][0] = 0
    }
    // fmt.Println(dp)
    for i:=1;i<len(nums);i++{
        for j:=0;j<=target; j++{
            if j<nums[i]{
                dp[i][j] = dp[i-1][j]
            }else{
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i])
            }
        }
    }
    fmt.Println(dp)
    return dp[len(nums)-1][target] == target
}
func sum(nums []int)int{
    temp := 0
    for _, v :=range nums{
        temp += v
    }
    return temp
}

滚动数组版本

func sum(nums []int)int{
    temp := 0
    for _, v :=range nums{
        temp += v
    }
    return temp
}
func max(m, n int)int{
    if m>n{
        return m
    }
    return n
}
func canPartition(nums []int) bool{
    target := sum(nums)
    if target%2 !=0{
        return false
    }
    target = target/2
    dp := make([]int, target+1)
    for i:=1;i<len(nums);i++{
        for j:=target;j>=nums[i];j--{
            dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])
        }
    }
    // fmt.Println(dp)
    return dp[target]==target
}
分类: 算法

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

ICP备案号: 辽ICP备20003309号