## IMPLEMENTASI 0-1 KNAPSACK MENGGUNAKAN ALGORITMA DYNAMIC PROGRAMMING PADA APLIKASI PERHITUNGAN HARGA SATUAN PRODUK PERCETAKAN BERBASIS WEB (STUDI KASUS: CV TUNAS UTAMA)
(a) Husni Teja Sukmana, (b) Arief Ardiyuanda
(a) Staf Pengajar Sains dan Teknologi Universitas Islam Negeri Syarif Hidayatullah Jakarta
(b) Mahasiswa Fakultas Sains dan Teknologi Universitas Islam Negeri Syarif Hidayatullah Jakarta

## ABSTRAK
Harga merupakan salah satu faktor kepuasan pelanggan. Perusahaan harus menentukan harga yang sesuai dengan harapan konsumen. Dalam menentukan harga satuan produk maka perusahaan harus mengetahui biaya produksi produk tersebut.  Untuk  mengetahui  biaya  produksi  maka  dibutuhkan  perhitungan  terhadap  faktor  produksi  dan  salah  satunya adalah  biaya bahan baku.  Bahan baku  kertas  pada bidang  percetakan  diasumsikan  sebagai permasalahan  0  1  knapsack dan  menggunakan  dynamic  programming  dalam  penyelesaiannya.  Metode  pengembangan  sistem  menggunakan  model proses  rapid  application  development  karena  aplikasi  yang  akan  dibuat  menggunakan  komponen-komponen  yang  sudah ada  dan  merupakan  aplikasi  sederhana.  Aplikasi  dibuat  berbasis  web  dengan  menggunakan  PHP  sebagai  bahasa pemrograman untuk membuat aplikasi dan MySQL sebagai perangkat lunak Sistem Manajemen Basis Data. Aplikasi dapat memaksimalkan bahan baku sehingga meminimalisir biaya produksi dan berdampak langsung pada harga satuan produk.
Keywords : 0-1 Knapsack, Dynamic Programming, Harga Satuan Produk

## 1. PENDAHULUAN
Kepuasan pelanggan ( Customer Satisfaction )
ditentukan oleh persepsi pelanggan atas performance produk  atau  jasa  dalam  memenuhi harapan  pelanggan.  Pelanggan  merasa  puas  apabila harapannya  terpenuhi  atau  akan  sangat  puas  jika harapan pelanggan terlampaui. Terdapat lima faktor utama yang menentukan tingkat kepuasan pelanggan  yaitu  kualitas  produk,  harga,  kualitas pelayanan, emosional, kemudahan untuk mendapatkan produk atau jasa tersebut.
CV.  Tunas  Utama  merupakan  salah  satu perusahaan  yang  bergerak  di  bidang  percetakan. Layaknya  sebuah  perusahaan  pada  umumnya, kepuasan  pelanggan  sangat  dikedepankan  terutama masalah  harga.  Dalam  menentukan  harga  sebuah produk, diperlukan perhitungan biaya produksi yang dikeluarkan. Terdapat empat faktor yang mempengaruhi  biaya  produksi  yaitu  bahan  baku, tenaga kerja, overhead pabrik, dan pengusaha.
Perusahaan  harus  menghitung  empat  faktor yang  telah  disebutkan,  salah  satunya  adalah  biaya
bahan  baku.  Pada  bidang  percetakan  bahan  baku yang  digunakan  adalah  kertas. Terdapat  beberapa jenis  kertas  yang  memiliki  beberapa  ukuran panjang dan lebar, perusahaan harus bisa memilih ukuran  mana  yang  akan  digunakan  untuk meminimalisir biaya bahan baku
sehingga  dapat  meminimalisir  biaya  produksi yang  berdampak  pada  harga  pokok  produksi. Harga  pokok  produksi  yang  didapat  digunakan untuk menentukan harga jual sebuah produk.
Untuk  mengatasi  masalah  perhitungan harga satuan produk dibuat sebuah sistem berbasis web.  Sedangkan  untuk  penentuan  bahan  baku yang  digunakan  pada  proses  produksi  maka dilakukan penerapan algoritma dynamic programming dalam penghitungannya
2. LANDASAN TEORI

## 2.1 Algoritma
Algoritma  adalah  kumpulan  instruksi/perintah /langkah  yang  berhingga  jumlahnya,  dituliskan secara sistematis, dan digunakan untuk menyelesaikan masalah/persoalan logika dan matematika dengan bantuan komputer (Sismoro,2005:29).

