perfectprint.java

该程序用Java实现了算法中的动态规划问题_漂亮打印

/* 算法思想：该最优打印算法是根据矩阵连乘算法改编的来的
 * 对于每行最多能容纳 M个字符，随机生成 n 个长度为1到（M/2+1）的单词，给出最漂亮
 * 打印的输出 ，用 0 表示单词的一个字符，用 + 表示一个空格 。
 * 其中用firstL[i][j]用来表示最漂亮打印单词i到j时，第一行的最后一个单词的序号。
 * 用 pC[i][j].cost 用来表示最漂亮打印单词i到j时，所需要的开销（各行所剩的空格数的立方和）。
 * 用 pC[i][j].lastL 用来表示最漂亮打印单词i到j时，最后一行所剩的空格数。
 * 该算法的空间开销为 O ( n^2 ),时间开销为 O(n^3)
 */

package pp;
import java.lang.*;
import java.util.*;
import java.io.*;

class PrintC
{
    public int cost;
    public int lastLS;
};

public class PerfectPrint {   
     
     // Perfectly print out all the words
    private static void PrintAll(int[] wordLen,int M,int[][] firstL){
        int n = wordLen.length-1;
        int start = 1;
	int end = firstL[1][n];
        int t = M; 
        int len;
	while( start <= n )
	{
            System.out.print("    ");
            //the first word in one line
            len = wordLen[start] ;
            for(int i=0;i< len ;i++ ){
                 System.out.print("0");
                 t--;
            }               
            for(int w =start+1; w<= end ; w++ )
            {
		System.out.print("+"); // 0 presrnt space
                t--;
                len = wordLen[w] ;
		for(int i=0;i< len ;i++ ){
                     System.out.print("0");
                     t--;
                 }   
            }
            while (t>0){
                System.out.print("+");
                t -- ;
            }
             System.out.println(" ");
             start = end + 1;
             if(start <= n)
                end = firstL[start][n];
             t = M;
      }
      System.out.println("The print was done :) ");
      return;       
    }
    
    public static void main(String[] args) {
        // TODO code application logic here
        int n ;
	int M;
	n = 30;  // total number of words
	M = 10;  // maximum characters in one line
	int[] wordLen = new int[n+1] ; // storage every word's length
	//pC[i][j] present the cost when perfectly print words form word-i to word-j
        PrintC[][] pC = new PrintC[n+1][n+1] ; 
         
        for(int i=0;i<=n;i++ )
            for( int j=0;j<=n;j++ )
             pC[i][j] = new PrintC();
        //firstL[i][j] storage the last word of the first line when perfectly print words form word-i to word-j
	int[][] firstL = new int[n+1][n+1] ; 
	int MAX = (int) M /2;  //maximum characters each can have
        Random random=new Random();
        // generate the length of words randomly
        System.out.println(" We will print "+n+" words ,the length of each word is :");        
	for( int i=1;i<=n;i++){
            wordLen[i] = Math.abs( random.nextInt() % MAX) + 1;
            System.out.print("  "+wordLen[i]);
            if( (i>9) && (i % 10) == 0 )   
                System.out.println(" ");
        }
        System.out.println(" ");       
        //initialization
          for(int i=1;i<=n;i++){
            pC[i][i].cost = 0;
            pC[i][i].lastLS = M - wordLen[i] ;  // the characters last line can have more
            firstL[i][i] = i;
	}
        
        //generate the form in perfect-print
	for(int r= 2; r<= n ; r++ )
	 for(int i =1 ;i<= n-r+1 ;i++)
	 {
            int j = i+r-1;
            int temp;
            temp =  pC[i][i].lastLS ;
	    pC[i][j].cost = temp*temp*temp + pC[i+1][j].cost;
	    pC[i][j].lastLS = pC[i+1][j].lastLS ;
	    firstL[i][j] = firstL[i][i];
	    for(int k =i+1;k<j;k++)
            {
                temp = pC[i][k].lastLS;
		int t = pC[i][k].cost + temp*temp*temp + pC[k+1][j].cost ;
		if( t < pC[i][j].cost )
		{
                    pC[i][j].cost = t;
                    pC[i][j].lastLS = pC[k+1][j].lastLS ;
		    firstL[i][j] = firstL[i][k];
		}
            }
            if( (wordLen[j] < pC[i][j-1].lastLS) && pC[i][j-1].cost < pC[i][j].cost )
            {              
		pC[i][j].cost = pC[i][j-1].cost;
		pC[i][j].lastLS = pC[i][j-1].lastLS - wordLen[j] -1;
		if( firstL[i][j-1] == (j-1) )
                	firstL[i][j] = j;
		else    firstL[i][j] = firstL[i][j-1];
             }           
	}
        System.out.println(" When perfectly printing,the sum of the cubic of spaces each line left is:" + pC[1][n].cost );
        System.out.println(" The words above can be printed perfectly below :" );
        System.out.println(" '0' presents character,'+' presents space ! ");
        PrintAll(wordLen, M,firstL);          
	return;		
    }
    
}