本文主要是介绍2024/06/13--代码随想录算法3/17|01背包问题 二维、01背包问题 一维、416. 分割等和子集,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
01背包问题 二维
卡码网链接
动态规划5步曲
- 确定dp数组(dp table)以及下标的含义:dp[i][j] :从下标为[0,i-1]个物品中任取,放进容量为j的背包,价值总和最大为多少。
- 确定递推公式,
有两个方向可以推导出来dp[i][j] :
不放物品i: dp[i][j] = dp[i - 1][j]
放物品i: dp[i][j] = dp[i-1][j-weight[i]] + value[i]
所以递归公式: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);- dp数组如何初始化 【】
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
for (int j = 0 ; j < weight[0]; j++) { // 当然这一步,如果把dp数组预先初始化为0了,这一步就可以省略,但很多同学应该没有想清楚这一点。dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];
}
- 确定遍历顺序【其实从递归公式: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出dp[i][j] 是由左上方数值推导出来了,那么 其他下标初始为什么数值都可以,因为都会被覆盖。】
- 举例推导dp数组
先遍历物品,还是先遍历背包都可以,先遍历物品比较简单
def hanshu():M, bagweight = [int(x) for x in input().split()]weight = [int(x) for x in input().split()]value = [int(x) for x in input().split()]dp = [[0]*(bagweight+1) for i in range(M)] #dp[i][j]代表从物品【0,i-1】让任意取,背包重量j,达到的最大价值#初始化for j in range(weight[0],bagweight+1):dp[0][j] = value[0]for i in range(1, M):for j in range(1, bagweight+1):if j>=weight[i]:dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])else:dp[i][j] = dp[i-1][j]return dp[M-1][bagweight]maxs = hanshu()
print(maxs)
01背包问题 一维(滚动数组)
其实就是遍历物品i的时候,覆盖i-1的结果
动态规划5步曲
- 确定dp数组(dp table)以及下标的含义:dp[j] :容量为j的背包,价值总和最大为dp[i]。
- 确定递推公式,
有两个方向可以推导出来dp[i][j] :
不放物品i: dp[i][j] = dp[i - 1][j]
放物品i: dp[i][j] = dp[i-1][j-weight[i]] + value[i]
所以递归公式:此时dp[j]有两个选择,一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j],即不放物品i,一个是取dp[j - weight[i]] + value[i],即放物品i,指定是取最大的,毕竟是求最大价值,
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
- dp数组如何初始化
- 确定遍历顺序 倒序遍历背包是为了保证物品i只被放入一次!
for(int i = 0; i < weight.size(); i++) { // 遍历物品for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量【倒序】dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}
def test_1_wei_bag_problem():weight = [1, 3, 4]value = [15, 20, 30]bagWeight = 4# 初始化dp = [0] * (bagWeight + 1)for i in range(len(weight)): # 遍历物品for j in range(bagWeight, weight[i] - 1, -1): # 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i])print(dp[bagWeight])test_1_wei_bag_problem()
416. 分割等和子集
力扣链接
要明确本题中我们要使用的是01背包,因为元素我们只能用一次。
回归主题:首先,本题要求集合里能否出现总和为 sum / 2 的子集。
动态规划5步曲
- 确定dp数组(dp table)以及下标的含义:dp[j] :容量为j的背包,价值总和最大为dp[i]。
- 确定递推公式,
有两个方向可以推导出来dp[i][j] :
不放物品i: dp[i][j] = dp[i - 1][j]
放物品i: dp[i][j] = dp[i-1][j-weight[i]] + value[i]
所以递归公式:此时dp[j]有两个选择,一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j],即不放物品i,一个是取dp[j - weight[i]] + value[i],即放物品i,指定是取最大的,毕竟是求最大价值,
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
- dp数组如何初始化
- 确定遍历顺序 倒序遍历背包是为了保证物品i只被放入一次!
== 如果 dp[j] = j 说明,集合中的子集总和正好可以凑成总和j,理解这一点很重要。==
主要要理解,题目中物品是nums[i],重量是nums[i],价值也是nums[i],背包体积是sum/2。
时间复杂度:O(n^2)
空间复杂度:O(n)
class Solution:def canPartition(self, nums: List[int]) -> bool:if sum(nums) % 2 != 0:return Falsetarget = sum(nums) // 2dp = [0] * (target + 1)for num in nums:for j in range(target, num-1, -1):dp[j] = max(dp[j], dp[j-num] + num)return dp[-1] == target # 集合中的元素正好可以凑成总和target
class Solution:def canPartition(self, nums: List[int]) -> bool:total_sum = sum(nums)if total_sum % 2 != 0:return Falsetarget_sum = total_sum // 2dp = [[False] * (target_sum + 1) for _ in range(len(nums) + 1)]# 初始化第一行(空子集可以得到和为0)for i in range(len(nums) + 1):dp[i][0] = Truefor i in range(1, len(nums) + 1):for j in range(1, target_sum + 1):if j < nums[i - 1]:# 当前数字大于目标和时,无法使用该数字dp[i][j] = dp[i - 1][j]else:# 当前数字小于等于目标和时,可以选择使用或不使用该数字dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]return dp[len(nums)][target_sum]
这篇关于2024/06/13--代码随想录算法3/17|01背包问题 二维、01背包问题 一维、416. 分割等和子集的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!