## 2.2 Dynamic Programming
Dynamic Programming adalah sebuah metode yang dapat  digunakan  saat  permasalahan  dapat  diurai menjadi beberapa permasalahan. Dynamic programming menyelesaikan  setiap  permasalahan hanya  sekali  kemudian  jawaban  tersebut  disimpan dalam sebuah tabel, itu dilakukan untuk menghindari  perhitungan  kembali  permasalahan yang ditemui selanjutnya.(Cormen,2002:323).
Algoritma dynamic  programming dapat dipecah menjadi 4 langkah rangkaian :
1. Karakteristikan  bahwa  masalah  adalah  solusi optimal.
2. Secara berulang mendefinisikan nilai dari solusi optimal.
3. Menghitung  nilai  solusi  optimal  dengan  cara bottom-up.
4. Membangun  solusi  optimal  dari  informasi  yang telah didapat.
Pada dynamic  programming menggunakan teknik bottom-up .  Ada  tiga  maksud  dalam  teknik bottom-up yaitu;
1. Mulai  dengan  bagian  permasalahan  yang  paling kecil
2. Kombinasikan  solusi  yang  didapatkan    dan ukuran dinaikkan
3. Kerjakan hingga dicapai solusi permasalah asli.
Dynamic programming
menggunakan prinsip-prinsip  optimal,  artinya  setiap  bagian  dari penyelesaian  yang  dijalankan  harus  optimal,  solusi bagian  tersebut  lalu  dikombinasikan  sehingga menghasilkan solusi yang optimal.

## 2.3 Knapsack Problem
Knapsack  Problem dapat  digambarkan sebagai  berikut:  Seorang  Pencuri  merampok  toko, menemukan sejumlah n benda, benda ke i memiliki keuntungan v dollar dan berat w pon. Pencuri ingin mengambil barang yang berharga sebanyak mungkin,  namun  ia  hanya  bisa  membawa  barang seberat W pon.( Cormen,2002:382) Dari  pengertian  di  atas  maka  muncul  dua permasalahan knapsack yaitu fractional  knapsack dan 0-1  knapsack  problem .  Contoh  penerapan  dari permasalahan  knapsack  adalah  pemotongan  bahan
baku  manufaktur.  Penjelasan  dari  kedua  versi adalah sebagai berikut :
1. Fractional knapsack problem
Maksud  dari fractional  knapsack adalah objek-objek  yang  tersedia  boleh  diambil sebagian  saja.  Misal  terdapat  objek  yang mempunyai berat 5 kg dengan nilai Rp. 5000, maka  diperbolehkan  hanya  mengambil  2  kg dengan nilai Rp. 2000.
2. 0-1 knapsack problem
Inti  dari  knapsack  0-1  adalah  objek  yang tersedia harus diambil secara keseluruhan atau tidak sama sekali
for w ← 0 to W do c[0,w] ←0 end for for i ← 1 to n do c[i,0] ← 0 end for for i ← 1 to n do for w=0 to W do if w[i] ≤ w then if v[i] + c[ i,w-w[i] ] > c[i – 1, w ] then
c[i,w] ←v[i] + c[i-1, w-w[i] ]
else c[i,w] ← c [i–1,w]
end if else c[i,w] ← c[i-1,w] end if end for
end for
Gambar  1.  Algoritma  Dynamic  Programming pada  0-1 Knapsack
2.4 Biaya Biaya adalah semua pengeluaran untuk mendapatkan barang/jasa dari pihak ketiga (Kuswadi,2006:60).

## 2.5 Produksi
Produksi  adalah  suatu  usaha  atau  kegiatan  untuk menambah  kegunaan  (nilai  guna)  suatu  barang. Kegunaan  suatu  barang  akan  bertambah  bila memberikan  manfaat  baru  atau  lebih  dari  bentuk semula (Putong,2005:203).

## 2.6 Biaya Produksi
Biaya  Produksi  adalah  semua  pengeluaran  yang dilakukan  oleh  perusahaan  untuk  memperoleh faktor-faktor  produksi  dan  bahan-bahan  mentah yang  akan  digunakan  untuk  menciptakan  barang-
barang  yang  di  produksikan  perusahaan  tersebut (sadono,2006:205)

