Koin Paling Sedikit
Tukar uang dengan koin sesedikit mungkin untuk pecahan sembarang.
Di negeri dongeng, koin yang beredar bernilai aneh, misalnya 1, 3, dan 4. Greedy gagal di sini: untuk 6, greedy memberi 4 + 1 + 1, padahal 3 + 3 hanya dua koin. Temukan banyak koin paling sedikit dengan cara yang selalu benar.
Masukan
Baris pertama berisi N (1 sampai 20) dan jumlah uang J (0 sampai 20000). Baris kedua berisi N nilai koin yang berbeda, masing-masing 1 sampai 10000. Setiap jenis koin tersedia tanpa batas.
Keluaran
Banyak koin paling sedikit untuk membentuk tepat J, atau Tidak mungkin bila tidak bisa.
Contoh masukan dan keluaran
Contoh 1
Masukan
3 6 1 3 4
Keluaran
2
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Misalkan minimum[t] adalah banyak koin paling sedikit untuk total t. Untuk membentuk t, koin terakhir yang dipakai pasti salah satu jenis koin.
Petunjuk 2
minimum[t] = 1 + minimum[t - k] untuk koin k terbaik. Isi dari total 0 sampai J, dengan minimum[0] = 0.