Top Banner
Tugas 2 Struktur Data & Algoritma II Aplikasi Algoritma Greedy Sifat Tugas : Kelompok (sesuai dengan pembagian awal) Batas pengumpulan : 23 Oktober 2014 Arsip pengumpulan : - CD yang berisi Source dan Exe program disertai manual .txt - Laporan (hard copy) Selesaikan permasalahan berikut dengan menerapkan algoritma greedy dengan menggunakan bahasa pemrograman java: 1. Masalah Penukaran Uang Diberikan uang senilai A. Tukar A dengan koin-koin/ uang yang ada. Berapa jumlah minimum koin yang diperlukan untuk penukaran tersebut. a. Input : Jumlah uang yang ditukar (A), Jumlah jenis koin (n) dan nominalnya (Ki s/d Kn) b. Output : Jumlah/cacah minimum uang/koin hasil penukaran & daftar uang/koin penukaran 2. Pemilihan Aktivitas (Activity Selection Problem) Misalkan kita memiliki S = {1, 2, …, n} yang menyatakan n buah aktivitas yang ingin menggunakan sebuah resource, yakni ruang pertemuan, yang hanya dapat digunakan satu aktivitas setiap saat. Tiap aktivitas i memiliki waktu mulai si dan waktu selesai fi, dimana si <= fi. Dua aktivitas i dan j dikatakan kompatibel jika interval [si, fi] dan [sj, fj] tidak bentrok. a. Input : Jumlah aktivitas (n), Waktu mulai aktivitas (Si), Waktu berakhir aktivitas(Fi) dengan syarat Si<=Fi (program harus bisa mengecek syarat ini) b. Output : Jumlah/cacah maksimum aktivitas yang bisa dilayani & daftar aktivitas yang dipilih 3. Integer Knapsack Seorang pedagang alat rumah tangga keliling harus memilih barang-barang yang akan dijual setiap harinya dengan batas daya mobil pick-up yang dimilikinya. Misalkan pedagang keliling tersebut memiliki n jenis barang untuk dijual dengan berat (w) dan keuntungan penjualan (p) yang berbeda-beda untuk tiap jenisnya. Mobil yang akan dipakai untuk mengangkut barang-barang tersebut hanya mampu menampung beban seberat K kg. a. Input : Jumlah barang(n), berat barang (Wi s/d Wn), keuntungan barang (Pi s/d Pn), Kapasitas Maksimum (K) b. Output : Total bobot teringan & total keuntungan maksimal Cat: Gunakan 3 pendekatan greedy by profit, greedy by weight, & greedy by density Keterangan : 1. Program dibuat terpisah untuk masing- masing problem dan memiliki fitur untuk mengulangi percobaan. 2. Interface program boleh menggunakan console ataupun GUI (preferred). -selamat menger j akan-
29

Tugas Algoritma Greedy

Apr 15, 2017

Download

Education

Welcome message from author
This document is posted to help you gain knowledge. Please leave a comment to let me know what you think about it! Share it to your friends and learn new things together.
Transcript
Page 1: Tugas Algoritma Greedy

Tugas 2 Struktur Data & Algoritma II

Aplikasi Algoritma Greedy

Sifat Tugas : Kelompok (sesuai dengan pembagian awal)

Batas pengumpulan : 23 Oktober 2014 Arsip pengumpulan : - CD yang berisi Source dan Exe program disertai manual.txt

- Laporan (hard copy)

Selesaikan permasalahan berikut dengan menerapkan algoritma greedy dengan menggunakan

bahasa pemrograman java:

1. Masalah Penukaran Uang

Diberikan uang senilai A. Tukar A dengan koin-koin/ uang yang ada. Berapa jumlah minimum koin yang diperlukan untuk penukaran tersebut.

a. Input : Jumlah uang yang ditukar (A), Jumlah jenis koin (n) dan nominalnya (Ki s/d Kn)

b. Output : Jumlah/cacah minimum uang/koin hasil penukaran & daftar uang/koin

penukaran

2. Pemilihan Aktivitas (Activity Selection Problem)

Misalkan kita memiliki S = {1, 2, …, n} yang menyatakan n buah aktivitas yang ingin menggunakan sebuah resource, yakni ruang pertemuan, yang hanya dapat digunakan satu

aktivitas setiap saat. Tiap aktivitas i memiliki waktu mulai si dan waktu selesai fi, dimana si <= fi. Dua aktivitas i dan j dikatakan kompatibel jika interval [si, fi] dan [sj, fj] tidak bentrok.

a. Input : Jumlah aktivitas (n), Waktu mulai aktivitas (Si), Waktu berakhir aktivitas(Fi) dengan syarat Si<=Fi (program harus bisa mengecek syarat ini)

b. Output : Jumlah/cacah maksimum aktivitas yang bisa dilayani & daftar aktivitas yang dipilih

3. Integer Knapsack

Seorang pedagang alat rumah tangga keliling harus memilih barang-barang yang akan dijual

