두 포인트 그룹을 연결하는 데 필요한 최소 비용

王林
풀어 주다: 2024-09-01 06:34:06
원래의
1055명이 탐색했습니다.

1595. 두 포인트 그룹을 연결하는 데 필요한 최소 비용

난이도:어려움

주제: 배열, 동적 프로그래밍, 비트 조작, 매트릭스, 비트마스크

첫 번째 그룹은 크기1점, 두 번째 그룹은 크기2점, 크기1 > = 크기2.

두 점 사이의 연결 비용은 크기1 x 크기2 행렬로 제공됩니다. 여기서 비용[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 == 비용.길이
  • 크기2 == 비용[i].길이
  • 1 <= 사이즈1, 사이즈2 <= 12
  • 크기1 >= 크기2
  • 0 <= 비용[i][j] <= 100

힌트:

  1. 왼쪽의 각 점은 이미 왼쪽 노드에 연결된 정확한 점에 연결되거나 어떤 노드에도 연결되지 않은 오른쪽 노드의 하위 집합에 연결됩니다.
  2. 비트마스킹과 함께 동적 프로그래밍을 사용합니다. 여기서 상태는 (첫 번째 그룹에 할당된 포인트 수, 두 번째 그룹에 할당된 포인트의 비트마스크)입니다.

해결책:

비트마스킹을 통해 동적 프로그래밍을 활용할 수 있습니다. 첫 번째 그룹의 각 포인트를 고려하고 이를 두 번째 그룹의 모든 포인트에 연결하려고 노력하여 비용을 최소화한다는 아이디어입니다.

비트마스킹을 사용한 DP(동적 프로그래밍) 접근 방식

단계:

  1. 주 대표:

    • 다음과 같은 경우 DP 테이블 dp[i][mask]를 사용합니다.
      • i는 첫 번째 그룹(0부터 size1-1까지)의 인덱스입니다.
      • 마스크는 두 번째 그룹의 어느 지점이 연결되었는지 나타내는 비트마스크입니다.
  2. 상태 전환:

    • 첫 번째 그룹의 각 점에 대해 두 번째 그룹의 모든 점에 연결하고 이에 따라 DP 테이블을 업데이트해 보세요.
    • 두 번째 그룹의 새 포인트가 연결되면 마스크에서 해당 비트를 업데이트합니다.
  3. 기본 사례:

    • dp[0][0] = 0으로 시작합니다(처음에는 연결 없음).
  4. 목표:

    • 두 그룹의 모든 점 연결을 나타내는 dp[size1][(1 << size2) - 1]의 최소 비용을 계산합니다.

이 솔루션을 PHP: 1595로 구현해 보겠습니다. 두 포인트 그룹을 연결하는 데 필요한 최소 비용






설명:

  • DP 배열 dp[i][mask]는 그룹 1의 첫 번째 i 지점을 마스크로 표시된 그룹 2의 지점과 연결하는 최소 비용을 저장합니다.
  • 중첩 루프는 i와 마스크의 각 조합을 반복하여 가능한 모든 연결을 고려하여 최적의 비용을 찾으려고 노력합니다.
  • 결국 솔루션은 두 번째 그룹의 일부 포인트가 아직 연결되지 않은 시나리오를 고려하여 최소 비용을 계산하여 모든 포인트가 연결되도록 합니다.

이러한 접근 방식은 문제의 제약을 효율적으로 처리하고 두 그룹을 연결하는 데 드는 비용을 최소화합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

  • 링크드인
  • 깃허브

위 내용은 두 포인트 그룹을 연결하는 데 필요한 최소 비용의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

원천:dev.to
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