首页 > 其他分享 >代码随想录day35 || 416 分割等和子集

代码随想录day35 || 416 分割等和子集

时间:2024-08-20 11:28:52浏览次数:13  
标签:背包 target int day35 随想录 416 weights 物品 dp

背包问题

有n件物品和一个最多能背重量为 w 的背包。第i件物品的重量是 weight[i],得到的价值是 value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。
image


// pake
//
//	@Description:
//	@param weights: 物品i对应重量
//	@param value: 物品i对应价值
//	@param n: 背包容量
//	@return int
func pake(weights, value []int, n int) {
	// dp 五部曲
	// 确定dp数组以及下标的含义: dp[i][j] 代表容量为j的背包装前i个物品获得的最大价值
	// 递推公式 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w(i)]+v(i))
	// 初始化,背包容量为0初始化为0,物品0 初始化小于w(0)的背包价值为0. 大于初始化为v(0)
	// 遍历,先物品后背包
	// 打印

	var dp = make([][]int, len(weights))
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, n+1)
	}

	// dp[i][0] 初始化为0,dp[0][j] 看情况

	for i := 0; i < len(dp); i++ {
		for j := 0; j < len(dp[0]); j++ {
			if j == 0 {
				dp[i][j] = 0
			} else if i == 0 {
				if j >= weights[i] {
					dp[i][j] = value[i]
				} else {
					dp[i][j] = 0
				}
			} else {
				var v1, v2 int
				v1 = dp[i-1][j]
				if j-weights[i] >= 0 {
					v2 = dp[i-1][j-weights[i]] + value[i]
				}
				fmt.Println(v1, v2)
				dp[i][j] = max(v1, v2)
			}

		}
	}
	fmt.Println(dp)
}

// pake
//
//	@Description:
//	@param weights: 物品i对应重量
//	@param value: 物品i对应价值
//	@param n: 背包容量
//	@return int
func pake(weights, value []int, n int) {
	// dp 五部曲
	// 确定dp数组以及下标的含义: dp[j] 代表容量为j的背包装物品能够获得的最大价值
	// 递推公式 dp[j] = max(dp[j], dp[j-w(i)]+v(i))
	// 初始化,背包容量为0初始化为0,其他也初始化为0
	// 遍历,先物品后背包,但是背包要反序遍历,因为递推公式依赖的是上一层循环的前一个元素,如果在遍历过程中修改了上一层的之前元素,那么之后的递推就是错误的, 可能导致一个物品多次使用的情况,
	// 打印

	var dp = make([]int, n+1)

	for i := 0; i < len(weights); i++ {
		for j := n; j > 0; j-- {
			var v int
			if j-weights[i] >= 0 {
				v = dp[j-weights[i]] + value[i]
			}

			dp[j] = max(dp[j], v)
		}
	}
	fmt.Println(dp)
}

416 分割等和子集

func canPartition(nums []int) bool {
	// 本题主要难点在于,能否想到,通过将target = sum/2 ,并且填满target容量的背包从而转换成01背包问题
	// 证明,01背包元素不重复,如果dp[target] == target, 使用了m个元素,和为target=sum/2,那么剩下元素和也为sum/2,从而出现两个子集和相同

	// dp数组以及下标,dp[j] 表示容量j能装的最大价值,本题数组可以看作重量=价值
	// 递推公式 dp[j] = max(dp[j], dp[j-w[j]]+v[j]) = max(dp[j], dp[j-nums[j]]+nums[j])
	// 初始化 全部0
	// 遍历顺序,外层物品正序,内层背包倒叙
	// print
	var sum, target int
	for _, v := range nums {
		sum += v
	}
	if sum % 2 == 1 { // 和为奇数无法等量划分
		return false
	}

	target = sum / 2
	dp := make([]int, target + 1)
	for i:=0; i<len(nums); i++{
		for j:=target; j>=nums[i]; j-- { //j>nums[i] 表示空间至少要比i所占用空间大,不然就无法放入,当然也可以在内部判断剪枝
			dp[j] = max(dp[j], dp[j-nums[i]] + nums[i])
		}
	}

	fmt.Println(dp)
	if dp[target] == target{
		return true
	}
	return false
}

func max (i, j int )int {
	if i>j{
		return i
	}
	return j
}

