algorithm dynamic programming

Ltd的算法大抄·动态规划·01背包题目

leetcode:416.1049.494.474

Posted by Ltd on Wednesday, May 10, 2023

这篇主要是01背包问题的题目解析

对应leetcode题目为416.1049.494.474

代码地址https://github.com/Ltd5552/Algorithm/tree/master/8-DP/Bag

  • 对于二维dp数组，遍历的前后顺序和物品容量层次顺序都可以交换，因为二维保留了更多的上下文信息
  • 对于一维dp数组，只能是先遍历物品再遍历容量，而且容量的遍历只能是倒序

416.分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

分析

由于是分割为两个子集，子集元素和要求相等，那么就可以转换为找其中一个子集的元素，使其满足和为sum/2就行，而每个元素只能加一次，所以是01背包问题。

int型

根据之前的理论知识，dp[i]可以定义为当容量为j时能够装入的最大价值（对于这道题而言可以把每个元素的值形象化，数值既是重量又是价值）

判断最后的结果dp[target]是否等于target，若相等那么说明能够找到一些元素使得和为sum/2，剩下的也就是sum/2，所以就分出来了。

这种方式是将能否找到等价地转为了找到需要满足什么条件，再用这个条件来判断。

// 执行耗时:36 ms,击败了26.80% 的Go用户
// 内存消耗:3.5 MB,击败了58.06% 的Go用户
func canPartitionI(nums []int) bool {
	var sum int
	for _, i := range nums {
		sum += i
	}
	if sum%2 != 0 {
		return false
	}
	target := sum / 2
	dp := make([]int, target+1)
	for i := range nums {
		for j := target; j >= nums[i]; j-- {
			dp[j] = utils.Max(dp[j], dp[j-nums[i]]+nums[i])
		}
	}
	return dp[target] == target
}

bool型

将dp[i]定义为当容量为i时能否被填满，bool类型

因为减少了比较，直接使用Bool所以更高效一点

// 执行耗时:16 ms,击败了93.44% 的Go用户
// 内存消耗:2.5 MB,击败了91.63% 的Go用户
func canPartitionII(nums []int) bool {
	var sum int
	for _, i := range nums {
		sum += i
	}
	if sum%2 != 0 {
		return false
	}
	//背包的目标容量
	target := sum / 2
	//dp数组表示的是容量为i时能否被填满
	//这样定义的话需要先有效的初始化
	dp := make([]bool, target+1)
	//使用nums中的第一个元素进行初始化
	for i := 0; i <= target; i++ {
		dp[i] = nums[0] == i
	}
	//从第2个开始，第一个用来初始化了
	for i := 1; i < len(nums); i++ {
		for j := target; j >= nums[i]; j-- {
			//从后往前的遍历，当满足填满条件的话就是true
			dp[j] = dp[j] || dp[j-nums[i]]
		}
	}
	return dp[target]
}

1049.最后一块石头的重量II

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

  • 如果 x == y，那么两块石头都会被完全粉碎；
  • 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

示例 1：

输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

示例 2：

输入：stones = [31,26,33,21,40]
输出：5

提示：

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 100

分析

为何能够转为01背包问题

大概来说就是把原石头看成数值，分为较为均匀的两堆（和的大小差不多），一堆取正号，一堆取负号，这样获得的就是差值最小的

所以就是在背包容量为sum/2的情况下装尽可能多的石头，实际结果可能无法正好是装满sum/2，找到最相近的也就是最大价值的就可以了。

这样一看其实和上一道是类似的，上一题是直接分为确定的一半作为容量看能否装满，这里是对容量为一半的尽量装满，装不满的部分就是差值了也就是最后一块的重量。

int型

同上，dp[j]定义为容量为j的背包最多能装的最大重量，对于石头（元素）重量和价值都是其数值，所以下面递推式中的含义是不同的

// 执行耗时:0 ms,击败了100.00% 的Go用户
// 内存消耗:2 MB,击败了56.24% 的Go用户
func lastStoneWeightII(stones []int) int {
	var sum int
	for _, i := range stones {
		sum += i
	}
	target := sum / 2 //目标的背包容量，向下取整
	dp := make([]int, target+1)
	for i := range stones {
		for j := target; j >= stones[i]; j-- {
            //j-stones[i]减的重量，+stones[i]加的价值
			dp[j] = utils.Max(dp[j], dp[j-stones[i]]+stones[i])
		}
	}
	return sum - 2*dp[target]
}

最后一步是(sum - dp[target]) - dp[target]，因为取target的时候是向下取整的，所以sum - dp[target] >= dp[target]，所以用前者减去后者就是最后一块石头的重量。

bool型

这个和之前的也类似，dp[i]定义为容量为i的背包是否能够装满

