动态规划是最优化原理中的一种重要的方法。
动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题,它们的结果都逐渐被计算并被保存,从简单的问题直到整个问题都被解决。因此,动态规划保存递归时的结果,因而不会在解决同样的问题时花费时间。
动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解。简单地说,问题能够分解成子问题来解决。
总的来说,动态规划的优势在于:
问题描述:
动态规划举例
图10-3(a)示出了一个数字三角形,请编一个程序,
计算从顶至底的某处的一条路劲,
使该路劲所经过的数字的总和最大。
(1) 每一步可沿左斜线向下或右斜线向下;
(2) 1<三角形行数≤100;
(3) 三角形中的数字为0,1,……99。
输入数据:
由INPUT.TXT文件中首先读到的是三角形的行数,
在例子中INPUT.TXT表示如图13-3(b).
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
5 6 9 5 9 8
从别人blog里看到这个题目,手上痒痒,就写了一个.用的是逆向递推法从顶部往下.
分2个文件,一个主程序和一个用于读取文件的辅助类.
思路:
1.算出每个节点的规划值(也就是待比较的最大值),并记录搜索路径
2.取三角形底边所有规划值中的最大值
3.输出路径
主程序
package
test;
import
java.util.
*
;
/** */
/**
* 用动态规划法求出最优路径
*
@author
zqc
*
*/
public
class
DynamicSolveTrianglePath
{
private
String[][] str_triangle
=
null
;
private
Node[][] triangle_nodes
=
null
;
private
List nodes;
private
List paths;
//
节点
static
class
Node
{
private
int
value;
private
List path
=
new
Vector();
public
List getPath()
{
return
path;
}
public
void
setPath(List p)
{
path
=
p;
}
//
n=(0,0) or (0,1) or (2,2)
public
void
addPath(String n)
{
path.add(n);
}
public
void
addPath(List pa)
{
path.addAll(pa);
}
public
int
getValue()
{
return
value;
}
public
void
setValue(
int
value)
{
this
.value
=
value;
}
}
public
DynamicSolveTrianglePath()
{
initNodes();
findPath();
}
// 从根节点开始,逆向推解出到达所有节点的最佳路径
private void initNodes(){
this.str_triangle = ReadTriangle.getTriangle();
triangle_nodes = new Node[str_triangle.length][];
nodes = new Vector();
for(int i = 0 ; i < str_triangle.length; i++){
triangle_nodes[i] = new Node[str_triangle[i].length];
for(int j = 0 ; j<str_triangle[i].length;j++){
String currentPath = "("+i+","+j+")";
Node n = new Node();
if(i==0&&j==0){
n.setValue(
c(str_triangle[0][0])
);
n.addPath(currentPath);
triangle_nodes[i][j] = n;
continue;
}
//左右边界节点
if((j==0||j==str_triangle[i].length-1)){
if(i==1){//第2行的节点
int value = c(str_triangle[0][0])+c(str_triangle[i][j]);
List ph = triangle_nodes[0][0].getPath();
n.addPath(ph);
n.addPath(currentPath);
n.setValue(value);
ph = null;
}else{//0,1行以下的其他边界节点
int value = j==0?c(str_triangle[i][j])+triangle_nodes[i-1][j].getValue():
c(str_triangle[i][j])+triangle_nodes[i-1][j-1].getValue();
List ph = j==0?triangle_nodes[i-1][j].getPath():
triangle_nodes[i-1][j-1].getPath();
n.addPath(ph);
n.addPath(currentPath);
n.setValue(value);
}
}else{//除边界节点外其他节点
Node node1 = triangle_nodes[i-1][j-1];
Node node2 = triangle_nodes[i-1][j];
Node bigger = max(node1,node2);
List ph = bigger.getPath();
n.addPath(ph);
n.addPath(currentPath);
int val = bigger.getValue()+c(str_triangle[i][j]);
n.setValue(val);
}
triangle_nodes[i][j] = n;
n = null;
}//end of for j
}//end of for i
}
private Node max(Node node1,Node node2){
int i1 = node1.getValue();
int i2 = node2.getValue();
return i1>i2?node1:node2;
}
private int c(String s){
return Integer.parseInt(s);
}
//找出最佳路径
private void findPath(){
if(this.triangle_nodes==null)return;
int max = 0;
int mi = 0;
int mj = 0;
for(int i = 0 ; i < triangle_nodes.length; i++){
for(int j = 0 ; j<triangle_nodes[i].length;j++){
int t = triangle_nodes[i][j].getValue();
if(t>max){
max = t;
mi = i;
mj = j;
}
}
}
System.out.println("Max Path:"+triangle_nodes[mi][mj].getPath());
System.out.println("Max Value:"+max);
}
public static void main(String[] args)throws Exception{
DynamicSolveTrianglePath dsp = new
DynamicSolveTrianglePath();
}
}
用于读取文件的辅助类
package
test;
import
java.io.
*
;
import
java.util.
*
;
/** */
/**
* 输入文本格式为
* 类似这样一个数字三角形
*
* x
* x x
* x x x
* x x x x
* x x x x x
*
*
@author
zqc
*
*/
public
class
ReadTriangle
{
public
static
分享到:
相关推荐
应用动态规划算法思想求解矩阵连乘的顺序问题。 【实验性质】 验证性实验(学时数:2H) 【实验要求】 应用动态规划算法的最优子结构性质和子问题重叠性质求解此问题。分析动态规划算法的基本思想,应用动态规划策略...
动态规划,算法采用动态规划算法实现以下问题: 1、 最少硬币问题(必做) (算法实现题 3-2、 http://acm.nankai.edu.cn/p1132.html) 2、 最小M段和 (算法实现题 3-11、参见P63 最大m子段和) 3、最长子序列 ...
动态规划是研究一类最优化问题的方法,在经济、工程技术、企业管理、工农业生产及军事等领域中都有广泛的应用。近年来,在ACM/ICPC中,使用动态规划(或部分应用动态规划思维)求解的题不仅常见,而且形式也多种多样。...
模型算法大全:规划模型(19份),供大家学习参考: 课件:最短路问题.ppt LINGO线性规划及其灵敏度分析.doc ... 动态规划+多目标规划(2份) 1.动态规划.ppt 2.多目标.ppt 整数规划.docx 线性规划.docx
算法分析实验:动态规划法求最长公共子序列及其01背包
动态规划的讲义。十分有用。 用了之后收获很大。 推荐各位研究算法的同学
《算法设计与分析》课程笔记代码Part2(动态规划+贪心算法+回溯算法) 本文为博主基于课堂ppt以及自行编写的代码整理的研究生《算法设计与分析》课程笔记,涉及分治算法、动态规划算法、贪心算法、回溯算法、分支...
论文包括:题目,摘要,正文,参考文献 ...§2动态规划的设计与实现 §2.1动态规划的多样性 §2.2动态规划的模式性 §2.3动态规划的技巧性 §3动态规划与一些算法的比较 §3.1动态规划与递推 §3.2动态规划与搜索
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。...2:动态规划
(2) 金罐游戏问题的动态规划解法。 算法设计与分析-4动态规划金罐游戏.pptx 蛮力法(简单重复递归)和动态规划解决金罐问题 状态数组 子问题 状态方程 蛮力法(时间复杂度O(2n))和动态规划(时间复杂度O(n2)) ...
北京工业大学--算法作业2--动态规划算法实现0-1背包问题---Java代码 利用动态规划算法实现0-1背包问题或装配线调度问题。(二选一) 要求测试数据以文本文件的形式存储, 即所有的数据由文本文件读入。 利用动态...
动态规划算法 动态规划算法基本思想: 1、 将待求解问题分阶段处理 2.doc
(2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。 最后,所有边都被删除,游戏结束。游戏的得分就是所剩顶点上的整数值。 包括代码+流程图+uml...
简单清晰的代码风格,完备的代码注释,详细的实验报告 算法分析。你值得拥有。 问题描述: 商店中每种商品都有标价。例如,一朵花的价格是2 元。一个花瓶的价格是5 元。为了吸引顾客,商店提供了一组优惠商品价。...
《数据结构与算法分析:C语言描述》特色:着重讨论了算法设计技巧,包括贪婪算法、分治算法、动态规划、随机化算法以及回溯算法。系统介绍了当前流行的论题和新的数据结构,如斐波那契堆、斜堆、二项队列、跳跃表和...
2.最大子段和问题,比较三重循环,分治法和动态规划算法的效果,测试数据:1) (-2,11,-4,13,-5,-2)2)过去大约三百年间,太阳黑子数的时间数据如
2.动态规划应用举例 3.马氏决策规划简介 动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于,它可以把一个n 维决策问题变换为几个一维最优化问题,从而一个一个地去解决。 需指出:动态规划是...
《数据结构与算法分析:C语言描述》特色:着重讨论了算法设计技巧,包括贪婪算法、分治算法、动态规划、随机化算法以及回溯算法。系统介绍了当前流行的论题和新的数据结构,如斐波那契堆、斜堆、二项队列、跳跃表和...
动态规划是对最优化问题的一种新的算法设计方法。由于各种问题的性质不同, 确定最优解的条件也互不相同,因而动态规划的没计法对不同的问题,有各具特 色的表示方式。不存在一种万能的动态规划算法。但是可以通过...
5:动态规划、回溯搜索、分治算法、分支界定;6:最优化理论的三大经典算法(模拟退火算法、神经网络算法、遗传算法);7:网格算法和穷举法;8:连续数据离散化;9:数值分析算法;10:图象处理算法(常用matlab来...