动态规划 是 最优化原理 中的一种重要的方法。
动态规划在查找有很多 重叠子问题 的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题,它们的结果都逐渐被计算并被保存,从简单的问题直到整个问题都被解决。因此,动态规划保存递归时的结果,因而不会在解决同样的问题时花费时间。
动态规划只能应用于有 最优子结构 的问题。最优子结构的意思是局部最优解能决定全局最优解。简单地说,问题能够分解成子问题来解决。
总的来说,动态规划的优势在于:
问题描述:
动态规划举例
图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
思路:
1.算出每个节点的规划值(也就是待比较的最大值),并记录搜索路径
2.取三角形底边所有规划值中的最大值
3.输出路径
主程序
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.trim()); } //找出最佳路径 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(); } }
用于读取文件的辅助类
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 String TRIANGLE_FILE ="c:/java/triangle.txt" ; public static String[][] getTriangle() { String[][] rtn; try{ File f =new File(ReadTriangle.TRIANGLE_FILE); BufferedReader br=new BufferedReader(new FileReader(f)); List l =new Vector(); String line =br.readLine(); while (line != null ) { l.add(line.trim()); line=br.readLine(); } int heigth=l.size(); rtn =new String[heigth][]; for ( int i =0 ; i< heigth ; i ++ ) { String s = (String)l.get(i); String[] tk =s.split(" "); int tklen =tk.length; rtn[i] =new String[tklen]; for ( int k =0 ; k < tklen ; k ++ ) { rtn[i][k] = tk[k]; } } return rtn; } catch (FileNotFoundException e) { System.out.println("err1="+e); } catch (IOException e) { System.out.println("err2="+e); } return null ; } public static void main(String args[]){ String[][] trn=ReadTriangle.getTriangle(); System.out.println("toal="+trn.length); for(int i=0;i< trn.length;i++){ System.out.println("ok="+trn[i].length); for(int j=0;j< trn[i].length;j++) System.out.println(trn[i][j]); } } }结果输出如下:
↑返回目录
前一篇: java中的String池
后一篇: 递归--树型的方式输出目录下的文件