Príklad na dynamické programovanie

Created: 2008-06-19 - 17:00

Nuz islo tu o to, ze mate maticu MxN a v nej mate nerovnomerne rozmiestneny urcity pocet jablk. Zacinate v lavom hornom rohu a ulohou programu je zistit kedy sa da nazbierat najviac jablk, ak sa da pohybovat len smerom dole a smerom doprava. T.z. najst taku cestu do praveho dolneho rohu, aby bol pocet nazbieranych jablk maximalny...



import java.util.Scanner;

public class jablka {

     /**
      * @param args
      */
     static int m,n; // matica M krat N
     static int[][] matica ; // matica
     static int[][] pomocna ; // matica
     static char[][] cesta ; // matica cesty ze skade prisiel vysledok
     
     public static void jablka2(){
          nacitaj();
          
          for (int i = 0; i < m; i++) {
               if((i-1)<0)
                    pomocna[i][0] = matica[i][0];
               else {
                    pomocna[i][0] = pomocna[i-1][0]+matica[i][0];
                    cesta[i][0]= 'H';
               }
          }
          for (int i = 0; i < n; i++) {
               if((i-1)<0)
                    pomocna[0][i] = matica[0][i];
                    else {
                         pomocna[0][i] = pomocna[0][i-1]+matica[0][i];
                         cesta[0][i] = 'L';
                    }
          }
          for (int i = 1; i < m; i++) {
               for (int j = 1; j < n; j++) {
                    if(pomocna[i-1][j]<pomocna[i][j-1]){
                         pomocna[i][j] = pomocna[i][j-1] + matica[i][j];
                         cesta[i][j] = 'L';
                    } else {
                         pomocna[i][j] = pomocna[i-1][j] + matica[i][j];
                         cesta[i][j] = 'H';
                    }
               }
          }
          System.out.println(pomocna[m-1][n-1]);
          for (int j2 = 0; j2 < m; j2++) {
               for (int k = 0; k < n; k++) {
                    System.out.print(" " + cesta[j2][k]);
               }
               System.out.println();
          }
     }
     public static void nacitaj(){
     Scanner s = new Scanner(System.in);
     m =
     s.nextInt();
     n = s.nextInt();
     matica = new int[m][n];
     pomocna = new int [m][n];
     cesta = new char [m][n];
     for (int i = 0; i < m; i++) {
          for (int j = 0; j < n; j++) {
               matica[i][j] = s.nextInt();
          }
     }
     }
     public static void main(String[] args) {
          // TODO Auto-generated method stub
          jablka2();
     }

}