Tempat Pensil

Soal 3 Olimpiade Sains Mahasiswa 2007, Yogyakarta.

Deskripsi Soal :

Andi gemar mengoleksi pensil. Kian hari, koleksi pensilnya semakin banyak. Oleh karena itu dia berencana membeli tempat pensil baru di toko A untuk menampung N pensil koleksinya. Toko A menjual 2 jenis tempat pensil dengan harga dan kapasitas yang berbeda. Tempat pensil 1 berharga R1 dan dapat menyimpan J1 pensil, sedangkan tempat pensil 2 berharga R2 dan dapat menyimpan J2 pensil. Diberikan input N, R1, J1, R2, dan J2. Buatlah program yang mengoutputkan jumlah tempat pensil 1dan jumlah tempat pensil 2 yang harus dibeli Andi sehingga tempat pensil yang dibelinya tepat menampung N pensilnya. Jika tidak ada kombinasi sehingga tempat pensil yang dibelinya tepat menampung N pensil, maka outputkan ”Tidak jadi beli”

Contoh Input 1 :

47 2 4 5 7

Contoh Output1 :

10 1

Contoh Input 2 :

47 2 4 5 6

Contoh Output 2 :

Tidak jadi beli

Solusi :

Sekilas problem ini seperti problem knapsack. Tapi karena saya lupa bagaimana coding untuk knapsack(^_^’) dan tempat pensilnya hanya ada 2, maka saya tulis program dengan algoritma yang berbeda.

Pertama kita tentukan tempat pensil mana yang punya efisiensi yang lebih tinggi. Efisiensi kita definisikan sebagai kapasitas dibagi harga tempat pensil. Sebut saja TP1 adalah tempat pensil dengan efisiensi tinggi, dan TP2 untuk tempat pensil yang lain. Sedangkan KAP adalah kapasitas total dari tempat pensil yang dibeli Andi. Kemudian, semaksimal mungkin kita hanya membeli TP1, tetapi KAP tidak boleh lebih dari N. Selama KAP bukan sama dengan N dan jumlah TP1 yang dibeli Andi lebih dari sama dengan 0, maka jika KAP:

lebih dari N, maka kurangi jumlah TP1 yang dibeli.

kurang dari N, maka tambah jumlah TP2 yang dibeli.

Untuk lebih jelasnya, silahan lihat contoh listing program saya berikut ini

type tempat_pensil=record

r,j:integer;

end;

var n:integer;

data1,data2:tempat_pensil;

jml1,jml2,kap:integer;

procedure hitung(tp1,tp2:tempat_pensil;var jml1,jml2:integer);

begin

jml1:=n div tp1.j;

kap:=jml1*tp1.j;

while (kap<>n) and (jml1>=0) do

if kap<n then

begin

inc(jml2);

inc(kap,tp2.j);

end

else

begin

dec(jml1);

dec(kap,tp1.j);

end;

end;

begin

readln(n,data1.r,data1.j,data2.r,data2.j);

if (data1.j/data1.r)>(data2.j/data2.r) then

hitung(data1,data2,jml1,jml2)

else

hitung(data2,data1,jml2,jml1);

if kap=n then

writeln(jml1,’ ‘,jml2)

else

writeln(‘Tidak jadi beli’);

end.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s