setiap harinya dengan batas daya mobil pick-up yang dimilikinya. Misalkan pedagang keliling tersebut memiliki n jenis barang untuk dijual dengan berat (w) dan keuntungan penjualan (p) yang berbeda-beda untuk tiap jenisnya. Mobil yang akan dipakai untuk

mengangkut barang-barang tersebut hanya mampu menampung beban seberat K kg. a. Input : Jumlah barang(n), berat barang (Wi s/d Wn), keuntungan barang (Pi s/d Pn),

Kapasitas Maksimum (K) b. Output : Total bobot teringan & total keuntungan maksimal

Cat: Gunakan 3 pendekatan greedy by profit, greedy by weight, & greedy by density

Keterangan :

1. Program dibuat terpisah untuk masing-masing problem dan memiliki fitur untuk mengulangi percobaan.

2. Interface program boleh menggunakan console ataupun GUI (preferred).

-selamat mengerjakan-

Page 2: Tugas Algoritma Greedy

1. moneychange

a. duit.java package moneychange; import java.io.*; class duit { static int results[]=new int[100]; static int items[]=new int[100]; static int length=0; static int duit=0; void sort() { int j; boolean flag=true; int temp; while(flag) { flag=false; for(j=0;j<length;j++) { if(items[j]<items[j+1]) { temp=items[j]; items[j]=items[j+1]; items[j+1]=temp; flag=true; } } } } void input(int index, int value) { items[index]=value; } void length(int input) { length=input; } void duit(int input) { duit=input; } void calculate() { for(int i=0;i<100;i++) { results[i]=0; } int current=0; sort(); // int results[]=new int[20]; // int results[]={0}; for (int i =0;i<=length-1;i++) { for(;(current+items[i])<=duit;) { current+=items[i]; results[i]++; } }

Page 3: Tugas Algoritma Greedy

for(int i=length-1;i>=0;i--) System.out.println(items[i]+"="+results[i]); } int getResult(int index) { return results[index]; } int getItems(int index) { return items[index]; } }

b. Moneychange.java /* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */ package moneychange; /** * * @author Rifqi */ public class Moneychange { /** * @param args the command line arguments */ public static void main(String[] args) { // TODO code application logic here UI a = new UI(); a.main(args); } }

c. UI.java /* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */ package moneychange; /** * * @author Rifqi */ public class UI extends javax.swing.JFrame { /** * Creates new form UI */ public UI() { initComponents(); }

Page 4: Tugas Algoritma Greedy

/** * This method is called from within the constructor to initialize the form. * WARNING: Do NOT modify this code. The content of this method is always * regenerated by the Form Editor. */ @SuppressWarnings("unchecked") // <editor-fold defaultstate="collapsed" desc="Generated Code">//GEN-BEGIN:initComponents private void initComponents() { input1 = new javax.swing.JTextField(); total = new javax.swing.JTextField(); jumlah = new javax.swing.JComboBox(); input2 = new javax.swing.JTextField(); input3 = new javax.swing.JTextField(); input4 = new javax.swing.JTextField(); input5 = new javax.swing.JTextField(); input6 = new javax.swing.JTextField(); output1 = new javax.swing.JTextField(); output2 = new javax.swing.JTextField(); output3 = new javax.swing.JTextField(); output4 = new javax.swing.JTextField(); output5 = new javax.swing.JTextField(); output6 = new javax.swing.JTextField(); button = new javax.swing.JButton(); reset = new javax.swing.JButton(); setDefaultCloseOperation(javax.swing.WindowConstants.EXIT_ON_CLOSE); input1.setText("100"); input1.addActionListener(new java.awt.event.ActionListener() { public void actionPerformed(java.awt.event.ActionEvent evt) { input1ActionPerformed(evt); } }); total.setText("Uang"); total.setCursor(new java.awt.Cursor(java.awt.Cursor.TEXT_CURSOR)); jumlah.setModel(new javax.swing.DefaultComboBoxModel(new String[] { "1", "2", "3", "4", "5", "6" })); jumlah.setSelectedIndex(5); jumlah.addActionListener(new java.awt.event.ActionListener() {

Page 5: Tugas Algoritma Greedy

public void actionPerformed(java.awt.event.ActionEvent evt) { jumlahActionPerformed(evt); } }); input2.setText("200"); input2.addActionListener(new java.awt.event.ActionListener() { public void actionPerformed(java.awt.event.ActionEvent evt) { input2ActionPerformed(evt); } }); input3.setText("500"); input4.setText("1000"); input4.addActionListener(new java.awt.event.ActionListener() { public void actionPerformed(java.awt.event.ActionEvent evt) { input4ActionPerformed(evt); } }); input5.setText("2000"); input5.addActionListener(new java.awt.event.ActionListener() { public void actionPerformed(java.awt.event.ActionEvent evt) { input5ActionPerformed(evt); } }); input6.setText("5000"); input6.addActionListener(new java.awt.event.ActionListener() { public void actionPerformed(java.awt.event.ActionEvent evt) { input6ActionPerformed(evt); } }); output1.setEditable(false); output1.setText("Hasil"); output2.setEditable(false); output2.setText("Hasil"); output3.setEditable(false); output3.setText("Hasil"); output4.setEditable(false); output4.setText("Hasil"); output5.setEditable(false); output5.setText("Hasil"); output6.setEditable(false); output6.setText("Hasil"); button.setText("Calculate"); button.addActionListener(new java.awt.event.ActionListener() {

Page 6: Tugas Algoritma Greedy

public void actionPerformed(java.awt.event.ActionEvent evt) { buttonActionPerformed(evt); } }); reset.setText("Reset"); reset.addActionListener(new java.awt.event.ActionListener() { public void actionPerformed(java.awt.event.ActionEvent evt) { resetActionPerformed(evt); } }); javax.swing.GroupLayout layout = new javax.swing.GroupLayout(getContentPane()); getContentPane().setLayout(layout); layout.setHorizontalGroup( layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING) .addGroup(layout.createSequentialGroup() .addGap(84, 84, 84) .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING, false) .addGroup(layout.createSequentialGroup() .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.TRAILING, false) .addComponent(input1, javax.swing.GroupLayout.Alignment.LEADING) .addComponent(input2) .addComponent(total, javax.swing.GroupLayout.DEFAULT_SIZE, 55, Short.MAX_VALUE) .addComponent(input3) .addComponent(input4) .addComponent(input5) .addComponent(input6)) .addGap(32, 32, 32) .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING, false) .addComponent(jumlah, javax.swing.GroupLayout.Alignment.TRAILING, javax.swing.GroupLayout.PREFERRED_SIZE, 57, javax.swing.GroupLayout.PREFERRED_SIZE)

