Skripsi

Penerapan algoritma greedy dan pembuatan program komputer untuk menyelesaikan permasalahan knapsack 0-1 dan fractional knapsack / Yoyok Bakdar Muntoro

Abstrak
Permasalahan Knapsack merupakan salah satu bentuk permasalahan optimasi (maksimum atau minimum). Pada skripsi ini dibahas penyelesaian permasalahan Knapsack 0-1 dan Fractional Knapsack serta suatu program komputer untuk menyelesaikan permasalahan tersebut yang diberi nama program Greedy . Pada permasalahan Knapsack 0-1 variabel keputusan yang diperoleh yaitu xi bernilai 1 jika objek itu dipilih dan xi bernilai 0 jika objek tidak dipilih. Sedangkan pada permasalahan Fractional Knapsack variabel keputusan bernilai 0 8804 xi 8804 1. Untuk menyelesaikan permasalahan Knapsack 0-1 dan Fractional Knapsack digunakan algoritma Greedy dan Brute-Force. Cara penyelesaian menggunakan algoritma Greedy dibagi menjadi tiga strategi penyelesaian yaitu Greedy by weight Greedy by profit dan Greedy by density. Sedangkan pada algoritma Brute-Force dengan mendaftar semua himpunan bagian dari solusi jadi banyaknya himpunan bagian dari n elemen adalah sebanyak 2n. Pada skripsi ini permasalahan Knapsack 0-1 yang dibahas adalah masalah kapasitas maksimum tempat pembuangan sampah dan masalah investasi. Sedangkan permasalahan Fractional Knapsack yang dibahas adalah masalah keuntungan maksimum. Untuk mempermudah penyelesaian masalah Knapsack 0-1 dan Fractional Knpasack maka penulis membuat program komputer dengan bantuan pemrograman Delphi 7.0.

Informasi Detail

DDC

Rs 005.1 YOY p

Prodi

Skripsi (Sarjana)--Universitas Negeri Malang. Program Studi Matematika, 2007.

Deskripsi Fisik

ix, 85 hlm : il. : tab. ; 29 cm

Bahasa

Indonesia

No Reg

00024/KI/08

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang. 2007

Subjek

1. ALGORITMA GREEDY PENERAPAN
2. KOMPUTER PROGRAM
3. KNAPSACK

Pembimbing

1. PURWANTO ; 2. MIMIEP S. MADJA

Lampiran Berkas