// 执行耗时:4 ms,击败了21.50% 的Go用户
// 内存消耗:1.9 MB,击败了97.70% 的Go用户
func lastStoneWeightII(stones []int) int {
	var sum int
	for _, i := range stones {
		sum += i
	}
	target := sum / 2 //目标的背包容量，向下取整
	dp := make([]bool, target+1)
	//初始0为true，以便能够找到装满背包的石子
	dp[0] = true
	for i := range stones {
		for j := target; j >= stones[i]; j-- {
			dp[j] = dp[j] || dp[j-stones[i]]
		}
	}
	for j := target; ; j-- {
		//这里的j不一定是target，是满足使用stones中的石子“装满”j容量条件下和target最近的一个
		if dp[j] {
			return sum - 2*j
		}
	}
}

上面两种dp数组表达的含义不同：

  1. 第一种表示目标容量下能装最多价值的背包，选出的就是固定容量下能装最大价值的背包（不一定是满的），强调最大价值，所以是int类型
  2. 第二种表示能够使用已有石子装满目标容量的背包，选出的是最接近target容量的满背包，强调装满，所以是bool类型

494.目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

  • 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

输入：nums = [1], target = 1
输出：1

提示：

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 1000

分析

这道题就是添加正负号，暴力解法是对每一种情况都枚举出来判断，时间复杂度是2^n，回溯也差不多暴力，这道题主要分析动态规划的方法。

动态规划

这道题一看是区分正负号，和之前的题划分为两堆非常相似，一堆正、一堆负，正负之差就是目标和，关键是确定背包的容量是多少。

这里目标和是已知，总和也已知，两个方程两个未知数很好推导出正/负的多少。（这里的正负我们先不加上符号，只考虑绝对值的多少）

sum = post + neg
post - neg = target
sum = 2*neg + target
neg = (sum - target)/2

由上面的式子可以推导出neg作为背包容量时的大小（以post来装也是一样的）

之前的都是求容量为i的背包最多能装多少，而这里问题就转换为了装满容量为neg的背包有多少种方法，是个排列组合问题

递推公式变为dp[j] += dp[j - nums[i]]，初始化dp[0]=1这样结果才有意义（无需强行解释，带入进去看结果正不正确就行）

// 执行耗时:4 ms,击败了66.47% 的Go用户
// 内存消耗:2.3 MB,击败了51.80% 的Go用户
func findTargetSumWaysII(nums []int, target int) int {
	sum := 0
	for _, num := range nums {
		sum += num
	}
	if (sum-target)%2 != 0 || (sum-target) < 0 {
		return 0
	}
	capacity := (sum - target) / 2
	dp := make([]int, capacity+1)
	dp[0] = 1
	for i := range nums {
		for j := capacity; j >= nums[i]; j-- {
			//dp[j]可以由第j-nums[i]个推出来，由于是获取满足条件的总和，所以是累加操作
			dp[j] += dp[j-nums[i]]
		}
	}
	return dp[capacity]
}

回溯

// 执行耗时:636 ms,击败了6.54% 的Go用户
// 内存消耗:2 MB,击败了84.29% 的Go用户
func findTargetSumWays(nums []int, target int) int {
	count := 0
	var backTrack func(int, int)
	backTrack = func(index, sum int) {
		if index == len(nums) {
			if sum == target {
				count++
			}
			return
		}
		backTrack(index+1, sum+nums[index])
		backTrack(index+1, sum-nums[index])
	}
	backTrack(0, 0)
	return count
}

474.一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

提示：

  • 1 <= strs.length <= 600
  • 1 <= strs[i].length <= 100
  • strs[i] 仅由 '0' 和 '1' 组成
  • 1 <= m, n <= 100

分析

这道题初看不知道怎么下手，但m、n限制0、1的最多个数很像背包容量，这里也是求子集元素最大个数，相当于是要价值最大，越看越像，结果确实也是背包问题，而且是01背包问题。

可以将每一个字符串看成不同的物品，背包容量是二维的形式，更宏观上可以看作是一维的。

定义dp[i][j]为装满i个0和j个1情况下最大子集的大小（元素个数）

递推式dp[i][j] = max(dp[i][j], dp[i-count0][j-count1]+1)

上面的count0和count1对应的是每一个物品（字符串）的0和1的个数。

代码

func findMaxForm(strs []string, m int, n int) int {
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for _, str := range strs {
		count0 := strings.Count(str, "0")
		count1 := strings.Count(str, "1")
		//和一维一样还是倒序遍历，而这两个之间可以交换顺序
		for i := m; i >= count0; i-- {
			for j := n; j >= count1; j-- {
				dp[i][j] = utils.Max(dp[i][j], dp[i-count0][j-count1]+1)
			}
		}
	}
	return dp[m][n]
}

这道题就是对背包容量升了一个维度，本质上和前面的没有任何区别

CATALOG
    FEATURED TAGS
    algorithm binary tree double pointer dynamic programming stack