## 2.7 Harga Satuan Produk
Harga  satuan  produk  atau  harga  pokok produksi adalah perhitungan yang mencakup semua biaya  yang  telah  diadakan  untuk  suatu  produk sampai  barang  itu  terjual,  memberikan  informasi yang penting untuk penentuan harga jual (Gilarso,2003:128).
Tujuan kalkulasi harga satuan produk adalah
1. Sebagai dasar untuk menentukan harga jual.
2. Sebagai alat untuk mengawasi efisiensi perusahaan.
3. Untuk penentuan besarnya laba/rugi.
4. Sebagai pegangan dalam  memilih cara produksi yang paling efisien.

## 3. METODOLOGI PENELITIAN

## 3.1 Pengumpulan Data

## 3.1.1 Studi Lapangan
Pada  teknik  observasi  ini,  penulis  mempelajari secara  langsung  proses  perhitungan  biaya produksi  di      CV.  Tunas  Utama,    hal  ini dilakukan  untuk  memahami  dan  mendapatkan informasi jelas seputar proses perhitungan bahan baku  secara  khusus  maupun  perhitungan  biaya produksi secara umum.

## 3.1.2 Studi Pustaka
Penulis  membaca  dan    mempelajari  buku-buku mengenai dynamic  programming terutama  pada masalah 0  1  knapsack yang  menjadi  masalah pada  penentuan  bahan  baku  yang  akan digunakan pada proses produksi serta mempelajari perhitungan yang dikeluarkan pada tahap produksi atau biasa disebut biaya produksi, serta  buku-buku  lainnya  yang  berkaitan  dengan masalah pada penulisan ini.

## 3.2 Pengembangan Sistem
Dalam  penelitian  ini  metode  pengembangan sistem yang digunakan adalah Rapid Application  Development (RAD).  RAD  adalah sebuah  model  proses  pengembangan  perangkat lunak sekuensial linear yang menekankan siklus pengembangan cepat. Model RAD ini merupakan  adaptasi  "kecepatan  tinggi"  dari model sekuensial linear di mana pengembangan cepat  dicapai  dengan  menggunakan  model pendekatan  konstruksi  berbasis  komponen.  Jika kebutuhan  dipahami  dengan  baik,  proses  RAD memungkinkan  tim  pengembang  menciptakan
"sistem  fungsional  yang  utuh"  dalam  periode waktu  periode  yang  sangat  pendek  kira-kira 60-90 hari. (Pressman,2010: 82).
Gambar 2. The RAD Model

## 4. HASIL DAN PEMBAHASAN

## 4.1 Communication
CV.  Tunas  Utama  membutuhkan  adanya aplikasi  yang  berguna  untuk  melakukan perhitungan  biaya  produksi  terutama  pada perhitungan  penentuan  bahan  baku  yang  akan digunakan pada proses produksi.
Perhitungan  biaya  produksi  yang  telah didapatkan sebagai output aplikasi perhitungan  biaya  produksi  ini,  digunakan sebagai  pertimbangan  penentuan  harga  jual kepada konsumen.

## 4.2 Planning
Berdasarkan permasalahan yang telah diketahui  pada  tahap  sebelumnya,  maka  yang harus  diakomodasi  oleh  aplikasi  yang  akan dibuat  seperti  perhitungan  biaya  bahan  baku yang  digunakan  untuk  menghitung  biaya produksi, kemudian perhitungan biaya produksi  yang  digunakan  untuk  menghitung harga pokok produksi dan selanjutnya perhitungan  harga  jual  kepada  konsumen. Dapat diketahui juga proses bisnis yang terjadi serta  data-data  yang  diperlukan  seperti  data kertas,  proses  dan  finishing  yang  akan digunakan  untuk  perhitungan  biaya  produksi itu sendiri.
Communication Planning Modelling Business modelling Data modeling Process modelling Construction Component reuse Automatic code generation Testing 6 0 – 9 0 da ys Deployment
Integration Delivery Feedback
60 – 90 days
4.3 Modelling
4.3.1 Business Modelling
Pemodelan ini
dilakukan untuk menggambarkan  urutan  aktifitas  yang menghasilkan suatu nilai atau objek yang dapat  dilihat  bagi  satu  pihak  atau  entitas tertentu.
.

