Program Algoritma Greedy di java

Algoritma Greedy adalah salah satu algoritma yang sering digunakan untuk memecahkan persoalan optimasi (persoalan mencari solusi optimum).
Contoh penukaran koin :
akan diberikan uang 450 dengan koin yang ditukar adalah 100, 50, 25, dan 15 berapa solusi minimumnya???
Berikut contoh program untuk mencari banyak koin dgn menggunakan algoritma greedy.

import java.io.DataInputStream;
class algoritmaGreedy
{
 public int i,j,k;
 
 // konstruktor
 algoritmaGreedy(){
 }
 
 // method untuk proses algoritma greedy
 void Greedy(int koin[], int hasil[],int jum[], int uang, int i)
 {
  int s [] = new int[uang];
  
  while(jum[i] < uang)
  {
   k=(int)(Math.random()*koin.length);
   s[hasil[i]] = koin[k];
   
   if((jum[i] + s[hasil[i]]) <= uang)
    System.out.print(s[hasil[i]]+" ");
   
   jum[i]+=s[hasil[i]];
   hasil[i]+=1; 
  }
  System.out.print("}");
  
  if (jum[i] == uang)
   System.out.println(" = "+hasil[i]+" koin");
   else
    System.out.println(" = Tidak ada solusi");
 }
 
 // method sorting
 void sorting(int data[], int n)
 {
  for(i=0;i<n-1;i++){
      for(j=0; j<n-1;j++)
       if(data[j]<data[j+1])
       {
        k=data[j];
        data[j]=data[j+1];
        data[j+1]= k;
       }
     }
 }
 
 // method untuk mencari solusi max n min
 void solusiGlobal(int data[],int jum[], int uang)
    {
     int bin[] = new int[data.length];
     j=0;
     for (i=0;i<data.length;i++)
     {
      if(jum[i]==uang){
       bin[j]=data[i];
       j+=1;
      } 
     }
     
     sorting(bin,bin.length);
     
     k=0;
     for(i=0;i<bin.length;i++)
      if(bin[i] != 0)
       k+=1;
       
     System.out.println("nSolusi Minimum : "+bin[k-1]);
     System.out.println("Solusi Maximum : "+bin[0]);
 }
}

class main
{
 public static void main (String[] args) throws Exception
 {
  DataInputStream entri = new DataInputStream(System.in);
  System.out.print("Masukan jumlah uang yg di tukar: ");
  int uang = Integer.parseInt(entri.readLine());
  System.out.print("Masukkan banyaknya koin: ");
  int n = Integer.parseInt(entri.readLine());
  int koin[] = new int[n];
  
  for(int i = 0;i<n;i++)
  {
   System.out.print("Koin ke-"+(i+1)+" : ");
   koin[i] = Integer.parseInt(entri.readLine());
  }
  
  System.out.print("Masukkan batas iterasi: ");
  int batas = Integer.parseInt(entri.readLine());
  int hasil[] = new int [batas];
  int jum[] = new int [batas];
  

  // instansiasi objek greedy
  algoritmaGreedy g = new algoritmaGreedy();
    
  for(int i =0;i<batas;i++)
  {
   System.out.print("nSolusi ke-"+(i+1)+" = {");
   g.Greedy(koin,hasil,jum,uang,i);
  }
  g.solusiGlobal(hasil,jum,uang);
 }
}

Read More

Program Mencetak Gapura dengan Java

Program berikut adalah program untuk mencetak deret angka berbentuk gapura(gapuro) yang berbasi OOP (Object Oriented Programming) atau pemrograman berorientasi objek.

import java.io.*;


class SegitigaAtas{
 protected int angka;
 
 public SegitigaAtas(){
 }
 
 public SegitigaAtas(int angka){
  this.angka=angka;
 }
 
 public void cetakGambar(){
  int batas = angka*2;
  int n = 1;
  int temp = batas-n;
  int angka1= angka;
  int angka2= angka;
  
  for(int i=0;i<angka;i++){
   for(int j=0;j<batas;j++){
    if(j>=temp){
     System.out.print(angka1++);
    }
    else
     System.out.print(" ");
   }
   
   for(int j=0;j<5;j++){
    System.out.print(" ");
   }
   
   for(int j=0;j<n;j++){
    System.out.print(angka2--);
   }
   
   System.out.println();
   temp--;
   n++;
   angka1=(angka-i)-1;
   angka2=angka;
  }
 }
}

class SegitigaBawah extends SegitigaAtas{
 public SegitigaBawah(){
  
 }
 
 public SegitigaBawah(int angka){
  super(angka);
 }
 
 private void showGambar(){
  int batas = angka*2;
  int n = 2;
  int temp = batas-n;
  for(int i=0;i<angka;i++){
   for(int j=0;j<batas;j++){
    if(j>=temp){
     System.out.print(i+1);
    }
    else
     System.out.print(" ");
   }
   
   for(int j=0;j<5;j++){
    System.out.print(" ");
   }
   
   for(int j=0;j<n;j++){
    System.out.print(i+1);
   }
   
   System.out.println();
   temp-=2;
   n+=2;
  }
 }
 
 public void cetakGambar(){
  super.cetakGambar();
  showGambar();
 }
}

public class gapuroM2{
 public static void main (String[] args) throws Exception {
  DataInputStream dis = new DataInputStream(System.in);
  System.out.print("Inputkan angka dibawah 10 : ");
  int angka = Integer.parseInt(dis.readLine());
  SegitigaBawah s = new SegitigaBawah(angka);
  s.cetakGambar();
 }
}

apabila program diatas dijalankan maka hasilnya adalah seperti dibawah ini:

Read More