BNPCHS 2009 - Final Round
H - Drum Minyak Pak Ricat
Author: Ricky Winata
Soal ini adalah tipikal soal dynamic programming, dimana kita diharuskan mencari solusi optimal dari berbagai solusi yang ada. Soal ini dapat kita selesaikan dengan menjalankan dua kali dynamic programming knapsack untuk mendapatkan jawabannya.
Kita akan menjalankan DP knapsack untuk pertama kali untuk mendapatkan semua kemungkinan isi dari drum dengan harga yang termurah, dengan relasi rekursi sbb :
Cd = kapasitas maksimal drum
M = jumlah paket
Ci = kapasitas pengisian paket ke i
Pi= harga paket ke i
Kemudian untuk DP knapsack kedua, kita akan memakai hasil dari DP pertama tadi untuk mendapatkan solusi optimal yang kita inginkan, dengan relasi rekursi sebagai berikut:
N = jumlah minyak yang akan di distribusikan
Cd = kapasitas maksimal drum
Pd = harga 1 drum
f1(i) = harga optimal dari knapsack pertama untuk kapasitas i dalam 1 drum
- Problem A - Teks Fibonacci
- Problem B - BeSaR DaN KeCiL
- Problem C - Rentang Terbesar
- Problem D - Merakit Komputer
- Problem E - Mario Bros
- Problem F - Kaca Patri
- Problem G - Jumlah Pembagi
- Problem H - Drum Minyak Pak Ricat
- Problem I - Jumlah Pangkat
- Problem J - Ordo Keprimaan
- Medalist
pertamax!
Eko Wibowo
7 Dec 09 at 11:42 pm
setelah di teliti, 10 problems yang ada, problem authornya beda2 smua :))
Felix J
8 Dec 09 at 12:34 am
Argghhhh, problem A dan G ngga akan pernah gw lupain !
Timotius Sakti
8 Dec 09 at 12:43 am
Wah soal2nya bagus2 loh…
Variasinya dan tingkat kesulitannya pas!
Hore… sekarang tidak ada alasan lagi untuk tidak nge-blog INC/ICPC 09 >:)
Felix Halim
8 Dec 09 at 10:56 am
kok blakangan ini write-upnya ngga ada storynya pak? spt write-up HS07 gt… pengen tau behind the scene-nya kayak apa
anyway, soalnya bagus2 & menarik, tapi banyak bgt euy
Angelina Veni
8 Dec 09 at 10:30 pm
mana?
mahli
10 Dec 09 at 4:24 pm
writeup icpc….~ >:)
Felix J
11 Dec 09 at 8:20 pm
gan, ada contoh kodingannya g tentang problem dari A-j tu???
kirimin dong.. thanks
martin muhar
14 May 10 at 5:12 pm