## Gambar 3. Use Case Diagram
4.3.2 Data Modelling
Berdasarkan observasi yang telah dilakukan  peneliti,  maka  dibutuhkan tabel-tabel  untuk  penyimpanan  data, seperti  tabel  admin  sebagai  penyimpan data account administrator ,  tabel  kertas sebagai  penyimpan  data  jenis  kertas, harga kertas dan ukuran awal kertas, tabel proses  sebagai  penyimpan  data  proses dan  harga  cetak,  tabel  finishing  sebagai penyimpan  data  proses  dan  harga finishing,  dan  tabel  ukuran  sebagai penyimpan  data  ukuran  potong  standar kertas.

## 4.3.3 Process Modelling
Pada tahap sebelumnya telah
didefinisikan  data  yang  dibutuhkan,  data ini kemudian ditransformasi untuk mendapatkan aliran informasi yang mungkin dan diperlukan untuk mengimplementasikan fungsi bisnis.
Gambar 3. Flowchart Perhitungan Bahan Baku
Gambar 4. Flowchart Perhitungan Harga Satuan Produk

## 4.3.4 Pemodelan Knapsack
Algoritma  dynamic  programming  akan digunakan  sebagai  penentuan  bahan baku yang akan digunakan pada proses produksi.  Berikut  merupakan  contoh implementasi algoritma dynamic programming  pada  suatu  kasus  yang terjadi  pada  aplikas  perhitungan  harga satuan  produk,  bagaimana  aplikasi menentukan  pola  pemotongan  dari kertas  besar  (A)  menjadi  potongan kertas kecil (B):
Pengguna Menghitung harga satuan Menghitung harga satuan Memasukkan data kertas Administrator Menghitung biaya bahan baku Merubah data kertas Menghapus data kertas Memasukkan data proses Merubah data proses Menghapus data proses
Memasukkan data finishing Merubah data finishing Menghapus data finishing Memasukkan data ukuran
Merubah data ukuran Menghapus data ukuran Merubah password Mulai Quantitty, jenis kertas,ukuran, potongan Selesai Biaya bahan baku Biaya bahan baku           Quantity/potongan x harga Mulai quantity, ukuran, jenis kertas, proses, finishing,potongan Selesai Harga Satuan Produk Biaya produksi         biaya bahan baku + proses + finishing quantity Harga Satuan Produk         Biaya Produksi * 1.5 2 3 1 A
Terdapat  ukuran  awal  kertas  pada gambar  A  dengan  P=  3  dan  L=2  akan  di potong  pada  gambar  B  menjadi  ukuran P1=2  dan  L1=1,  berapakan  potongan  yang akan dihasilkan?
Langkah  1  :  menentukan  variabel-variabel yang  akan  dipergunakan  untuk  perhitungan knapsack.  Berikut  variabel  yang  telah ditentukan:
Ruang -> W = L = 2 Jumlah  objek  yang  akan  dipotong  -> n=(P1,L1) = 2 Berat -> w =(w1,w2)=(P1,L1)= (2,1) Keuntungan -> v=(v1,v2)= (P/P2, P/P1)= (3,1)
Langkah  2    :    inisialisasikan  array  [0,0] dengan nilai 0  karena tidak ada objek yang dipilih.
Langkah  3  :  isi  tabel  berupa  array  dengan algoritma yang telah diketahui.

## 4.4 Construction
Pada  tahap  ini  mengimplementasikan  algoritma pada  aplikasi  perhitungan  harga  satuan  produk dengan  menggunakan  bahasa  pemrograman PHP versi 5.2.2 serta MYSQL versi 5.0.41.

## 4.5 Deployment

## 4.5.1 Pengenalan Tampilan
Memperkenalkan  tampilan  aplikasi  perhitungan harga satuan produk kepada pengguna.

## 4.5.2 Pengujian
Pengujian  berikut  dilakukan  dengan memasukkan berbagai variabel
Gambar 5. Hasil Perhitungan Bahan Baku
Gambar  6.  Hasil  Perhitungan  Harga  Satuan Produk
Penerapan dynamic programming pada penentuan bahan baku produksi menghasilkan perhitungan  yang  lebih  optimal  dan  akurat. Perhitungan  tersebut  kemudian  digunakan sebagai  salah  satu  faktor  untuk  menentukan harga satuan produk.

