1595年。 2 つのポイント グループを接続するための最小コスト
難易度: 難しい
トピック: 配列、動的プログラミング、ビット操作、行列、ビットマスク
点の 2 つのグループが与えられます。最初のグループのサイズは 1 ポイント、2 番目のグループのサイズは 2 ポイント、サイズ 1 > です。 = サイズ2.
任意の 2 点間の接続のコストは、size1 x size2 行列で与えられます。ここで、cost[i][j] は点 i を接続するコストです。最初のグループと 2 番目のグループの点 j。 両方のグループの各点が反対側のグループの 1 つ以上の点に接続されている場合、グループは接続されています。つまり、最初のグループの各点は 2 番目のグループの少なくとも 1 つの点に接続され、2 番目のグループの各点は最初のグループの少なくとも 1 つの点に接続されている必要があります。
2 つのグループを接続するために必要な最小コストを返します。
例 1:
1--A 2--B This results in a total cost of 17.
例 2:
1--A 2--B 2--C 3--A This results in a total cost of 4.
最初のグループのポイント 2 と 2 番目のグループのポイント A に複数のポイントが接続されていることに注意してください。接続できる点数に制限はないので問題ありません。私たちは最小の総コストのみを考慮します。
例 3:
制約:
ヒント:
解決策:
ビットマスクを使用した動的プログラミングを活用できます。このアイデアは、最初のグループの各ポイントを考慮し、それを 2 番目のグループのすべてのポイントに接続することでコストを最小限に抑えることです。
状態の表現:
状態遷移:
基本ケース:
目標:
このソリューションを PHP で実装してみましょう: 1595。 2 つのポイント グループを接続するための最小コスト
<?php /** * @param Integer[][] $cost * @return Integer */ function connectTwoGroups($cost) { ... ... ... /** * go to ./solution.php */ } // Example usage: $cost1 = [[15, 96], [36, 2]]; $cost2 = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]; $cost3 = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]]; echo connectTwoGroups($cost1) . "\n"; // Output: 17 echo connectTwoGroups($cost2) . "\n"; // Output: 4 echo connectTwoGroups($cost3) . "\n"; // Output: 10 ?>
このアプローチは問題の制約を効率的に処理し、2 つのグループを接続するためのコストを最小限に抑えます。
連絡先リンク
このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!
このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:
以上が2 つのポイント グループを接続するための最小コストの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。