Cari bilangan laluan dengan berat W dalam pokok K-ary menggunakan C++

Dalam artikel ini, kami akan menggunakan C++ untuk mengira bilangan laluan dengan berat W dalam pokok K-ary. Kami telah diberikan pokok K-ary, iaitu pokok di mana setiap nod mempunyai anak K dan setiap tepi mempunyai berat, dengan berat berkurangan daripada 1 kepada K daripada nod kepada semua anak-anaknya.

Kita perlu mengira bilangan kumulatif laluan bermula dari nod akar yang mempunyai berat W dan sekurang-kurangnya satu tepi dengan berat M. Jadi, berikut adalah contoh:

Input : W = 4, K = 3, M = 2

Output : 6

Dalam masalah yang diberikan, kami akan menggunakan dp untuk mengurangkan kerumitan masa dan ruang. Dengan menggunakan penghafalan, kami boleh membuat program kami lebih cepat dan menyesuaikannya dengan kekangan yang lebih besar.

Kaedah

Dalam kaedah ini kita akan melintasi pokok dan menjejaki tepi dengan atau tanpa berat sekurang-kurangnya M dan berat bersamaan dengan W dan kemudian kita menambah jawapan.

Input

#include <bits/stdc++.h>
using namespace std;
int solve(int DP[][2], int W, int K, int M, int used){
   if (W < 0) // if W becomes less than 0 then return 0
       return 0;
    if (W == 0) {
        if (used) // if used is not zero then return 1
           return 1; //as at least one edge of weight M is included
       return 0;
   }
    if (DP[W][used] != -1) // if DP[W][used] is not -1 so that means it has been visited.
       return DP[W][used];
    int answer = 0;
   for (int i = 1; i <= K; i++) {
        if (i >= M)
           answer += solve(DP, W - i, K, M, used | 1); // if the condition is true
                                                    //then we will change used to 1.
       else
           answer += solve(DP, W - i, K, M, used);
   }
   return answer;
}
int main(){
   int W = 3; // weight.
   int K = 3; // the number of children a node has.
   int M = 2; // we need to include an edge with weight at least 2.
   int DP[W + 1][2]; // the DP array which will
   memset(DP, -1, sizeof(DP)); // initializing the array with -1 value
   cout << solve(DP, W, K, M, 0) << "\n";
   return 0;
}

Output

3

Penjelasan kod di atas

Dalam kaedah ini, mana-mana tepi dengan berat M disertakan sekurang-kurangnya sekali atau tidak. Kedua, kami mengira jumlah berat laluan jika ia sama dengan W.

Kami menambah jawapan dengan satu, menandakan laluan sebagai dilawati, meneruskan melalui semua laluan yang mungkin, dan mengandungi sekurang-kurangnya satu tepi dengan berat lebih besar daripada atau sama dengan M.

Kesimpulan

Dalam kertas ini, kami menggunakan pengaturcaraan dinamik untuk menyelesaikan masalah mencari bilangan laluan dengan berat W dalam pokok k-ary dengan kerumitan masa O(W*K).

Kami juga mempelajari program C++ dan kaedah lengkap (biasa dan cekap) untuk menyelesaikan masalah ini.

Atas ialah kandungan terperinci Cari bilangan laluan dengan berat W dalam pokok K-ary menggunakan C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!