Ransel Pendaki
Isi ransel dengan perbekalan bernilai setinggi mungkin, boleh dipotong.
Pendaki Gunung Rinjani membawa ransel yang hanya kuat menampung W kilogram. Perbekalannya berupa bahan curah seperti beras, gula, dan kacang, jadi boleh dibawa sebagian. Setiap bahan punya berat dan nilai manfaat. Berapa nilai manfaat terbesar yang bisa dibawa?
Masukan
Baris pertama berisi N (1 sampai 1000) dan W (1 sampai 100000). N baris berikutnya masing-masing berisi berat (1 sampai 10000) dan nilai (1 sampai 10000) sebuah bahan.
Keluaran
Nilai terbesar dengan tepat dua angka di belakang titik.
Contoh masukan dan keluaran
Contoh 1
Masukan
3 50 10 60 20 100 30 120
Keluaran
240.00
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Bahan yang paling berharga per kilogramnya sebaiknya diambil lebih dulu. Hitung rasio nilai dibagi berat untuk setiap bahan.
Petunjuk 2
Urutkan dari rasio tertinggi. Ambil seluruh bahan selama masih muat, lalu ambil sebagian dari bahan berikutnya untuk mengisi sisa ruang.