武进网站建设咨询网站建设培训基地

当前位置： 首页 > news >正文

武进网站建设咨询,网站建设培训基地,外贸有限公司英文网站,电子政务网站建设的步骤一般为一、了解动态规划1.简单来说动态规划是一种状态转移与递推2.例题引入——最少硬币问题有多个不同面值的硬币(任意面值)#xff1b; 数量不限#xff1b; 输入金额S#xff0c;输出最少硬币组合。 #xff08;回顾用贪心求解硬币问题。#xff09;贪心法硬币面值1、2、5。支…一、了解动态规划1.简单来说动态规划是一种状态转移与递推2.例题引入——最少硬币问题有多个不同面值的硬币(任意面值) 数量不限 输入金额S输出最少硬币组合。 回顾用贪心求解硬币问题。贪心法硬币面值1、2、5。支付13元要求硬币数量最少。贪心法: (1) 5元硬币2个(2) 2元硬币1个(3) 1元硬币1个正确! 答案是:2枚5元硬币1枚2元硬币1枚1元硬币。硬币面值1、2、4、5、6。支付9元要求硬币数量最少。贪心法: (1) 6元硬币1个(2) 2元硬币1个(3) 1元硬币1个错误! 答案是:1枚5元硬币1枚4元硬币。硬币问题的正解是动态规划动态规划给定15102550这5种面值的硬币 数量不限 输入金额S输出最少硬币组合。首先定义数组Min[ ] 记录最少硬币数量。对输入的某个金额iMin[i]是最少的硬币数量。1. 只考虑1元面值的硬币。i1元时等价于ii-1 0元需要的硬币数量加上1个1元硬币。——其中把Min[ ]叫做“状态”把Min[ ]的变化叫做“状态转移”。2.所有金额仍然都只用1元硬币。i2元时等价于ii-1 1元需要的硬币数量加上1个1元硬币。i3元时…i4元时…3.在1元硬币的计算结果基础上再考虑加上5元硬币的情况。从i5开始就行了。i5元时等价于:(1) i i-5 0元需要的硬币数量加上1个5元硬币。Min[5]1(2) 原来的Min[5]5。取 (1) (2)的最小值所以Min[5]1。i6元时等价于:(1) i i-5 1元需要的硬币数量加上1个5元硬币。Min[6]2(2) 原来的Min[6]6。取 (1) (2)的最小值所以Min[6]2。i7元时…i8元时…动态规划总结用1元和5元硬币结果:递推关系状态转移方程:Min[i] min(Min[i], Min[i - 5] 1)继续处理其它面值硬币。动态规划实现代码实现递推关系上面代码状态名是Min[ ]但是其实习惯上把状态命名为dp[ ]更好。二、动态规划的两个特征1.重叠子问题子问题是原大问题的小版本计算步骤完全一样;计算大问题的时候需要多次重复计算小问题。一个子问题的多次计算耗费了大量时间。用DP处理重叠子问题每个子问题只需要计算一次从而避免了重复计算这就是DP效率高的原因。2.最优子结构首先大问题的最优解包含小问题的最优解。其次可以通过小问题的最优解推导出大问题的最优解。三、记忆化如果各个子问题不是独立的如果能够保存已经解决的子问题的答案在需要的时候再找出已求得的答案可以避免大量的重复计算。基本思路:用一个表记录所有已解决的子问题的答案不管该问题以后是否被用到只要它被计算过就将其结果填入表中。四、动态规划求解过程图解五、最经典的动态规划问题——0/1背包给定n种物品和一个背包 物品i的重量是wi 其价值为Vi 背包的容量为C。背包问题: 选择装入背包的物品使得装入背包中物品的总价值最大。 如果在选择装入背包的物品时对每种物品i只有两种选择: 装入背包或不装入背包称为0/1背包问题。设xi表示物品i装入背包的情况xi0表示物品i没有被装入背包xi1表示物品i被装入背包。有5个物品重量分别是{2,2,6,5,4} 价值分别为{6,3,5,4,6} 背包的容量为10。定义一个(n1)X(C1)的二维表dp[ ][ ]。 dp[i][i]表示把前i个物品装入容量为j的背包中获得的最大价值。填表:按只放第1个物品、只放前2个、只放前3个……一直到放完这样的顺序考虑。(从小问题扩展到大问题)1、只装第1个物品。(横向是递增的背包容量)2、只装前2个物品。如果第2个物品重量比背包容量大那么不能装第2个物品情况和只装第1个一样。如果第2个物品重量小于等于背包容量那么:1如果把物品2装进去(重量是2)那么相当于只把1装到(容量-2)的背包中。需要用到前面的需要用到前面的结果即已经解决的子问题的答案经解决的子问题的答案。2如果不装2那么相当于只把1装到背包中。——取(1) 和 (2)的最大值。3、只装前3个物品。如果第3个物品重量比背包容量大那么不能装第3个物品情况和只装第1、2个一样。如果第3个物品重量小于等于背包容量那么:1如果把物品3装进去(重量是6)那么相当于只把1、2装到(容量-6)的背包中。2如果不装3那么相当于只把1、2装到背包中。——取(1) 和 (2)的最大值。按这样的规律一行行填表直到结束。现在回头考虑装了哪些物品。看最后一列1514说明装了物品5否则价值不会变化。六、蓝桥杯真题(1174号)1.DP状态设计DP状态: 定义二维数组dp[ ][ ]大小为N * C。dp[i][j]:把前i个物品(从第1个到第i个) 装入容量为j的背包中获得的最大价值。把每个dp[i][j]看成一个背包: 背包容量为j装1~i这些物品。最后得到的dp[N][C]就是问题的答案:把N个物品装进容量C的背包的最大价值。2.DP状态转移方程(递推公式)递推计算到dp[i][j]分2种情况:(1)第i个物品的体积比容量j还大不能装进容量的背包。那么直接继承前i-1个物品装进容量j的背包的情况即可: dp[i][j] dp[i-1][j]。(1)第i个物品的体积比容量j小能装进背包。又可以分为2种情况: 装或者不装第i个。1)装第i个。从前i-1个物品的情况下推广而来前i-1个物品是dp[i-1][j]。第i个物品装进背包后背包容量减少c[i]价值增加w[i]。有:dp[i][j] dp[i-1][j-c[i]] w[i]。2)不装第i个。那么:dp[i][j] dp[i-1][j]。取1)和2)的最大值状态转移方程:dp[i][j] max(dp[i- 1][j]d[i- 1][j- c[i]] w[i])3.代码七、空间优化:滚动数组把dp[ ][ ]优化成一维的dp[ ]以节省空间。Dp[i][]是从上面一行dp[i-1]算出来的第i行只跟第i-1行有关系跟更前面的行没有关系:dp[i][j] max(dp[i - 1][j], dp[i - 1][j - c[i]] w[i])优化:只需要两行dp[0][]、dp[1][]用新的一行覆盖原来的一行交替滚动。经过优化空间复杂度从O(N*C)减少为O©1.交替滚动定义dp[2][i]: 用dp[O][]和dp[1][]交替滚动。优点逻辑清晰、编码不易出错建议初学者采用这个方法。代码now始终指向正在计算的最新的一行old指向已计算过的旧的一行。对照原递推代码now相当于iold相当于i - 1。对照未经优化优化之后2.自我滚动继续精简:用一个一维的dp[ ]就够了自己滚动自己。dp[i][j] max(dp[i - 1][j], dp[i - 1][j - c[i]] w[i])对照未经优化优化之后注意自我滚动时j从小往大循环是错误的优化之前填表的过程自我滚动填表的过程例如i 2时左图的dp[5]经计算得到dp[5] 9把dp[5]更新为9。右图中继续往后计算当计算dp[8]时得dp[8] dp[5]’ 3 93 12。这个答案是错的。错误的产生是滚动数组重复使用同一个空间引起的。注意自我滚动时j从大往小循环是正确的优化之前填表的过程自我滚动填表的过程例如i 2时首先计算最后的dp[9] 9它不影响前面状态的计算。