Kos Minimum untuk Menghubungkan Dua Kumpulan Mata

1595. Kos Minimum untuk Menghubungkan Dua Kumpulan Mata

Kesukaran: Sukar

Topik: Tatasusunan, Pengaturcaraan Dinamik, Manipulasi Bit, Matriks, Bitmask

Anda diberi dua kumpulan mata di mana kumpulan pertama mempunyai saiz₁ mata, kumpulan kedua mempunyai saiz₂ mata, dan saiz₁ > = saiz₂.

Kos sambungan antara mana-mana dua titik diberikan dalam saiz₁ x saiz₂ matriks dengan kos[i][j] ialah kos penyambungan titik i daripada kumpulan pertama dan titik j kumpulan kedua. Kumpulan disambungkan jika setiap titik dalam kedua-dua kumpulan disambungkan kepada satu atau lebih titik dalam kumpulan bertentangan. Dalam erti kata lain, setiap titik dalam kumpulan pertama mesti disambungkan kepada sekurang-kurangnya satu titik dalam kumpulan kedua dan setiap titik dalam kumpulan kedua mesti disambungkan kepada sekurang-kurangnya satu titik dalam kumpulan pertama.

Pulangan kos minimum yang diperlukan untuk menyambung dua kumpulan.

Contoh 1:

• Input: kos = [[15, 96], [36, 2]]
• Output: 17
• Penjelasan: Cara optimum untuk menghubungkan kumpulan ialah:

  1--A
  2--B
  This results in a total cost of 17.

Contoh 2:

• Input: kos = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]
• Output: 4
• Penjelasan: Cara optimum untuk menghubungkan kumpulan ialah:

  1--A
  2--B
  2--C
  3--A
  This results in a total cost of 4.

Perhatikan bahawa terdapat berbilang titik disambungkan ke titik 2 dalam kumpulan pertama dan titik A dalam kumpulan kedua. Ini tidak penting kerana tiada had bilangan mata yang boleh disambungkan. Kami hanya mengambil berat tentang jumlah kos minimum.

Contoh 3:

• Input: kos = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8] ]
• Output: 10

Kekangan:

• saiz₁ == kos.panjang
• saiz₂ == kos[i].panjang
• 1 <= saiz₁, saiz₂ <= 12
• saiz₁ >= saiz₂
• 0 <= kos[i][j] <= 100

Petunjuk:

1. Setiap titik di sebelah kiri sama ada akan disambungkan ke titik tepat yang telah disambungkan ke beberapa nod kiri, atau subset nod di sebelah kanan yang tidak disambungkan ke mana-mana nod
2. Gunakan pengaturcaraan dinamik dengan bitmasking, di mana keadaan akan berada (bilangan mata yang diberikan dalam kumpulan pertama, bitmask mata yang diberikan dalam kumpulan kedua).

Penyelesaian:

Kami boleh memanfaatkan pengaturcaraan dinamik dengan bitmasking. Ideanya adalah untuk meminimumkan kos dengan mempertimbangkan setiap titik dalam kumpulan pertama dan cuba menyambungkannya ke semua titik dalam kumpulan kedua.

Pendekatan Pengaturcaraan Dinamik (DP) dengan Bitmasking

Langkah-langkah:

1. Perwakilan Negeri:

   • Gunakan dp jadual DP[i][topeng] di mana:
     • i ialah indeks dalam kumpulan pertama (dari 0 hingga saiz1-1).
     • mask ialah bitmask yang mewakili titik mana dalam kumpulan kedua telah disambungkan.

2. Peralihan Negeri:

   • Untuk setiap titik dalam kumpulan pertama, cuba sambungkannya ke setiap titik dalam kumpulan kedua, kemas kini jadual DP dengan sewajarnya.
   • Jika titik baharu dalam kumpulan kedua disambungkan, kemas kini bit yang sepadan dalam topeng.

3. Kes Asas:

   • Mulakan dengan dp[0][0] = 0 (tiada sambungan pada mulanya).

4. Matlamat:

   • Kira kos minimum untuk dp[saiz1][(1 << saiz2) - 1], yang mewakili penyambungan semua titik daripada kedua-dua kumpulan.

Mari laksanakan penyelesaian ini dalam PHP: 1595. Kos Minimum untuk Menghubungkan Dua Kumpulan Mata

  
  
  Penjelasan:



Dp tatasusunan DP[i][mask] menyimpan kos minimum untuk menyambung mata i pertama daripada kumpulan 1 dengan mata dalam kumpulan 2 seperti yang ditunjukkan oleh topeng.
Gelung bersarang berulang pada setiap gabungan i dan mask, cuba mencari kos optimum dengan mempertimbangkan semua sambungan yang mungkin.
Akhirnya, penyelesaian mengira kos minimum mengambil kira senario di mana beberapa titik dalam kumpulan kedua mungkin masih tidak disambungkan, memastikan semua titik disambungkan.


Pendekatan ini mengendalikan kekangan masalah dengan cekap dan memastikan kos minimum untuk menyambungkan dua kumpulan.

Pautan Kenalan
Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:


LinkedIn
GitHub



          

            
        
Atas ialah kandungan terperinci Kos Minimum untuk Menghubungkan Dua Kumpulan Mata. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!