Cici Menerima 10 Buah Pekerjaan Rumah (PR) yang Harus Ia Kerjakan

-

Cici menerima 10 buah pekerjaan rumah (PR) yang harus ia kerjakan. Setelah melihat isi dari masing-masing PR, Cici memiliki  perkiraan,  berapa  lama  waktu  yang  diperlukan untuk  mengerjakan  masing-masing  PR  tersebut,  seperti terlihat pada tabel di bawah.


Sayangnya, ia tidak punya banyak waktu untuk mengerjakan semua PR. Cici menghitung bahwa ia hanya punya waktu total = 8 jam sebelum semua PR tersebut harus dikumpulkan. Cici ingin menentukan, PR mana yang harus ia kerjakan terlebih dahulu, dengan pertimbangan bahwa setiap PR memiliki nilai yang sama besarnya (terhadap nilai akhir Cici). Bantulah Cici menentukan PR yang mana saja yang harus ia kerjakan dalam waktu maksimal 8 jam, untuk mendapatkan total nilai akhir yang sebesar-besarnya.

Jawaban:

Untuk menentukan PR mana yang harus dikerjakan terlebih dahulu oleh Cici dengan tujuan mendapatkan total nilai akhir yang sebesar-besarnya dalam waktu maksimal 8 jam, kita dapat menggunakan pendekatan Greedy Algorithm. Berikut adalah langkah-langkahnya:

1. Mengurutkan PR berdasarkan waktu pengerjaan secara menaik. Dalam hal ini, kita akan mengurutkan PR berdasarkan waktu pengerjaan dalam jam dari yang terkecil hingga terbesar:

No. 9, PR I, Waktu Pengerjaan (Jam) 0,5
No. 4, PR D, Waktu Pengerjaan (Jam) 0,5
No. 3, PR C, Waktu Pengerjaan (Jam) 1
No. 6, PR F, Waktu Pengerjaan (Jam) 1
No. 8, PR H, Waktu Pengerjaan (Jam) 1
No. 1, PR A, Waktu Pengerjaan (Jam) 1,5
No. 10, PR J, Waktu Pengerjaan (Jam) 2
No. 7, PR G, Waktu Pengerjaan (Jam) 2,5
No. 2, PR B, Waktu Pengerjaan (Jam) 3
No. 5, PR E, Waktu Pengerjaan (Jam) 4

2. Mulai dari PR dengan waktu pengerjaan terkecil, tambahkan PR satu per satu ke dalam daftar PR yang akan dikerjakan oleh Cici selama total waktu pengerjaan PR tersebut tidak melebihi 8 jam.

  • PR I (Waktu Pengerjaan: 0,5 jam): Total waktu pengerjaan = 0,5 jam (kurang dari 8 jam), tambahkan PR I ke daftar.
  • PR D (Waktu Pengerjaan: 0,5 jam): Total waktu pengerjaan = 1 jam (kurang dari 8 jam), tambahkan PR D ke daftar.
  • PR C (Waktu Pengerjaan: 1 jam): Total waktu pengerjaan = 2 jam (kurang dari 8 jam), tambahkan PR C ke daftar.
  • PR F (Waktu Pengerjaan: 1 jam): Total waktu pengerjaan = 3 jam (kurang dari 8 jam), tambahkan PR F ke daftar.
  • PR H (Waktu Pengerjaan: 1 jam): Total waktu pengerjaan = 4 jam (kurang dari 8 jam), tambahkan PR H ke daftar.
  • PR A (Waktu Pengerjaan: 1,5 jam): Total waktu pengerjaan = 5,5 jam (kurang dari 8 jam), tambahkan PR A ke daftar.
  • PR J (Waktu Pengerjaan: 2 jam): Total waktu pengerjaan = 7,5 jam (kurang dari 8 jam), tambahkan PR J ke daftar.
3. PR yang tersisa adalah PR G, PR B, dan PR E. Namun, jika PR G ditambahkan ke daftar, total waktu pengerjaan akan melebihi 8 jam. Oleh karena itu, Cici tidak dapat mengerjakan PR G, PR B, dan PR E dalam waktu maksimal 8 jam.

Sebagai hasilnya, PR yang harus dikerjakan oleh Cici dalam waktu maksimal 8 jam adalah sebagai berikut:
  • PR I
  • PR D
  • PR C
  • PR F
  • PR H
  • PR A
  • PR J
Dengan mengerjakan PR tersebut, Cici akan mendapatkan total nilai akhir yang sebesar-besarnya dengan mempertimbangkan batasan waktu yang ada.