Ransel Petualang
Pilih barang utuh yang paling bernilai tanpa melebihi daya tampung ransel.
Kali ini barangnya tidak bisa dipotong: tenda, kompor, senter, dan lain-lain. Setiap barang dibawa utuh atau ditinggal. Pilih barang yang total nilainya paling besar tanpa melebihi daya tampung ransel.
Masukan
Baris pertama berisi N (1 sampai 60) dan W (1 sampai 5000). N baris berikutnya masing-masing berisi berat (1 sampai 5000) dan nilai (1 sampai 100000) sebuah barang.
Keluaran
Total nilai terbesar yang bisa dibawa.
Contoh masukan dan keluaran
Contoh 1
Masukan
4 7 1 1 3 4 4 5 5 7
Keluaran
9
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Misalkan terbaik[c] adalah nilai terbesar dengan daya tampung c. Proses barang satu per satu: setiap barang dibawa atau tidak.
Petunjuk 2
Untuk setiap barang, perbarui terbaik[c] dari c = W turun sampai berat barang. Arah turun memastikan satu barang tidak terpakai dua kali.