动态规划主要指的现阶段的所做决策最优决策加上将来所做的最优决策组合起来肯定是最优决策,它需要满足三个条件:
1.最优化原理(最优子结构性质):一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质
2.无后向性:将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态
3.子问题的重叠性:。动态规划实质上是一种以空间换时间的技术,它在实现的过程中,不得不存储产生过程中的各种状态,所以它的空间复杂度要大于其它的算法
详细介绍参见http://www.ahhf45.com/info/Data_Structures_and_Algorithms/algorithm/technique/dynamic_programming/chapter3.htm
接下来会列举几个经典题目,及解法:
1.0/1背包问题
题目:给定一个载重量为m,n个物品,其重量为wi,价值为vi,1<=i<=n,要求:把物品装入背包,并使包内物品价值最大
解题思路:每一个对象都只有两种状态,一种是在箱子里面,另一种是不在箱子里面,那么当重量相同的时候,我们可以去当前对象在箱子里面和当前对象不再箱子里面两种情况中的最佳值作为最优解,并记录下来。
是否满足3个特征:1.它满足最优化原理,既当对于前面判断好的对象,在某个具体的重量上的价值都是最优化的。
2.以前的对象是不是放到箱子里面,对后面的对象没有影响。
3.存储了以前的最优状态
算法的具体实现:
package com.fnk.acm;
public class Package {
private static int PackageWeight = 15;
private static int[] objectWeights = new int[] { 2, 6, 4, 7, 9 };
private static int[] objectValues = new int[] { 1, 6, 5, 9, 4 };
private static int[][] value = new int[objectWeights.length + 1][];
//初始化对象
private static void init() {
for (int i = 0; i < value.length; i++) {
value[i] = new int[PackageWeight + 1];
}
for (int i = 0; i < value.length; i++) {
for (int j = 0; j <= PackageWeight; j++) {
value[i][j] = -1;
}
}
}
public static int getMaxValue() {
init();
for (int i = 1; i < value.length; i++) {
for (int j = 1; j <= PackageWeight; j++) {
//首先将 重量为j的ID为i-1的value值 赋值给重量为j的ID为i的对象。这个 我们可以想象成第i的对象不放到箱子里面去。那样重量不变,价值额不变
value[i][j] = value[i - 1][j];
//当第 i个对象的重量小于J并且, value[i][j] < value[i - 1][j - objectWeights[i - 1]]+ objectValues[i - 1].
//此处我们假设 i为2,j为10. objectWeights[1]为5,那么value[i - 1][j - objectWeights[i - 1]] = value[1][5],objectValues[i - 1]
//指第2个对象的重量。那么整句的意思是,需要去判断一下,不妨第二个对象的价值大,还是第二个对象进去的价值大,取大的那个。
if (objectWeights[i - 1] <= j
&& value[i][j] < value[i - 1][j - objectWeights[i - 1]]
+ objectValues[i - 1]) {
//当第i个对象的重量等于j或者当value[i - 1][j - objectWeights[i - 1]]不为-1的时候才能将第I个对象放进箱子里
//当value[i - 1][j - objectWeights[i - 1]] = -1的时候,其实里面是没有放对象的,那么其实重量为0,那么把它当成重量为j - objectWeights[i - 1]就没有意义了
if (j == objectWeights[i - 1]){
value[i][j]= objectValues[i - 1];
}else if(value[i - 1][j - objectWeights[i - 1]] != -1){
value[i][j] = value[i - 1][j - objectWeights[i - 1]]
+ objectValues[i - 1];
}
}
}
}
int maxValue = 0;
int weight = 0;
for (int i = 1; i <= PackageWeight; i++) {
if (value[objectWeights.length][i] > maxValue) {
maxValue = value[objectWeights.length][i];
weight = i;
}
}
System.out.print("Max Value:" + maxValue + ",Weigth:" + weight);
return 0;
}
public static void main(String[] args) {
Package.getMaxValue();
}
}
2.求两地最短路径算法
解题思路,从目的地开始往后遍历。如果某一点有到目的地更近的方案,就记录下来。
是否满足3个特征:1.它满足最优化原理,如果当前节点到目的地的路径有n条,那么前n个点的最优解加上前个节点到当前节点的距离之和的最优解也就是当前节点到目的在的最优解
2.是否经过当前节点和以前的状态没有关系
3.存储了以前的最优状态
package com.fnk.acm;
public class MinPath {
private static char node[] = {'A','B','C','D','E','F','G'};
private static int array[][]=
{ /* A B C D E F G*/
/*A*/ {0, 5, 2, 0, 0, 0, 0}, // B -3- D
/*B*/ {0, 0, 0, 3, 2, 0, 0}, // / / /4
/*C*/ {0, 0, 0, 0, 7, 4, 0}, // /5 2/ /_
/*D*/ {0, 0, 0, 0, 0, 0, 4}, // A E -3- G
/*E*/ {0 ,0, 0, 0, 0, 0, 3}, // /2 / /
/*F*/ {0, 0, 0, 0, 0, 0, 5}, // / /7 /5
/*G*/ {0, 0, 0, 0, 0, 0, 0} // C -4- F
};
public static int getMinRoutineVal( )
{
int len = array[0].length;
int ret=0;
int sr[] = new int[len];
int way[] = new int[len];
int i,j,temp;
sr[len-1] = 0;
way[len-1] = len-1;
for(i=len-2; i>=0; i--) //计算每点的最小routine value.从根向顶层遍历
{
sr[i] = 0;
way[i] = 0;
for(j=i+1; j<len; j++)
{
if(array[i][j] != 0)
{
temp = sr[j]+array[i][j];
if(sr[i] == 0 || temp < sr[i])
{
sr[i] = temp;
way[i] = j;
}
}
}
}
PrintWay(way);
ret = sr[0];
return ret;
}
public static void PrintWay(int way[]) //打印路径
{
int i=0;
int len = way.length;
while(i != len-1)
{
System.out.println(node[i]);
i = way[i];
}
System.out.println(node[i]);
}
public static void main(String[] args){
//MinPath.getMinPath();
MinPath.getMinRoutineVal();
}
}
分享到:
相关推荐
利用动态规划算法,可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。因此,动态规划技术越来越成为解决许多重要的应用问题的关键技术。例如,用动态规划解决0-1背包问题、图像数据压缩、矩阵连乘、有向...
北京工业大学--算法作业2--动态规划算法实现0-1背包问题---Java代码 利用动态规划算法实现0-1背包问题或装配线调度问题。(二选一) 要求测试数据以文本文件的形式存储, 即所有的数据由文本文件读入。 利用动态...
【达摩老生出品,必属...资源名:matlab实现动态规划算法 程序源码.zip 资源类型:程序源代码 源码说明: 基于matlab实现动态规划的程序,包含完整源码和注释,非常适合借鉴学习 适合人群:新手及有一定经验的开发人员
1.掌握动态规划算法的基本思想,包括最优子结构性质和基于表格的最优值计算方法。 2.熟练掌握分阶段的和递推的最优子结构分析方法。 3.学会利用动态规划算法解决实际问题。 题目一:数塔问题 给定一个数塔,其...
几道动态规划的经典算法 非常经典 值得分享
动态规划算法简介 动态规划算法很详细 有典型例子 适合初学者
《动态规划算法实验》实验报告
动态规划算法将原问题分解为若干个子问题,先求子问题的解,然后从这些子问题的解得到原问题的解。 这些子问题的解往往不是相互独立的。在求解的过程中,许多子问题的解被反复地使用。为了避免重复计算,动态规划...
利用动态规划算法解决图形图像处理问题,用Java编写,代码经过调试健壮性良好
动态规划算法实现投资问题,老师给的比较实用的,呵呵,希望大家多多采纳
动态规划算法与贪心算法动态规划算法与贪心算法动态规划算法与贪心算法动态规划算法与贪心算法动态规划算法与贪心算法动态规划算法与贪心算法动态规划算法与贪心算法
动态规划算法课件PPT,读者可以参考,非常不错的,清华老师的
0_1背包问题动态规划算法的探讨.pdf 0_1背包问题动态规划算法的探讨.pdf 0_1背包问题动态规划算法的探讨.pdf
动态规划算法(下).ppt动态规划算法(下).ppt动态规划算法(下).ppt
详细解释了动态规划算法的各种应用场合,对于做ACM题很有帮助
动态规划算法求解TSP 用动态规划算法求解TSP,数据为Solomon数据集的c101文件读取,可视化路径图,用图展示每次迭代的最优值、最差值和平均值,并与Gurobi求解结果比较各计算时间下的目标值。动态规划算法求解TSP 用...
动态规划算法 数据结构 算法导论 编程思想 程序员指定用书
c/c++语言的动态规划算法动态规划动态规划动态规划动态规划
本算法用于背包问题的动态规划算法,假设每种物品的数量是不限的,求最大体积为C时的所装最有价值物品。