首页 / 算法 / 动态规划算法实例三则
动态规划算法实例三则
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了动态规划算法实例三则,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3407字,纯文字阅读大概需要5分钟。
内容图文
动态规划属于不好理解的计算机基本算法之一。
需要经过多次实践,才能体会其精妙之处。
其精妙的地方在于:降低运算量。
下面通过实例理解动态规划解题思路。
实例一:求数组的最大连续和子数组。参考文章
用动态规划来解,首先得考虑状态和状态转移方程。如果我们把题述数组看成序列,那么是不是可以用序列DP来考虑呢?
我们不妨考虑一个这样的序列:1,-3,5,-2,4
a[i]表示这个序列的第 i 个元素,dp[i]表示最后一个元素是a[i]的最大连续和(此乃状态,是不是跟LIS的DP解法有点类似),于是:
dp[0] : a[0] ; ( 1 )
dp[1] : max(dp[0] + a[1] , a[1]) ; ( -2 )
dp[2] : max(dp[1] + a[2] , a[2]) ; ( 5 )
dp[3] : max(dp[2] + a[3] , a[3]) ; ( 3 )
dp[4] : max(dp[3] + a[4] , a[4]) ; ( 7 )
所以:ans = 7 (dp数组的最大值)
于是,我们可以得到状态转移方程:dp[i+1] = max(dp[i]+a[i+1] , a[i+1])
写成代码的话,我们可以忽略掉dp数组,直接用一个变量sum来记录 i 之前的最大增量(因为如果这个增量为负,则变为0)
java源码如下:动态规划求解复杂度为o(n)
//动态规划方法dp public int maxSubArray3(int[] array) { int sum = 0; int ret = Integer.MIN_VALUE; for (int i = 0; i < array.length; i++) { sum += array[i]; if (sum > ret) { ret = sum; } if (sum < 0) { sum = 0; } } return ret; } public static void main(String[] ars) { int[] a = { -2, 1, -3, 4, -1, 2, 1, -5, 4}; MaxSubArray array = new MaxSubArray(); int max = array.maxSubArray3(a); System.out.println(max); }
注意:状态转移方程没有在代码中提现出来。
求子数组最大和问题,也可以直接遍历求解。复杂度为o(n^2)
java代码如下:
//直接遍历求解 public int maxSubArray4(int[] array) { int max = Integer.MIN_VALUE; int sum = 0; for (int i = 0; i < array.length; i++) { sum = 0; for (int j = i; j < array.length; j++) { sum += array[j]; if (sum > max) { max = sum; } } } return max; }
实例二:数组分割成两个数组,且两子数组和的差最小。
动态规划解题思路:
1、原数组所有元素之和为sum.
2、子数组和的差最小,则子数组和尽量接近sum/2.
3、问题转化为,求原数组中的子数组,子数组之和尽量接近sum/2,最好等于sum/2.这样差就会为0。
4、转化为01背包问题:sum/2为背包容量。
状态转移方程为(参考文章2):背包容量是SUM/2. 每个物体的体积是数的大小,然后尽可能的装满背包。
dp方程:f[i][V] = max(f[i-1][V-v[i]]+v[i], f[i-1][V] )
f[i][V]表示用前i个物体装容量为V的背包能够装下的最大值,f[i-1][V-v[i]]+v[i]表示第i个物体装进背包的情况,f[i-1][V]表示第i件物品不装进背包的情况。
java源码如下:
package test; import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class SplitArray { static int[][] result = new int[20][20]; static int split(int[] array) { int sum = 0; int len = array.length; for (int i = 1; i < len; i++){ sum += array[i]; } sum >>= 1; //动态规划 for (int i = 1; i < len; i++) { //循环数组 for (int j = 0; j <= sum; j++) { //背包容量 if (j >= array[i]) { //背包容量能放下array[i] result[i][j] = Math.max(result[i - 1][j], result[i - 1][j - array[i]] + array[i]); } else //不能放下array[i] result[i][j] = result[i - 1][j]; } } //查找出被 int j = sum; List<Integer> listA = new ArrayList<Integer>(); List<Integer> listB = new ArrayList<Integer>(); for (int i = len - 1; i > 0; i--) { if (result[i][j] > result[i - 1][j]) { //找出被选中的元素 listA.add(new Integer(array[i])); j -= array[i]; } else { listB.add(new Integer(array[i])); } } //显示划分结果 Object[] ret = listA.toArray(); System.out.println(Arrays.toString(ret)); ret = listB.toArray(); System.out.println(Arrays.toString(ret)); //给出差值 int sum1 = 0; int sum2 = 0; for (Integer integer : listA) { sum1 += integer; } for (Integer integer : listB) { sum2 += integer; } int diff = Math.abs(sum1 - sum2); return diff; } public static void main(String args[]) { int[] array = { 0, 3, 5, 2, 1, 4 }; int diff = split(array); System.out.println("the diff is: " + diff); } }
运行结果如下:
[2, 5]
[4, 1, 3]
the diff is: 1
实例三:经典背包问题温习(文考文章3)
01背包问题的动态规划转移方程为:
f[i][v] = max{ f[i-1][v] , f[i-1][v - c[i]] + v[i]}
参考文章
1、http://www.mamicode.com/info-detail-511949.html
2、http://www.tuicool.com/articles/ZF73Af
3、http://www.cnblogs.com/bourbon/archive/2011/08/23/2151044.html
原文:http://blog.csdn.net/qq_23617681/article/details/51334408
内容总结
以上是互联网集市为您收集整理的动态规划算法实例三则全部内容,希望文章能够帮你解决动态规划算法实例三则所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。