Page 7: Tugas Algoritma Greedy

.addComponent(output1, javax.swing.GroupLayout.DEFAULT_SIZE, 59, Short.MAX_VALUE) .addComponent(output2) .addComponent(output3) .addComponent(output4) .addComponent(output5) .addComponent(output6))) .addGroup(layout.createSequentialGroup() .addComponent(button) .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED, 8, Short.MAX_VALUE) .addComponent(reset))) .addContainerGap(170, Short.MAX_VALUE)) ); layout.setVerticalGroup( layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING) .addGroup(layout.createSequentialGroup() .addGap(27, 27, 27) .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.BASELINE) .addComponent(total, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE) .addComponent(jumlah, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE)) .addGap(19, 19, 19) .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.BASELINE) .addComponent(input1, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE) .addComponent(output1, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE)) .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED)

Page 8: Tugas Algoritma Greedy

.addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.BASELINE) .addComponent(input2, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE) .addComponent(output2, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE)) .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED) .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.BASELINE) .addComponent(input3, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE) .addComponent(output3, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE)) .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED) .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.BASELINE) .addComponent(input4, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE) .addComponent(output4, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE)) .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED) .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.BASELINE) .addComponent(input5, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE) .addComponent(output5,

Page 9: Tugas Algoritma Greedy

javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE)) .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED) .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.BASELINE) .addComponent(input6, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE) .addComponent(output6, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE)) .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.UNRELATED) .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.BASELINE) .addComponent(button) .addComponent(reset)) .addContainerGap(50, Short.MAX_VALUE)) ); pack(); }// </editor-fold>//GEN-END:initComponents private void input2ActionPerformed(java.awt.event.ActionEvent evt) {//GEN-FIRST:event_input2ActionPerformed // TODO add your handling code here: }//GEN-LAST:event_input2ActionPerformed private void input1ActionPerformed(java.awt.event.ActionEvent evt) {//GEN-FIRST:event_input1ActionPerformed // TODO add your handling code here: }//GEN-LAST:event_input1ActionPerformed private void buttonActionPerformed(java.awt.event.ActionEvent evt) {//GEN-FIRST:event_buttonActionPerformed // TODO add your handling code here: moneychange.duit d = new moneychange.duit(); int jembut = Integer.parseInt(total.getText()); d.duit(jembut);

Page 10: Tugas Algoritma Greedy

d.length(jumlah.getSelectedIndex() + 1); int i1 = Integer.parseInt(input1.getText()); d.input(0, i1); int i2 = Integer.parseInt(input2.getText()); d.input(1, i2); int i3 = Integer.parseInt(input3.getText()); d.input(2, i3); int i4 = Integer.parseInt(input4.getText()); d.input(3, i4); int i5 = Integer.parseInt(input5.getText()); d.input(4, i5); int i6 = Integer.parseInt(input6.getText()); d.input(5, i6); d.calculate(); output1.setText(String.valueOf(d.getResult(0))); output2.setText(String.valueOf(d.getResult(1))); output3.setText(String.valueOf(d.getResult(2))); output4.setText(String.valueOf(d.getResult(3))); output5.setText(String.valueOf(d.getResult(4))); output6.setText(String.valueOf(d.getResult(5))); input1.setText(String.valueOf(d.getItems(0))); input2.setText(String.valueOf(d.getItems(1))); input3.setText(String.valueOf(d.getItems(2))); input4.setText(String.valueOf(d.getItems(3))); input5.setText(String.valueOf(d.getItems(4))); input6.setText(String.valueOf(d.getItems(5))); }//GEN-LAST:event_buttonActionPerformed private void input4ActionPerformed(java.awt.event.ActionEvent evt) {//GEN-FIRST:event_input4ActionPerformed // TODO add your handling code here: }//GEN-LAST:event_input4ActionPerformed private void input5ActionPerformed(java.awt.event.ActionEvent evt) {//GEN-FIRST:event_input5ActionPerformed

Page 11: Tugas Algoritma Greedy

// TODO add your handling code here: }//GEN-LAST:event_input5ActionPerformed private void resetActionPerformed(java.awt.event.ActionEvent evt) {//GEN-FIRST:event_resetActionPerformed // TODO add your handling code here: input3.setText("0"); input1.setText("0"); input2.setText("0"); input4.setText("0"); input5.setText("0"); }//GEN-LAST:event_resetActionPerformed private void jumlahActionPerformed(java.awt.event.ActionEvent evt) {//GEN-FIRST:event_jumlahActionPerformed // TODO add your handling code here: }//GEN-LAST:event_jumlahActionPerformed private void input6ActionPerformed(java.awt.event.ActionEvent evt) {//GEN-FIRST:event_input6ActionPerformed // TODO add your handling code here: }//GEN-LAST:event_input6ActionPerformed /** * @param args the command line arguments */ public static void main(String args[]) { /* Set the Nimbus look and feel */ //<editor-fold defaultstate="collapsed" desc=" Look and feel setting code (optional) "> /* If Nimbus (introduced in Java SE 6) is not available, stay with the default look and feel. * For details see http://download.oracle.com/javase/tutorial/uiswing/lookandfeel/plaf.html */ try { for (javax.swing.UIManager.LookAndFeelInfo info : javax.swing.UIManager.getInstalledLookAndFeels()) { if ("Nimbus".equals(info.getName())) { javax.swing.UIManager.setLookAndFeel(info.getClassName()); break; } } } catch (ClassNotFoundException ex) { java.util.logging.Logger.getLogger(UI.class.getName()).log(java.util.logging.Level.SEVERE, null, ex);

Page 12: Tugas Algoritma Greedy

} catch (InstantiationException ex) { java.util.logging.Logger.getLogger(UI.class.getName()).log(java.util.logging.Level.SEVERE, null, ex); } catch (IllegalAccessException ex) { java.util.logging.Logger.getLogger(UI.class.getName()).log(java.util.logging.Level.SEVERE, null, ex); } catch (javax.swing.UnsupportedLookAndFeelException ex) { java.util.logging.Logger.getLogger(UI.class.getName()).log(java.util.logging.Level.SEVERE, null, ex); } //</editor-fold> /* Create and display the form */ java.awt.EventQueue.invokeLater(new Runnable() { public void run() { new UI().setVisible(true); } }); } // Variables declaration - do not modify//GEN-BEGIN:variables private javax.swing.JButton button; private javax.swing.JTextField input1; private javax.swing.JTextField input2; private javax.swing.JTextField input3; private javax.swing.JTextField input4; private javax.swing.JTextField input5; private javax.swing.JTextField input6; private javax.swing.JComboBox jumlah; private javax.swing.JTextField output1; private javax.swing.JTextField output2; private javax.swing.JTextField output3; private javax.swing.JTextField output4; private javax.swing.JTextField output5; private javax.swing.JTextField output6; private javax.swing.JButton reset; private javax.swing.JTextField total; // End of variables declaration//GEN-END:variables }

2. ResourceProject a. ActivityEngine.java

/*

Page 13: Tugas Algoritma Greedy

* To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */ /** * * @author Rifqi */ public class ActivityEngine { int clock[] = new int[1440]; int activities[][] = new int[100][1440]; int priority[] = new int[100]; int currentid = 0; void flush() { for (int i = 0; i < 100; i++) { for (int j = 0; j < 1440; j++) { activities[i][j] = 0; } clock[i] = 0; priority[i] = 0; } currentid = 0; } void setTimes(int id, int start, int end) { for (int i = start; i < end; i++) { activities[id][i] = 1; priority[id]++; } } void doActivity(int id) { for (int i = 0; i < 1440; i++) { if (activities[id][i] == 1) { clock[i] = id; } } } int prep(int hours, int minutes) { return (hours * 60) + minutes; } void createActivity(int hoursStart, int minutesStart, int hoursEnd, int minutesEnd) { currentid++; int start = prep(hoursStart, minutesStart); int end = prep(hoursEnd, minutesEnd); setTimes(currentid, start, end + 1); } void calculate() { for (int i = 1; i < currentid + 1; i++) { int id = i;

Page 14: Tugas Algoritma Greedy

for (int j = 1; j < currentid + 1; j++) { if (i != j) { if (activityCollisionCheck(i, j)) { id = priority[i] > priority[j] ? j : i; } } } doActivity(id); // System.out.println("asu "+id); } } boolean activityCollisionCheck(int id1, int id2) { for (int i = 0; i < 1440; i++) { if (activities[id1][i] > 0 && activities[id2][i] > 0) { return true; } else { } } return false; } String getResult() { String result = "Activities Done : " + String.valueOf(countActivities()) + "\nid\tStart Time\tEnd Time\n"; for (int i = 1; i < 1440; i++) { if (clock[i] != 0) { if (clock[i] != clock[i - 1]) { result += (String.valueOf(clock[i]) + "\t" + String.valueOf(i / 60) + "." + String.valueOf(i % 60) + "\t"); } if (clock[i] != clock[i + 1]) { result += (String.valueOf(i / 60) + "." + String.valueOf(i % 60) + "\n"); } } } return result; } int countActivities() { int activityDid = 0; for (int i = 0; i < 1440; i++) { if (clock[i] != 0) { if (clock[i] != clock[i + 1]) { activityDid++; } } } System.out.println(activityDid); return activityDid; } String listActivities() { String result = "id\tStart Time\tEnd Time\n";

Page 15: Tugas Algoritma Greedy

for (int j = 1; j < currentid + 1; j++) { for (int i = 1; i < 1440; i++) { // System.out.println("asu"); if (activities[j][i] != 0) { if (activities[j][i] != activities[j][i - 1]) { result += (String.valueOf(j) + "\t" + String.valueOf(i / 60) + "." + String.valueOf(i % 60) + "\t"); } if (activities[j][i] != activities[j][i + 1]) { result += (String.valueOf(i / 60) + "." + String.valueOf(i % 60) + "\n"); } } } } return result; } }

b. ResourceProject.java /* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */ /** * * @author Rifqi */ public class ResourceProject { /** * @param args the command line arguments */ public static void main(String[] args) { // TODO code application logic here UI a = new UI(); a.main(args); } }

c. UI.java /* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */ /**

Page 16: Tugas Algoritma Greedy

* * @author Rifqi */ public class UI extends javax.swing.JFrame { ActivityEngine e = new ActivityEngine(); /** * Creates new form UI */ public UI() { initComponents(); } /** * This method is called from within the constructor to initialize the form. * WARNING: Do NOT modify this code. The content of this method is always * regenerated by the Form Editor. */ @SuppressWarnings("unchecked") // <editor-fold defaultstate="collapsed" desc="Generated Code">//GEN-BEGIN:initComponents private void initComponents() { shr = new javax.swing.JTextField(); smin = new javax.swing.JTextField(); ehr = new javax.swing.JTextField(); emin = new javax.swing.JTextField(); jLabel2 = new javax.swing.JLabel(); jLabel3 = new javax.swing.JLabel(); add = new javax.swing.JButton(); jScrollPane1 = new javax.swing.JScrollPane(); textarea = new javax.swing.JTextArea(); Calc = new javax.swing.JToggleButton(); reset = new javax.swing.JButton(); setDefaultCloseOperation(javax.swing.WindowConstants.EXIT_ON_CLOSE); shr.setText("0"); smin.setText("0"); ehr.setText("0"); emin.setText("0"); jLabel2.setText("Start"); jLabel3.setText("End"); add.setText("Add"); add.addActionListener(new java.awt.event.ActionListener() {

Page 17: Tugas Algoritma Greedy

public void actionPerformed(java.awt.event.ActionEvent evt) { addActionPerformed(evt); } }); textarea.setColumns(20); textarea.setRows(5); jScrollPane1.setViewportView(textarea); Calc.setText("Calculate"); Calc.addActionListener(new java.awt.event.ActionListener() { public void actionPerformed(java.awt.event.ActionEvent evt) { CalcActionPerformed(evt); } }); reset.setText("Reset"); reset.addActionListener(new java.awt.event.ActionListener() { public void actionPerformed(java.awt.event.ActionEvent evt) { resetActionPerformed(evt); } }); javax.swing.GroupLayout layout = new javax.swing.GroupLayout(getContentPane()); getContentPane().setLayout(layout); layout.setHorizontalGroup( layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING) .addGroup(layout.createSequentialGroup() .addGap(27, 27, 27) .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.TRAILING) .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING) .addGroup(layout.createSequentialGroup() .addComponent(shr, javax.swing.GroupLayout.PREFERRED_SIZE, 25, javax.swing.GroupLayout.PREFERRED_SIZE) .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED) .addComponent(smin, javax.swing.GroupLayout.PREFERRED_SIZE, 25, javax.swing.GroupLayout.PREFERRED_SIZE))

Page 18: Tugas Algoritma Greedy

.addGroup(layout.createSequentialGroup() .addGap(17, 17, 17) .addComponent(jLabel2))) .addComponent(reset)) .addGap(18, 18, 18) .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING) .addComponent(Calc) .addComponent(add, javax.swing.GroupLayout.Alignment.TRAILING) .addGroup(javax.swing.GroupLayout.Alignment.TRAILING, layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING) .addGroup(layout.createSequentialGroup() .addComponent(ehr, javax.swing.GroupLayout.PREFERRED_SIZE, 25, javax.swing.GroupLayout.PREFERRED_SIZE) .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED) .addComponent(emin, javax.swing.GroupLayout.PREFERRED_SIZE, 25, javax.swing.GroupLayout.PREFERRED_SIZE)) .addGroup(layout.createSequentialGroup() .addGap(17, 17, 17) .addComponent(jLabel3)))) .addGap(18, 18, 18) .addComponent(jScrollPane1, javax.swing.GroupLayout.DEFAULT_SIZE, 313, Short.MAX_VALUE) .addContainerGap()) ); layout.setVerticalGroup( layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING) .addGroup(javax.swing.GroupLayout.Alignment.TRAILING, layout.createSequentialGroup() .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.TRAILING) .addGroup(layout.createSequentialGroup() .addGap(42, 42, 42) .addGroup(layout.createParallelGroup(j

Page 19: Tugas Algoritma Greedy

avax.swing.GroupLayout.Alignment.BASELINE) .addComponent(jLabel2) .addComponent(jLabel3)) .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED) .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.BASELINE) .addComponent(shr, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE) .addComponent(smin, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE) .addComponent(ehr, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE) .addComponent(emin, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE)) .addGap(18, 18, 18) .addComponent(add) .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED, 143, Short.MAX_VALUE) .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.BASELINE) .addComponent(Calc) .addComponent(reset))) .addGroup(layout.createSequentialGroup() .addContainerGap() .addComponent(jScrollPane1))) .addContainerGap()) ); pack(); }// </editor-fold>//GEN-END:initComponents private void addActionPerformed(java.awt.event.ActionEvent evt) {//GEN-FIRST:event_addActionPerformed

Page 20: Tugas Algoritma Greedy

// TODO add your handling code here: int sh = Integer.valueOf(shr.getText()); int sm = Integer.valueOf(smin.getText()); int eh = Integer.valueOf(ehr.getText()); int em = Integer.valueOf(emin.getText()); if (e.prep(sh, sm) - e.prep(eh, em) >= 0) { textarea.setText("INVALID START END TIME"); } else { e.createActivity(sh, sm, eh, em); textarea.setText(e.listActivities()); } shr.setText("0"); smin.setText("0"); ehr.setText("0"); emin.setText("0"); }//GEN-LAST:event_addActionPerformed private void CalcActionPerformed(java.awt.event.ActionEvent evt) {//GEN-FIRST:event_CalcActionPerformed // TODO add your handling code here: e.calculate(); textarea.setText(e.getResult()); }//GEN-LAST:event_CalcActionPerformed private void resetActionPerformed(java.awt.event.ActionEvent evt) {//GEN-FIRST:event_resetActionPerformed // TODO add your handling code here: e.flush(); textarea.setText("DONE"); }//GEN-LAST:event_resetActionPerformed /** * @param args the command line arguments */ public static void main(String args[]) { /* Set the Nimbus look and feel */ //<editor-fold defaultstate="collapsed" desc=" Look and feel setting code (optional) "> /* If Nimbus (introduced in Java SE 6) is not available, stay with the default look and feel. * For details see http://download.oracle.com/javase/tutorial/uiswing/lookandfeel/plaf.html */ try { for (javax.swing.UIManager.LookAndFeelInfo info : javax.swing.UIManager.getInstalledLookAndFeels()) {

Page 21: Tugas Algoritma Greedy

if ("Nimbus".equals(info.getName())) { javax.swing.UIManager.setLookAndFeel(info.getClassName()); break; } } } catch (ClassNotFoundException ex) { java.util.logging.Logger.getLogger(UI.class.getName()).log(java.util.logging.Level.SEVERE, null, ex); } catch (InstantiationException ex) { java.util.logging.Logger.getLogger(UI.class.getName()).log(java.util.logging.Level.SEVERE, null, ex); } catch (IllegalAccessException ex) { java.util.logging.Logger.getLogger(UI.class.getName()).log(java.util.logging.Level.SEVERE, null, ex); } catch (javax.swing.UnsupportedLookAndFeelException ex) { java.util.logging.Logger.getLogger(UI.class.getName()).log(java.util.logging.Level.SEVERE, null, ex); } //</editor-fold> /* Create and display the form */ java.awt.EventQueue.invokeLater(new Runnable() { public void run() { new UI().setVisible(true); } }); } // Variables declaration - do not modify//GEN-BEGIN:variables private javax.swing.JToggleButton Calc; private javax.swing.JButton add; private javax.swing.JTextField ehr; private javax.swing.JTextField emin; private javax.swing.JLabel jLabel2; private javax.swing.JLabel jLabel3; private javax.swing.JScrollPane jScrollPane1; private javax.swing.JButton reset; private javax.swing.JTextField shr; private javax.swing.JTextField smin; private javax.swing.JTextArea textarea; // End of variables declaration//GEN-END:variables }

3. Knapsack a. Knapsack.java

Page 22: Tugas Algoritma Greedy

package knapsack; class Knapsack { static int results[] = new int[100]; static int items[] = new int[100]; static int length = 0; static int duit = 0; void sort() { int j; boolean flag = true; int temp; while (flag) { flag = false; for (j = 0; j < length; j++) { if (items[j] < items[j + 1]) { temp = items[j]; items[j] = items[j + 1]; items[j + 1] = temp; flag = true; } } } } void input(int index, int value) { items[index] = value; } void setLength(int input) { length = input; } void setDuit(int input) { duit = input; } void calculate() { int current = 0; sort(); // int results[]=new int[20]; // int results[]={0}; for (int i = 0; i <= length - 1; i++) { for (; (current + items[i]) <= duit;) { current += items[i]; results[i]++; } } // for(int i=length-1;i>=0;i--) // System.out.println(items[i]+"="+results[i]); } int getResult(int index) { return results[index]; } int getItems(int index) { return items[index]; } }

b. knapsackm.java /*

Page 23: Tugas Algoritma Greedy

* To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */ package knapsack; /** * * @author khavid */ public class knapsackm { public static void main (String[] args){ Ui kentu = new Ui(); kentu.main(args); } }

c. Ui.java package knapsack; public class Ui extends javax.swing.JFrame { public Ui() { initComponents(); } //static void main(String[] args) { // throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates. // } /** * This method is called from within the constructor to initialize the form. * WARNING: Do NOT modify this code. The content of this method is always * regenerated by the Form Editor. */ @SuppressWarnings("unchecked") // <editor-fold defaultstate="collapsed" desc="Generated Code">//GEN-BEGIN:initComponents private void initComponents() { d = new javax.swing.JTextField(); jToggleButton1 = new javax.swing.JToggleButton(); h1 = new javax.swing.JLabel(); h2 = new javax.swing.JLabel(); h3 = new javax.swing.JLabel(); h4 = new javax.swing.JLabel(); h5 = new javax.swing.JLabel(); i1 = new javax.swing.JTextField(); i2 = new javax.swing.JTextField(); i3 = new javax.swing.JTextField(); i4 = new javax.swing.JTextField(); i5 = new javax.swing.JTextField();

Page 24: Tugas Algoritma Greedy

combobox = new javax.swing.JComboBox(); d.setText("Uang Awal"); d.addActionListener(new java.awt.event.ActionListener() { public void actionPerformed(java.awt.event.ActionEvent evt) { dActionPerformed(evt); } }); jToggleButton1.setText("RECEHKAN"); jToggleButton1.addActionListener(new java.awt.event.ActionListener() { public void actionPerformed(java.awt.event.ActionEvent evt) { jToggleButton1ActionPerformed(evt); } }); h1.setText("hasil"); h2.setText("hasil"); h3.setText("hasil"); h4.setText("hasil"); h5.setText("hasil"); combobox.setModel(new javax.swing.DefaultComboBoxModel(new String[] { "1", "2", "3", "4", "5" })); combobox.addActionListener(new java.awt.event.ActionListener() { public void actionPerformed(java.awt.event.ActionEvent evt) { comboboxActionPerformed(evt); } }); javax.swing.GroupLayout layout = new javax.swing.GroupLayout(this); this.setLayout(layout); layout.setHorizontalGroup( layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING) .addGroup(javax.swing.GroupLayout.Alignment.TRAILING, layout.createSequentialGroup() .addGap(126, 126, 126) .addComponent(d, javax.swing.GroupLayout.PREFERRED_SIZE, 98, javax.swing.GroupLayout.PREFERRED_SIZE) .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED, 24, Short.MAX_VALUE) .addComponent(jToggleButton1) .addGap(67, 67, 67))

Page 25: Tugas Algoritma Greedy

.addGroup(layout.createSequentialGroup() .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING) .addGroup(layout.createSequentialGroup() .addGap(102, 102, 102) .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING, false) .addComponent(i2, javax.swing.GroupLayout.Alignment.TRAILING) .addComponent(i1, javax.swing.GroupLayout.Alignment.TRAILING) .addComponent(i5, javax.swing.GroupLayout.DEFAULT_SIZE, 72, Short.MAX_VALUE) .addComponent(i4) .addComponent(i3)) .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.UNRELATED) .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING) .addComponent(h5, javax.swing.GroupLayout.PREFERRED_SIZE, 65, javax.swing.GroupLayout.PREFERRED_SIZE) .addComponent(h4, javax.swing.GroupLayout.PREFERRED_SIZE, 65, javax.swing.GroupLayout.PREFERRED_SIZE) .addComponent(h3, javax.swing.GroupLayout.PREFERRED_SIZE, 65, javax.swing.GroupLayout.PREFERRED_SIZE) .addComponent(h2, javax.swing.GroupLayout.PREFERRED_SIZE, 65, javax.swing.GroupLayout.PREFERRED_SIZE) .addComponent(h1, javax.swing.GroupLayout.PREFERRED_SIZE, 65, javax.swing.GroupLayout.PREFERRED_SIZE))) .addGroup(layout.createSequentialGroup() .addGap(30, 30, 30) .addComponent(combobox,

Page 26: Tugas Algoritma Greedy

javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE))) .addContainerGap(javax.swing.GroupLayout.DEFAULT_SIZE, Short.MAX_VALUE)) ); layout.setVerticalGroup( layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING) .addGroup(layout.createSequentialGroup() .addGap(20, 20, 20) .addComponent(d, javax.swing.GroupLayout.PREFERRED_SIZE, 32, javax.swing.GroupLayout.PREFERRED_SIZE) .addGap(3, 3, 3) .addComponent(combobox, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE) .addGap(1, 1, 1) .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.BASELINE) .addComponent(h1, javax.swing.GroupLayout.PREFERRED_SIZE, 21, javax.swing.GroupLayout.PREFERRED_SIZE) .addComponent(i1, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE)) .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED) .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING) .addComponent(h2, javax.swing.GroupLayout.Alignment.TRAILING, javax.swing.GroupLayout.PREFERRED_SIZE, 21, javax.swing.GroupLayout.PREFERRED_SIZE) .addComponent(i2, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE)) .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED) .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.BASELINE) .addComponent(h3, javax.swing.GroupLayout.PREFERRED_SIZE, 21,

Page 27: Tugas Algoritma Greedy

javax.swing.GroupLayout.PREFERRED_SIZE) .addComponent(i3, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE)) .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED) .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.BASELINE) .addComponent(h4, javax.swing.GroupLayout.PREFERRED_SIZE, 21, javax.swing.GroupLayout.PREFERRED_SIZE) .addComponent(i4, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE)) .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED) .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.BASELINE) .addComponent(h5, javax.swing.GroupLayout.PREFERRED_SIZE, 21, javax.swing.GroupLayout.PREFERRED_SIZE) .addComponent(i5, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE)) .addGap(29, 29, 29) .addComponent(jToggleButton1) .addContainerGap(43, Short.MAX_VALUE)) ); }// </editor-fold>//GEN-END:initComponents private void jToggleButton1ActionPerformed(java.awt.event.ActionEvent evt) {//GEN-FIRST:event_jToggleButton1ActionPerformed // Object index = d; Knapsack duit = new Knapsack(); int jembut = Integer.parseInt(d.getText()); duit.setDuit(jembut); duit.setLength(combobox.getSelectedIndex()); int input1 = Integer.parseInt(i1.getText()); duit.input(0, input1); int input2 = Integer.parseInt(i2.getText()); duit.input(1, input2); int input3 = Integer.parseInt(i3.getText()); duit.input(2, input3);