标签:背包,target,int,day35,随想录,416,weights,物品,dp
From: https://www.cnblogs.com/zhougongjin55/p/18369118

相关文章

  • springboot留守儿童爱心网站-计算机毕业设计源码04163
    目 录1绪论1.1研究背景与意义1.2国内外研究现状1.3论文结构与章节安排2 留守儿童爱心网站分析2.1可行性分析2.1.1技术可行性分析2.1.2 经济可行性分析2.1.3法律可行性分析2.2系统功能分析2.2.1功能性分析2.2.2非功能性分析2.3 系统用......
  • 「代码随想录算法训练营」第四十一天 | 单调栈 part1
    739.每日温度题目链接:https://leetcode.cn/problems/daily-temperatures/文章讲解:https://programmercarl.com/0739.每日温度.html题目难度:中等视频讲解:https://www.bilibili.com/video/BV1my4y1Z7jj/题目状态:看题解思路:定义一个单调栈,该栈存放下标,规则是要保持其下标对......
  • 多功能数据采集仪,VTN416帮您实时监测隧道、桥梁、铁路等工程
    多功能数据采集仪,VTN416帮您实时监测隧道、桥梁、铁路等工程VTN416是一款多通道振弦、温度、模拟传感信号系列数据采集仪,专为边坡监测、隧道监测、桥梁监测、铁路监测等领域设计。它能够实时在线采集32通道的振弦频率、热敏电阻或DS18B20温度传感器以及模拟量传感器(电流或电压)的数......
  • 代码随想录day34 || 62 不同路径,63 不同路径||,343整数拆分,96 不同搜索二叉树
    不同路径funcuniquePaths(mint,nint)int{ //dp五部曲 //dp数组以及下标的含义dp[i][j]代表从0,0走到i,j的不同路径条数 //递推公式 dp[i][j]=dp[i-1][j]+dp[i][j-1] //dp数组的初始化dp[i][0]==dp[0][j]=1 //遍历顺序 外层按照行,内层按照列遍历......
  • 代码随想录Day18
    530.二叉搜索树的最小绝对差给你一个二叉搜索树的根节点root,返回树中任意两不同节点值之间的最小差值。差值是一个正数,其数值等于两值之差的绝对值。示例1:输入:root=[4,2,6,1,3]输出:1示例2:输入:root=[1,0,48,null,null,12,49]输出:1提示:树中节点的数目范围是......
  • 代码随想录算法训练营第11天|二叉树part01
    理论基础需要了解二叉树的种类,存储方式,遍历方式以及二叉树的定义二叉树纯理论方面还是比较简单,以前都学过,没什么可讲的。满二叉树就是满了,完全二叉树就是层满了(而且是左边)。平衡二叉搜索树就是左右深度绝对值差1。一般采用链式存储方式,顺序存储结构如果父节点的数组......
  • 代码随想录算法训练营第10天|栈与队列part02
    150.逆波兰表达式求值本题不难,但第一次做的话,会很难想到,所以先看视频,了解思路再去做题classSolution{public:intevalRPN(vector<string>&tokens){stack<longlong>st;for(conststring&token:tokens){if(token=="+......
  • 代码随想录Day17
    654.最大二叉树给定一个不重复的整数数组nums。最大二叉树可以用下面的算法从nums递归地构建:创建一个根节点,其值为nums中的最大值。递归地在最大值左边的子数组前缀上构建左子树。递归地在最大值右边的子数组后缀上构建右子树。返回nums构建的最大二叉树......
  • 【代码随想录训练营第42期 Day32打卡 - 从零开始动态规划 - LeetCode 509. 斐波那契数
    目录一、做题心得二、动规五步走三、题目与题解题目一:509.斐波那契数题目链接题解1:记忆性递归 题解2:动态规划题目二:70.爬楼梯 题目链接题解:动态规划题目三:746.使用最小花费爬楼梯题目链接题解:动态规划三、小结一、做题心得今天开始动态规划章节的第一......
  • 代码随想录算法训练营第十五天
    力扣题部分:110.平衡二叉树题目链接:.-力扣(LeetCode)题面:        给定一个二叉树,判断它是否是平衡二叉树        平衡二叉树 是指该树所有节点的左右子树的深度相差不超过1思路(递归):还是递归三部曲(关于三部曲的具体内容和对递归看法建议可见昨......