mutigraphy.java

用动态规划法来解决多段图问题

import java.io.*;
import java.io.File;
import java.io.InputStream;
import java.lang.*;
import java.util.*;


public class mutigraphy {
float cost[];
int d[],p[],k,n,data[][],rol,vol;

char s[];
/*File datafile;*/
FileReader file;	

mutigraphy() {
		try{
		
 
	FileReader file=new FileReader("graphy.txt");
	k=(char)file.read()-48;
	n=(char)file.read()-48;System.out.println(k);
	System.out.println(n);
	data=new int[n][n];
    d=new int[n-1];
    p=new int[k];
   
	cost=new float[n];
	s=new char[3];
    
	 while(file.read(s,0,3)!=-1)
		{ rol=s[0]-48;
		  vol=s[1]-48;
		  data[rol][vol]=s[2]-48;
		  }
	
	}catch(NullPointerException e){
		System.out.print("sorry, failed of datafile input");
		System.exit(1);
		}
	catch(FileNotFoundException e){
		System.out.print(e);
		System.out.print("failed of datafile input");
		System.exit(1);
		}
    catch(IOException e){
    	System.out.print("IOExcetion.......");
    	
    }	
}
	
	
	
void fgraphy(){

	
int j;	
try{for(int i=0;i<n;i++)
  {for(j=0;j<n;j++){
  System.out.print(data[i][j]);
  	}
  System.out.println();
}}catch(NullPointerException e){
		System.out.print("sorry, failed of datafile input");
		System.exit(1);
		}	
	for( j=n-2;j>=0;j--)
	cost[j]=Cost(j,data,n,d);
	
 p[0]=0;p[k-1]=n-1;
 for(j=1;j<=k-2;j++)
 p[j]=d[(p[j-1])];
 System.out.println("the decision is:");
 for( j=0;j<k;j++)
 System.out.print(p[j]);
 System.out.println();
 System.out.println("each phrase cost is:");
 for( j=0;j<n;j++)
 System.out.print(cost[j]);
 System.out.println();
}





float Cost(int l,int[][] data,int n,int[] d){
	int i=l+1;
	float mintax=1000;

    for(;i<n;i++)
    {if(data[l][i]!=0)
	 if(data[l][i]+cost[i]<mintax){
		mintax=(data[l][i]+cost[i]);
	    d[l]=i;
	    }
	    }

	
	return mintax;
	
}

    

	public static void main(String[] args) {
		mutigraphy newgraphy=new mutigraphy();
	   newgraphy.fgraphy();
	
	}	
}