Algoritma pengaturcaraan dinamik dalam C++ dan kemahiran aplikasinya

Pengaturcaraan Dinamik (DP) ialah algoritma yang cekap digunakan untuk menyelesaikan beberapa masalah dengan sub-masalah yang bertindih dan sifat sub-struktur yang optimum. Terdapat beberapa teknik untuk meningkatkan kecekapan apabila melaksanakan algoritma pengaturcaraan dinamik dalam bahasa C++. Artikel ini akan memperkenalkan algoritma pengaturcaraan dinamik dan teknik aplikasinya dalam C++.

Idea utama algoritma pengaturcaraan dinamik adalah untuk menguraikan masalah kepada satu siri sub-masalah, dan apabila menyelesaikan setiap sub-masalah, kekalkan keadaan dan gunakan keadaan ini untuk mengelakkan pengiraan berulang. Algoritma pengaturcaraan dinamik boleh menyelesaikan beberapa masalah pengiraan yang mahal kerana ia hanya perlu mengira setiap submasalah sekali dan bukannya setiap masa.

1. Tiga elemen pengaturcaraan dinamik

Algoritma pengaturcaraan dinamik perlu memenuhi tiga elemen:

(1) Substruktur optimum: Penyelesaian optimum masalah mengandungi penyelesaian optimum bagi sub-masalahnya.

(2) Tiada kesan selepas: Semua keadaan dalam proses hanya berkaitan dengan keadaan semasa dan tiada kaitan dengan keadaan sebelumnya.

(3) Submasalah bertindih: Berbilang submasalah bertindih antara satu sama lain untuk mengelakkan pengiraan berulang.

2. Klasifikasi asas pengaturcaraan dinamik

Terdapat dua klasifikasi asas pengaturcaraan dinamik: satu ialah pengaturcaraan dinamik berasaskan negeri, dan satu lagi ialah pengaturcaraan dinamik berasaskan keputusan. Pengaturcaraan dinamik berasaskan negeri merujuk kepada menyimpan penyelesaian kepada setiap sub-masalah semasa pengiraan, dan kemudian mengira penyelesaian kepada masalah yang lebih besar berdasarkan nilai penyelesaian ini. Keadaan biasanya disimpan menggunakan struktur data, seperti tatasusunan. Pengaturcaraan dinamik berasaskan keputusan merujuk kepada menentukan penyelesaian optimum kepada masalah yang lebih besar berdasarkan penyelesaian optimum bagi setiap sub-masalah semasa pengiraan. Kaedah ini sering digunakan untuk menyelesaikan masalah pengoptimuman atau semasa mengira nilai minimum.

3. Kemahiran aplikasi pengaturcaraan dinamik

Apabila melaksanakan algoritma pengaturcaraan dinamik dalam C++, terdapat beberapa kemahiran aplikasi yang boleh meningkatkan kecekapan. Teknik ini termasuk:

(1) Gunakan pemalar dan bukannya subskrip tatasusunan: Dalam beberapa masalah pengaturcaraan dinamik, berbilang akses kepada tatasusunan diperlukan. Pada masa ini, anda boleh menggantikan subskrip tatasusunan dengan pemalar, yang boleh mempercepatkan akses. Contohnya:

for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        dp[i][j] = max(dp[i-1][j],dp[i][j-1])+1;
    }
}

Anda boleh menggunakan pembolehubah k untuk menggantikan subskrip tatasusunan dp:

for(int k=2;k<=n+m;k++){
    for(int i=1;i<=n;i++){
        int j = k-i;
        if(j<1 || j>m) continue;
        dp[i][j] = max(dp[i-1][j],dp[i][j-1])+1;
    }
}

(2) Mengoptimumkan tatasusunan: Dalam beberapa masalah pengaturcaraan dinamik, saiz tatasusunan adalah sangat besar, yang mungkin menyebabkan had memori . Pada masa ini, anda boleh menggunakan tatasusunan bergolek atau dimensi pertama tatasusunan dua dimensi untuk menyimpan hasil perantaraan. Contohnya:

int dp[N][M];
for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
        dp[i][j] = max(dp[i-1][j],dp[i][j-1])+1;
    }
}

boleh dioptimumkan untuk:

int dp[2][M];
for(int i=0;i<N;i++){
    int cur = i%2, pre = (i+1)%2;
    for(int j=0;j<M;j++){
        dp[cur][j] = max(dp[pre][j],dp[cur][j-1])+1;
    }
}

(3) Menjimatkan ruang: Dalam beberapa masalah pengaturcaraan dinamik, hanya keadaan terkini yang perlu disimpan dan bukannya keseluruhan tatasusunan. Pada masa ini, anda boleh menggunakan tatasusunan menatal untuk menyimpan hanya keadaan terkini.

(4) Elakkan pengiraan berulang: Dalam sesetengah masalah pengaturcaraan dinamik, mungkin terdapat sub-masalah berulang. Pada masa ini, anda boleh menggunakan carian yang dihafal atau pengaturcaraan dinamik bawah ke atas untuk mengelakkan pengiraan berulang.

4. Contoh pengaturcaraan dinamik

Berikut ialah beberapa contoh masalah pengaturcaraan dinamik:

(1) Jujukan Fibonacci: Jujukan Fibonacci bermakna bermula dari 0 dan 1, setiap nombor adalah sama dengan dua sebelumnya Jumlah bagi nombor. Contohnya, 0, 1, 1, 2, 3, 5, 8, 13, 21.

Formula rekursi ialah: f[n] = f[n-1] + f[n-2]

Menggunakan algoritma pengaturcaraan dinamik, ia boleh direalisasikan seperti berikut:

int dp[N];
dp[0] = 0;
dp[1] = 1;
for(int i=2;i<=n;i++){
    dp[i] = dp[i-1] + dp[i-2];
}

(2) Masalah beg ransel: Knapsack masalah bermakna terdapat N item, setiap item mempunyai berat dan nilai. Diberi kapasiti C sebuah beg beg, cari nilai maksimum yang boleh dimuatkan tanpa melebihi kapasiti beg beg itu.

Menggunakan algoritma pengaturcaraan dinamik, anda boleh mencapai perkara berikut:

int dp[N][C];
for(int i=0;i<N;i++){
    for(int j=0;j<C;j++){
        dp[i][j] = 0;
    }
}
for(int i=0;i<N;i++){
    for(int j=0;j<=C;j++){
        if(j>=w[i]){
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
        }
        else{
            dp[i][j] = dp[i-1][j];
        }
    }
}

Di atas adalah pengenalan ringkas kepada algoritma pengaturcaraan dinamik dan teknik aplikasinya dalam C++. Untuk masalah pengaturcaraan dinamik yang kompleks, kerumitan masa dan kerumitan ruang juga perlu dipertimbangkan. Oleh itu, apabila melaksanakan algoritma pengaturcaraan dinamik, adalah perlu untuk mempertimbangkan pelbagai faktor dan memilih kaedah yang sesuai.

Atas ialah kandungan terperinci Algoritma pengaturcaraan dinamik dalam C++ dan kemahiran aplikasinya. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!