海兴县网站建设公司,绥化市建设局网站,wordpress无法查看发布,广东省网站免备案这里写目录标题 总览dp问题的优化01背包问题概述算法思想算法思想中的注意点例题代码 完全背包问题概述 多重背包问题概述 分组背包问题概述 总览 dp问题的优化 要清楚#xff1a;dp问题的优化一般是对dp问题的代码或者计算方程做一个等效变形 有了这个前提#xff0c;我们在… 这里写目录标题 总览dp问题的优化01背包问题概述算法思想算法思想中的注意点例题代码 完全背包问题概述 多重背包问题概述 分组背包问题概述 总览 dp问题的优化 要清楚dp问题的优化一般是对dp问题的代码或者计算方程做一个等效变形 有了这个前提我们在写dp问题时要先将基本的代码写出来之后再做优化
01背包问题
概述 假设我们有N个物品我们的背包的体积是V N个物品每个物品有两个属性分别是v体积、和w价值或者说权重每个物品要么不选如果选的话只能选一次 我们的目标是要选出一些物品在总体积能装的下的情况下不一定必须装满争取价值之和最大化
算法思想 Dp问题要考虑两个问题一个是状态表示一个是状态计算 对于01背包问题 状态表示 我们先来看状态表示因为大前提是N个物品和V的体积也就是不算物品属性的话我们有两个参数所以状态表示f就有两个参数那他就是二维的状态表示fij 而对于一个状态表示 f我们要清楚他是一个集合那么一个集合就会有属性一个集合有三种属性根据不同的题设选择不同的属性三种属性分别是max元素最大值、min元素最小值、数量元素数量本题根据题设是属性选定为max表示求最大价值 那这个集合的元素表示什么呢该集合的元素表示在所有的选法中只从前 i 个物品选择总体积小于等于 j 的选法 总结状态表示就是将题意数学化将题设信息数学化为 fij 状态计算 状态计算就是对上面的 fij进行计算主要用到集合划分的思想 首先将集合划分为两部分 第一个部分是 f 集合中所有不含 i 的选法的最大值那么就是从1~i-1中选总体积不超过 j 也及时 fi-1j 第二个部分是 f 集合中所有含 i 的选法的最大值那么我们先将 i 排除求得不算 i 时剩余的值最大的选法因为排除了一个 i 那么体积限制也跟着缩小所以是从1~i-1中选总体积不超过 j-vi 的选法的元素的最大值即 f i-1j-vi
最后将两部分取maxAPI求得 fij注意因为第二部分是将 i 排除之后计算得出的所以在取max时第二个参数要加上i的价值wi即第二个参数为 fi-1j-vi wi 如下三张图 算法思想中的注意点
首先fij表示在前i个物品中选总体积不超过 j 的选法最大价值的值 这里的i 和 j 是通量相当于将题设扩展成普遍性了不是题设的最终量也就是 i 和 j在代码中是变化的最后是要输出fNV
其次对于状态计算不含i的部分一定会出现含i部分未必一定会出现所以代码中要加一个判断代码中会体现注意留意
例题代码 nm分别表示有n个物品总体积是m v[N],w[N]数组分别存储每个物品的体积和价值 f[N][N]是状态表示也就是前i个物品中选总体积不超过j的选法中价值最大的值
main函数里 首先输入n和m 然后for循环依次向v和w中输入值 之后双重循环 i 从1到等于nj从0到等于m至于为什么i从1开始而不从0开始是因为f[0][0~m],表示前0个物品中选出体积不超过 j的选法因为物品是0所以总价值也是0所以f[0][0到m]都是0又因为int定义自动初始化为0所以不用管 i 0的情况 循环内f[i][j] f[i-1][j]先将这个赋值给f[i][j] 之后判断第二部分因为第二部分只有在 jv[i]时才会出现所以加上if判断之后f[i][j] max( f[i][j] , f[i-1][ j-v[i] ] w[i] ) 因为第一步直接将值赋给了f[i][j]所以这里是用f[i][j]进行对比这样做的好处是将第一部分与第二部分隔离开因为第二部分需要特判
完全背包问题
概述 完全背包问题是每个物品有无限个每个物品都可以选无限次
多重背包问题
概述 多重背包问题是每个物品的个数不一样也就是每个物品的可选次数不一样
分组背包问题
概述 分组背包问题是会将物品进行分组每一组最多只能选择改组内的一个物品要么这个组不选如果想选择这个组里的物品只能选择改组内的一个物品且一次
