首页  >  文章  >  后端开发  >  连接两组点的最低成本

连接两组点的最低成本

王林
王林原创
2024-09-01 06:34:061024浏览

1595。连接两组点的最低成本

难度:

主题:数组、动态规划、位操作、矩阵、位掩码

您将获得两组点,其中第一组大小为 1 点,第二组大小为 2 点,大小为 1 > 点。 = 大小2.

任意两点之间的连接成本以大小 1 x size2 矩阵给出,其中 cost[i][j] 是连接点 i 的成本第一组和第二组的 j 点。如果两个组中的每个点都连接到相反组中的一个或多个点,则这些组已连接。换句话说,第一组中的每个点必须连接到第二组中的至少一个点,第二组中的每个点必须连接到第一组中的至少一个点。

返回连接两个组所需的最低成本

示例1:

Minimum Cost to Connect Two Groups of Points

  • 输入: 成本 = [[15, 96], [36, 2]]
  • 输出: 17
  • 说明:连接组的最佳方式是:
  1--A
  2--B
  This results in a total cost of 17.

示例2:

Minimum Cost to Connect Two Groups of Points

  • 输入: 成本 = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]
  • 输出: 4
  • 说明:连接组的最佳方式是:
  1--A
  2--B
  2--C
  3--A
  This results in a total cost of 4.

请注意,有多个点连接到第一组中的点 2 和第二组中的点 A。这并不重要,因为可以连接的点数没有限制。我们只关心最低的总成本。

示例 3:

  • 输入: 成本 = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8] ]
  • 输出: 10

约束:

  • 大小1 == cost.length
  • 大小2 == 成本[i].长度
  • 1 1,尺寸2
  • 尺寸1>=尺寸2
  • 0

提示:

  1. 左侧的每个点要么连接到已连接到某个左侧节点的精确点,要么连接到右侧未连接到任何节点的节点的子集
  2. 使用带有位掩码的动态规划,其中状态将为(第一组中分配的点的数量,第二组中分配的点的位掩码)。

解决方案:

我们可以利用带有位掩码的动态编程。这个想法是通过考虑第一组中的每个点并尝试将其连接到第二组中的所有点来最小化成本。

具有位掩码的动态规划 (DP) 方法

步骤:

  1. 国家代表

    • 使用 DP 表 dp[i][mask],其中:
      • i 是第一组中的索引(范围从 0 到 size1-1)。
      • mask 是一个位掩码,表示第二组中的哪些点已连接。
  2. 状态转换:

    • 对于第一组中的每个点,尝试将其连接到第二组中的每个点,相应地更新 DP 表。
    • 如果连接了第二组中的新点,则更新掩码中的相应位。
  3. 基本案例

    • 从 dp[0][0] = 0 开始(最初没有连接)。
  4. 目标

    • 计算 dp[size1][(1

让我们用 PHP 实现这个解决方案:1595。连接两组点的最低成本

<?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
?>

解释:

  • DP 数组 dp[i][mask] 存储将第 1 组中的前 i 个点与第 2 组中的点连接起来的最小成本,如 mask 所示。
  • 嵌套循环迭代 i 和 mask 的每个组合,尝试通过考虑所有可能的连接来找到最佳成本。
  • 最终,该方案会考虑第二组中某些点可能仍未连接的情况,计算最小成本,确保所有点都已连接。

这种方法有效地处理了问题的约束,并确保连接两个组的成本最小。

联系链接

如果您发现本系列有帮助,请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子?。您的支持对我来说意义重大!

如果您想要更多类似的有用内容,请随时关注我:

  • 领英
  • GitHub

以上是连接两组点的最低成本的详细内容。更多信息请关注PHP中文网其他相关文章!

声明:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn