Advertisement
SenkuIshigami

Dynamic programming

Nov 2nd, 2020
2,045
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.33 KB | None | 0 0
  1. import java.io.File;
  2. import java.io.FileNotFoundException;
  3. import java.util.Scanner;
  4.  
  5. public class Driver
  6. {
  7.     public static void main(String[] args)
  8.         {
  9.  
  10.             try
  11.             {
  12.             //scanning the n bower sources and the n LEDs from a file
  13.             Scanner scanner = new Scanner(new File("dynamicfile.txt"));
  14.             //array called num that holds the number in the first line and the second line
  15.             int []num = new int[2];
  16.             //i is a counter
  17.             int i=0;
  18.             while (scanner.hasNextInt())
  19.             {
  20.                 num[i]=scanner.nextInt();
  21.                 i++;
  22.             }
  23.             //count is to count number of digits in each integer value
  24.             int count=0;
  25.             //since we have two different values, counts is to hold these different values
  26.             int []counts=new int[2];
  27.             //since we are gonna change the value of num so we can get the number of digit, we hold them in a different type of integer
  28.             int num1=num[0];
  29.             int num2=num[1];
  30.             //calculating the number of digits in each integer
  31.             for(i=0;i<2;i++)
  32.             {
  33.                 count=0;
  34.             while(num[i] != 0 )
  35.             {
  36.                 num[i] /= 10;
  37.                 ++count;
  38.                 counts[i]=count;
  39.             }
  40.             }
  41.            
  42.             //creating arrays that will hold the n (n=count[0]) power sources, and the n LEDs(n=count[1] here)
  43.             int []S=new int[counts[0]];
  44.             int []L=new int[counts[1]];
  45.             //splitting the integer into individual digits and saving them in the power source array
  46.             while (num1 > 0 )
  47.             {
  48.                 for(int b=counts[0]-1;b>=0;b--)
  49.                 {
  50.                 S[b]= num1 % 10;
  51.                 num1 = num1/ 10;
  52.                 }
  53.             }
  54.             //splitting the integer into individual digits and saving them in the LEDs array
  55.             while (num2 > 0 )
  56.             {
  57.                 for(int b=counts[1]-1;b>=0;b--)
  58.                 {
  59.                 L[b]= num2 % 10;
  60.                 num2 = num2/ 10;
  61.                 }
  62.             }
  63.             //QuickSort quick=new QuickSort();
  64.             //quick.quickSort(S, 0,counts[0]-1);
  65.             MaxNumofLEDs max=new MaxNumofLEDs();
  66.             int maxnum=max.MaxNum(S,L,counts[0],counts[1]);
  67.             System.out.println(maxnum);
  68.             for(int b=0;b<counts[0];b++)
  69.             System.out.println(L[b]);
  70.              /*int size=maxnum;
  71.              int m=S.length;
  72.              int n=L.length;
  73.              int []l= new int[size+1];
  74.              l[size]=0;
  75.              while(m>0 && n>0)
  76.              {
  77.                 if(S[m-1]==L[n-1])
  78.                 {
  79.                     l[--size]=S[m-1];
  80.                     m--;
  81.                     n--;
  82.                 }
  83.                 else if(S[m-1]>L[n-1])
  84.                 {
  85.                     m--;
  86.                 }
  87.                 else
  88.                     n--;       
  89.                 }
  90.                System.out.println(l);*/
  91.             }
  92.             catch (FileNotFoundException e)
  93.             {
  94.                   e.printStackTrace();
  95.  
  96.  
  97.             }
  98.         }
  99. }
  100.  
  101. public class MaxNumofLEDs {
  102.     public int MaxNum( int[] S, int[] L, int m, int n )
  103.       {
  104.         //max holds the number of leds that are connected with the power source
  105.         int max[][] = new int[m+1][n+1];
  106.         //the initial value if one of the circuts is empty is zero
  107.         for(int i=0;i<=m;i++)
  108.         {
  109.             max[i][0]=0;
  110.  
  111.         }
  112.         for(int j=0;j<=n;j++)
  113.         {
  114.             max[0][j]=0;
  115.  
  116.         }
  117.        
  118.         for (int i=1; i<=m; i++)
  119.         {
  120.           for (int j=1; j<=n; j++)
  121.           {
  122.             if (S[i-1] == L[j-1])
  123.                 max[i][j] = max[i-1][j-1] + 1;
  124.             else
  125.                 max[i][j] = Math.max(max[i-1][j], max[i][j-1]);
  126.           }
  127.         }
  128.         for (int k = 0; k <= S.length; k++) {
  129.             for (int j = 0; j <= L.length; j++) {
  130.                
  131.                 System.out.print(max[k][j]+" ");
  132.             }
  133.             System.out.println("");
  134.         }
  135.         //returns the maximum number of LEDs
  136.       return max[m][n];
  137.       }
  138.  
  139. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement