Unbounded Knapsack Problem dalam Bahasa Java

Unbounded Knapsack Problem dalam Bahasa Java

Oleh : Jeffrey Hermanto Halimsetiawan [email protected]

tutorialpemrograman.wordpress.com 7 Februari 2010


Unbounded Knapsack Problem dalam Bahasa Java Penjelasan Problem : Seorang pendaki harus membawa 3 barang yaitu : makanan, obat-obatan dan baju. Makanan memiliki nilai 4, obat-obatan 3, dan baju 5 (baju memiliki nilai paling tinggi, dst). Untuk membawa barang-barang tersebut, sang pendaki menggunakan sebuah back pack dengan kapasitas 3 liter. Satu unit makanan memiliki ukuran 1 liter. Satu unit obat-obatan berukuran 1/4 liter. Dan satu unit baju berukuran 1/2 liter. 1. Justifikasi algoritma apakah yang bisa memaksimalkan nilai dari barang yang dibawa oleh pendaki. Jelaskan alasannya! 2. Buatlah algoritmanya! 3. Analysis running time dari algoritma yang anda kembangkan! 4. Implementasikan algoritma tersebut! Penjelasan Algoritma Dalam kasus di atas, diperlukan sebuah algoritma yang digunakan untuk mencari nilai yang optimum dari barang yang dibawa oleh pendaki dengan batas beban backpack pendaki. Agar didapatkan nilai yang optimal maka digunakan algoritma unbounded-knapsack untuk memecahkan permasalah di atas dengan pendekatan secara Dynamic Programming (DP). Algoritma unbounded knapsack atau yang disebut juga dengan integer-knapsack merupakan pengembangan dari algoritma knapsack dimana tidak ada batasan pengambilan jumlah sebuah item tetapi tetap memperhatikan batasan beban (weight). Karena seorang pendaki harus membawa minimal 1 untuk semua item barang, maka ada sedikit modifikasi algoritma unbounded knapsack yaitu setelah masing-masing diambil satu barang, baru dilakukan dynamic programming untuk mencari nilai yang maksimal dengan weight yang sudah dikurangi tersebut. Alasan menggunakan pendekatan secara dynamic programming karena greedy pada permasalahan knapsack di atas tidak ditemukan adanya greedy choice sehingga ada beberapa kasus dimana solusi greedy tidak optimal. Contoh kasusnya adalah sebagai berikut : MAKSIMUM WEIGHT = 3 ITEM Obat Baju Makanan

WEIGHT 0.25 0.4 0.95

VALUE 3 4 4

Weight setelah dikurangi semua item = 3 - 0.25 - 0.95 - 0.4 = 1.4 1. Greedy : W = 0.25 * 5 = 1.25 V =3*5 = 15 2. DP : W = 0.25 * 4 + 0.4 * 1 = 1.4 V =3*4+4*1

tutorialpemrograman.wordpress.com - 2009

RATIO ( VALUE / WEIGHT) 12 10 4.2

2


= 16 Dari contoh kasus di atas, Greedy menghasilkan value 15 sedangkan DP menghasilkan value 16 sehingga terbukti bahwa greedy tidak menghasilkan solusi yang optimal seperti pada dynamic programming. Langkah-langkah : Step 1: Characterize optimal subproblems Jika kita membawa item ke-j, kapasitas sisanya adalah nilai maksimum dari berat (weight-weights[j]) dari semua item yang mungkin dibawa. Step 2: Recursive algorithm

Pseudocode Rekursif : Algoritma recKnapsack(weight, best[],weights[],values[],itemKnown[],n) { i, space, max  -1, maxi  0, t; if (best[weight] >= 0) return best[weight]; for i from 1 to n if ((space = weight-weights[i]) >= 0) if ((t = recKnapsack(space) + values[i]) > max) { max  t; maxi  i; } best[weight]  max; itemKnown[weight]  maxi; return max; }

Step 3: Dynamic programming algorithm Pseudocode Algoritma Algoritma Knapsack(weight,best[],weights[],values[],n) { i, space, m, t, itemKnown[]; for m from 1 to weight for i from 0 to n { if ((space = m-weights[i]) >= 0) { t = best[space] + values[i]; if (t >= best[m]) { best[m]  t; itemKnown[m]  i; } } } for (m=weight; m>0 ; m-=weights[itemKnown[m]] )


3


solution[itemKnown[m]]++; return best[c]; }

Step 4 : Contructing optimal solution Algoritma printOptimalSolution(weight,best[],weights[],values[],itemKnown[],n) { wt  0, val  0; for j from 0 to n if ( best[j] > 0 ) { print ("%d of item %d (%d wt, %d val)\n", best[j], j, weights[j], values [j] ); wt += best [j] * weights[j]; val += best [j] * values [j]; } print("Total weight: %d\nTotal profit: %d\n", wt, val); }

Analisa Running Time t(n)

=

t(n)

=

Sehingga order of growth memenuhi :

Implementasi : package ub; import java.util.Arrays; import java.util.StringTokenizer; public class MainFrame extends javax.swing.JFrame { public MainFrame() { initComponents(); this.setTitle("FP PAAL Kelas A - Unbounded Knapsack"); } int unboundedKnapsack(int c, int n, int[] weights, int[] values, int[] solution ) { int i, space, m, t, best[], bestItem[]; bestItem = new int [c+1]; best = new int [c+1]; Arrays.fill(best, 0); for ( m = 1; m <= c; m++ ) for (i = 0; i < n; i++) { if ( (space = m-weights[i]) >= 0 ) { t = best[space] + values[i]; if ( t >= best[m] )


4


{ best[m] = t; bestItem[m] = i; } } for (int iterator : best){ areaOutput.append(iterator + " "); } areaOutput.append("\n"); } for (m=c; m>0 ; m-=weights[bestItem[m]] ) solution[bestItem[m]]++; return best[c]; } private void computeUnboundedKnapsack() { if (txtValues.getText().matches("") || txtWeights.getText().matches("") || txtMaxWeight.getText().matches("") || txtN.getText().matches("")){ areaOutput.setText("ERROR! Ada field yang masih kosong!"); return; } int n; int [] values; int [] weights;

// jumlah item // nilai dari setiap item // berat dari setiap item

int maxWeight, sisaWeight, totalValue = 0, i; double[] tempWeight; try { n = Integer.parseInt(txtN.getText()); weights = new int[n]; values = new int[n]; tempWeight = new double[n]; } catch (NumberFormatException nfe){ areaOutput.setText("ERROR! Input n tidak sesuai format!"); return; } try { maxWeight = Integer.parseInt(txtMaxWeight.getText()); } catch (NumberFormatException nfe){ areaOutput.setText("ERROR! Input kapasitas tidak sesuai format!"); return; } StringTokenizer tokensValues = new StringTokenizer(txtValues.getText()); StringTokenizer tokensWeight = new StringTokenizer(txtWeights.getText()); if (tokensValues.countTokens() != tokensWeight.countTokens() || tokensWeight.countTokens() != n){ areaOutput.setText("ERROR! Jumlah input values/weights dengan n tidak sesuai"); return; } double minWeight = maxWeight; for (i=0;i

5


tempWeight[i]= Double.parseDouble(awal); if(tempWeight[i]<minWeight) minWeight = tempWeight[i]; } System.out.println(minWeight); for (i=0;i 0 ) { areaOutput.append("Item ke-"+i+" sebanyak "+ solution[i] + " [Weight : "+weights[i] * minWeight +" - Value : "+values[i]+"]\n"); totalWeight += solution[i] * weights[i]; totalValue += solution[i] * values[i]; } areaOutput.append("Berat Total : "+totalWeight+"\nNilai Maksimum : "+totalValue+"\n"); } @SuppressWarnings("unchecked") // <editor-fold defaultstate="collapsed" desc="Generated Code">//GENBEGIN:initComponents private void initComponents() { txtWeights = new javax.swing.JTextField(); txtValues = new javax.swing.JTextField(); txtN = new javax.swing.JTextField(); jLabel1 = new javax.swing.JLabel(); jLabel2 = new javax.swing.JLabel(); jLabel3 = new javax.swing.JLabel(); jScrollPane1 = new javax.swing.JScrollPane(); areaOutput = new javax.swing.JTextArea(); getButton = new javax.swing.JButton(); jLabel4 = new javax.swing.JLabel(); txtMaxWeight = new javax.swing.JTextField(); setDefaultCloseOperation(javax.swing.WindowConstants.EXIT_ON_CLOSE);


6


jLabel1.setText("Weight[n]"); jLabel2.setText("Value[n]"); jLabel3.setText("n"); areaOutput.setColumns(20); areaOutput.setRows(5); jScrollPane1.setViewportView(areaOutput); getButton.setText("Get Optimal Value.."); getButton.addActionListener(new java.awt.event.ActionListener() { public void actionPerformed(java.awt.event.ActionEvent evt) { getButtonActionPerformed(evt); } }); jLabel4.setText("Max Weight"); javax.swing.GroupLayout layout = new javax.swing.GroupLayout(getContentPane()); getContentPane().setLayout(layout); layout.setHorizontalGroup( layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING) .addGroup(layout.createSequentialGroup() .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING) .addGroup(layout.createSequentialGroup() .addGap(131, 131, 131) .addComponent(getButton)) .addGroup(layout.createSequentialGroup() .addGap(38, 38, 38) .addComponent(jScrollPane1, javax.swing.GroupLayout.PREFERRED_SIZE, 317, javax.swing.GroupLayout.PREFERRED_SIZE))) .addContainerGap(45, Short.MAX_VALUE)) .addGroup(javax.swing.GroupLayout.Alignment.TRAILING, layout.createSequentialGroup() .addContainerGap() .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.TRAILING) .addGroup(layout.createSequentialGroup() .addComponent(jLabel4) .addGap(55, 55, 55) .addComponent(txtMaxWeight, javax.swing.GroupLayout.DEFAULT_SIZE, 139, Short.MAX_VALUE)) .addGroup(javax.swing.GroupLayout.Alignment.LEADING, layout.createSequentialGroup() .addComponent(jLabel3) .addGap(106, 106, 106) .addComponent(txtN, javax.swing.GroupLayout.DEFAULT_SIZE, 139, Short.MAX_VALUE)) .addGroup(layout.createSequentialGroup() .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING) .addGroup(javax.swing.GroupLayout.Alignment.TRAILING, layout.createSequentialGroup() .addComponent(jLabel1) .addGap(64, 64, 64)) .addGroup(layout.createSequentialGroup() .addComponent(jLabel2) .addGap(72, 72, 72))) .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.TRAILING, false) .addComponent(txtValues, javax.swing.GroupLayout.Alignment.LEADING)


7


.addComponent(txtWeights, javax.swing.GroupLayout.Alignment.LEADING, javax.swing.GroupLayout.DEFAULT_SIZE, 139, Short.MAX_VALUE)))) .addGap(139, 139, 139)) ); layout.setVerticalGroup( layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING) .addGroup(javax.swing.GroupLayout.Alignment.TRAILING, layout.createSequentialGroup() .addGap(27, 27, 27) .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.BASELINE) .addComponent(txtWeights, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE) .addComponent(jLabel1)) .addGap(18, 18, 18) .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.BASELINE) .addComponent(txtValues, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE) .addComponent(jLabel2)) .addGap(18, 18, 18) .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.BASELINE) .addComponent(jLabel3) .addComponent(txtN, 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(txtMaxWeight, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE) .addComponent(jLabel4)) .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED, 18, Short.MAX_VALUE) .addComponent(jScrollPane1, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE) .addGap(30, 30, 30) .addComponent(getButton) .addGap(20, 20, 20)) ); pack(); }// //GEN-END:initComponents private void getButtonActionPerformed(java.awt.event.ActionEvent evt) {//GENFIRST:event_getButtonActionPerformed areaOutput.setText(""); computeUnboundedKnapsack(); }//GEN-LAST:event_getButtonActionPerformed public static void main(String args[]) { java.awt.EventQueue.invokeLater(new Runnable() { public void run() { new MainFrame().setVisible(true); } }); } // Variables declaration - do not modify//GEN-BEGIN:variables private javax.swing.JTextArea areaOutput;


8


private javax.swing.JButton getButton; private javax.swing.JLabel jLabel1; private javax.swing.JLabel jLabel2; private javax.swing.JLabel jLabel3; private javax.swing.JLabel jLabel4; private javax.swing.JScrollPane jScrollPane1; private javax.swing.JTextField txtMaxWeight; private javax.swing.JTextField txtN; private javax.swing.JTextField txtValues; private javax.swing.JTextField txtWeights; // End of variables declaration//GEN-END:variables }

Screenshot Aplikasi


9

Unbounded Knapsack Problem dalam Bahasa Java

Recommend Documents