连接两组点的最低成本-php教程-PHP中文网

连接两组点的最低成本

王林

发布： 2024-09-01 06:34:06

原创

1054 人浏览过

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

难度：难

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

您将获得两组点，其中第一组大小为 ₁ 点，第二组大小为 ₂ 点，大小为 ₁ > 点。 = 大小₂.

任意两点之间的连接成本以大小 ₁ x size₂ 矩阵给出，其中 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

约束：

大小₁ == cost.length
大小₂ == 成本[i].长度
1 1，尺寸₂
尺寸₁>=尺寸₂
0

提示：

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

解决方案：

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

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

步骤：

国家代表：
- 使用 DP 表 dp[i][mask]，其中：
  - i 是第一组中的索引（范围从 0 到 size1-1）。
  - mask 是一个位掩码，表示第二组中的哪些点已连接。
状态转换:
- 对于第一组中的每个点，尝试将其连接到第二组中的每个点，相应地更新 DP 表。
- 如果连接了第二组中的新点，则更新掩码中的相应位。
基本案例：
- 从 dp[0][0] = 0 开始（最初没有连接）。
目标：
- 计算 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
?>

登录后复制