Gagasan dasar pemrograman dinamis adalah untuk menguraikan masalah untuk diselesaikan menjadi beberapa sub-masalah, pertama-tama menyelesaikan sub-masalah, dan menyimpan solusi dari sub-masalah ini. Jika Anda perlu menggunakan solusi dari sub-masalah ini di masa depan ketika menyelesaikan sub-masalah yang lebih besar, Anda dapat secara langsung mengekstrak solusi yang dihitung ini untuk menghindari operasi yang berulang. Solusi untuk menyimpan subproblem dapat diisi menggunakan metode formulir, seperti menyimpan dalam array.
Gunakan contoh praktis untuk mencerminkan ide algoritmik pemrograman dinamis - masalah perubahan koin.
Deskripsi Pertanyaan:
Misalkan ada beberapa koin dan ada jumlah yang tidak terbatas. Silakan cari tahu jumlah minimum koin yang dapat membuat sejumlah perubahan tertentu. Sebagai contoh, beberapa jenis koin adalah [1, 3, 5], jumlah minimum koin dengan nilai nominal 2 adalah 2 (1, 1), jumlah minimum koin dengan nilai nominal 4 adalah 2 (1, 3), dan jumlah koin minimum dengan nilai nominal 11 adalah 3 (5, 5, 1 atau 5, 3, 3).
Analisis Masalah:
Asumsikan bahwa set koin yang berbeda adalah koin array [0, ..., n-1]. Kemudian temukan jumlah koin minimum dengan nilai nominal K, lalu fungsi hitung dan koin koin koin memenuhi kondisi ini:
hitung (k) = min (hitungan (k - koin [0]), ..., hitung (k - koin [n - 1])) + 1;
Dan rumus sebelumnya hanya berlaku jika kondisi k - koin [i]> = 0 && k - koin [i] <k terpenuhi.
Karena k- koin [i] <k, saat menghitung jumlah (k), hitungan (i) (i <- [0, k-1]) harus dipenuhi, jadi di sini melibatkan masalah backtracking.
Jadi kita dapat membuat matriks matriks [k + 1] [koin.length + 1], sehingga matriks [0] [j] semuanya diinisialisasi ke 0 nilai, dan simpan jumlah minimum koin dengan nilai nominal i dalam matriks [i] [koin.length].
Dan proses spesifiknya adalah sebagai berikut:
* K | Koin 1 3 5 Min * 0 0 0 0 0 0 * 1 1 0 0 1 * 2 2 0 2 * 3 3 1 0 3, 1 * 4 2 2 0 2, 2 * 5 3 3 1 3, 3, 1 * 6 2 2 2 2 2, 2, 2 * ...
Akhirnya, implementasi kode Java spesifik adalah sebagai berikut:
public static int backtrackingcoin (int [] koin, int k) {// metode backtracking + pemrograman dinamis if (koin == null || koin.length == 0 || k <1) {return 0; } int [] [] matriks = int int [k + 1] [koin.length + 1]; untuk (int i = 1; i <= k; i ++) {for (int j = 0; j <coins.length; j ++) {int prek = i - koin [j]; if (prek> -1) {// Hanya jika tidak kurang dari 0, Prek dapat ada dalam matriks array dan backtracking dapat dilakukan. matrix[i][j] = matrix[preK][coins.length] + 1;//The face value i is backtracking if (matrix[i][coins.length] == 0 || matrix[i][j] < matrix[i][coins.length]) {//If the current number of coins is the smallest, update the minimum number of coins in the min column matriks [i] [koin.length] = matriks [i] [j]; }}} return matrix [k] [Coins.length]; }Kode telah diuji, dan semua kasus uji yang diberikan oleh pertanyaan telah disahkan!
Meringkaskan
Di atas adalah seluruh konten artikel ini tentang kode implementasi masalah perubahan koin dari pemrograman dinamis Java. Saya harap ini akan membantu semua orang. Teman yang tertarik dapat terus merujuk ke topik terkait lainnya di situs ini. Jika ada kekurangan, silakan tinggalkan pesan untuk menunjukkannya. Terima kasih teman atas dukungan Anda untuk situs ini!