Page 28: Tugas Algoritma Greedy

int input4 = Integer.parseInt(i4.getText()); duit.input(3, input4); int input5 = Integer.parseInt(i5.getText()); duit.input(4, input5); duit.calculate(); // TODO add your handling code here: }//GEN-LAST:event_jToggleButton1ActionPerformed private void dActionPerformed(java.awt.event.ActionEvent evt) {//GEN-FIRST:event_dActionPerformed // TODO add your handling code here: }//GEN-LAST:event_dActionPerformed private void comboboxActionPerformed(java.awt.event.ActionEvent evt) {//GEN-FIRST:event_comboboxActionPerformed // TODO add your handling code here: }//GEN-LAST:event_comboboxActionPerformed // Variables declaration - do not modify//GEN-BEGIN:variables private javax.swing.JComboBox combobox; private javax.swing.JTextField d; private javax.swing.JLabel h1; private javax.swing.JLabel h2; private javax.swing.JLabel h3; private javax.swing.JLabel h4; private javax.swing.JLabel h5; private javax.swing.JTextField i1; private javax.swing.JTextField i2; private javax.swing.JTextField i3; private javax.swing.JTextField i4; private javax.swing.JTextField i5; private javax.swing.JToggleButton jToggleButton1; // End of variables declaration//GEN-END:variables /** * * @param args */ public static void main(String args[]) { System.out.println(); // java.awt.EventQueue.invokeLater(new Runnable() { // @Override // public void run() { java.awt.EventQueue.invokeLater(new Runnable() { @Override public void run() { new Ui().setVisible(true); } });

Page 29: Tugas Algoritma Greedy

// } // }); }