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.