## 4.5.3 Implementasi
Pada  tahap  ini  dilakukan  pengarahan  cara penggunaan  aplikasi  perhitungan.  Setelah dapat  berjalan  dengan  baik  maka  aplikasi  ini sudah  dapat  diterapkan  pada  perusahaan percetakan.

## 5. KESIMPULAN
1. Aplikasi  dapat  menghitung  biaya  produksi dengan  variabel input yang  telah  ditentukan perusahaan.
2. Aplikasi  mampu  menentukan  ukuran  kertas yang  akan  dipakai  sebagai  bahan  baku produksi.
3. Berhasil mengimplementasikan metode dynamic programming pada masalah optimalisasi knapsack yang  terdapat  pada aplikasi  perhitungan  biaya  produksi  produk percetakan.

## 6. REFERENSI
[1] Cormen, Thomas H., et all. 2002. Introduction to Algorithms . New York: McGraw Hill.
[2] Hanchate, D. B dan Kurmi, A. J. 2007. Design and Analysis of Algorithms . Pune: Technical
Publications Pune. [3] Henrywae.2008. Sistem Informasi Percetakan .[Online]. Tersedia: http:www.ziddu.com/download/2703645/Plano.zi p.html.[4 Mei 2010].
[4] Irawan, Handi. 2002. 10 Prinsip Kepuasan Pelanggan . Jakarta: PT Elex Media Komputindo.
2
[5] Kadir, Abdul dan Heriyanto. 2005. Algoritma
Pemrograman Menggunakan C++. Jogyakarta: CV Andi Offset.
[6] Kamus Besar Bahasa Indonesia.
[7] Kellerer, Hans., et all. 2004. Knapsack Problems .
Berlin: Springer.
[8] Kuswadi. 2006. Memahami Rasio-Rasio Keuangan Bagi Orang Awam . Jakarta: PT Elex Media Komputindo. [9] Lew, A dan Mauch, H. 2007. Dynamic Programming A Computational Tool . Berlin: Springer. [10]  Munir, Rinaldi. 2007. Algoritma dan Pemrograman
Dalam Bahasa PASCAL dan C . Bandung: Informatika.
[11]  Musselman, A. Vernon dan Jackson, John H. 1996. Pengantar Ekonomi Perusahaan . Jakarta: Erlangga.
[12]  Pressman, Roger S. 2010. Software Engineering “A Practitioner’s Approach” . New York: McGraw Hill. [13]  Purwanto, Eko Budi. 2008. Perancangan dan Analisis Algoritma . Jogyakarta: Graha Ilmu.
[14]  Putong,Iskandar. 2005. Teori Ekonomi Mikro : Kajian Konvensional dan Wacana Syariah . Jakarta: Mitra Wacana Media. [15]  Ryan. 2007. Perancangan Program Aplikasi Optimalisasi  Biaya Produksi Cetak Dengan Metode Pendekatan Mundur  (Studi Kasus : Percetakan Paperindo Harsa ).[Online].Tersedia: http://library.binus.ac.id/e Colls/eThesis/Abstrak/2007-2-00473- MTIF%20Abstrak.pdf . [11 April 2010]. [16]  Sismoro, Heri. 2005. Logika Informatika, Algoritma dan Pemrograman Komputer. Jogyakarta: Jogyakarta. [17]  Sjukani. Moh. 2007. Algoritma (Algoritma dan Struktur Data 1) dengan C, C++ dan Java . Jakarta: Mitra Wacana Media. [18]  Shi, Nansi dan Murthy, V.K. 2003. Architectural Issues of Web-Enabled Electronic Business . Hershey: Idea Group Publishing. [19]  Soeharno. 2009. Teori Mikroekonomi . Jogyakarta:
CV Andi Offset.
[20]  Sukirno, Sadono. 2006. Pengantar Teori Mikro
Ekonomi . Jakarta: PT Raja Grafindo Persada. [21]  Sumarsono, Sonny. 2007. Ekonomi Mikro Teori dan Soal Latihan . Jogyakarta: Graha Ilmu. [22]  Tanadi, Kevin.2008. Perbandingan Algoritma yang dipakai dalam 2D Knapsack Problem .[Online].Tersedia: http://www.informatika. org/~rinaldi/Stmik/2007- 2008/Makalah2008/MakalahIF2251-2008-055.pdf. [30 Maret 2010]