[동적 기획] [쌍 조 TSP 와 MTSP 문제] hdu 2224 & hdu 4281
1429 단어 동적 계획
우선 2 조 TSP: hdu 2224
평면 에 있 는 N 개 점 (1 ~ N) 을 주 고 1 번 점 에서 출발 하여 가장 오른쪽 끝 에 있 는 점 N 으로 가서 1 을 되 돌려 줍 니 다. 중간 에 어떤 점 을 반복 해 서 는 안 되 고 모든 점 을 한 번 씩 다 가 야 합 니 다. 가장 작은 총 경 로 를 구 해 야 합 니 다.
이 물건 은 NPC 계산 가이드 에 O (N ^ 2) 를 소개 하 는 알고리즘 이 있 는 것 이 아니다.
dp [i] [j] 는 1 에서 i 까지 및 1 에서 j 까지 의 최소 총 경 로 를 표시 합 니 다 (i < j).
이동: ① i < j - 1 시 dp [i] [j] = dp [i] [j - 1] + dis [j - 1] [j] 는 i < j - 1, dp [i] [j] 가 dp [i] [j] 에서 만 유래 할 수 있 음 이 분명 하 다.② i = j - 1 시 dp [j - 1] [j] 는 dp [k] [j - 1] + dis [k] [j] (k < j - 1) 에서 유래 할 수 있다.
void solve()
{
dp[1][2] = dis[1][2];
for(int j = 3; j <= N; j++)
{
for(int i = 1; i < j - 1; i++)
{
dp[i][j] = dp[i][j-1] + dis[j - 1][j];
}
dp[j - 1][j] = inf;
for(int i = 1;i < j - 1; i++)
{
dp[j - 1][j] = min(dp[j - 1][j],dp[i][j - 1] + dis[i][j]);
}
}
dp[N][N] = dp[N - 1][N] + dis[N - 1][N];
}MTSP：hdu4281
위 에 문제 랑 많이 다 르 지 는 않 지만 이번 에는 한 번 가 는 게 아니 라 여러 번 가 는 거 야.
그러면 이것 은 매번 의 TSP 를 완성 한 다음 에 모든 상태 에 대한 부분 집합 을 매 거 한 다음 에 현재 상태의 최소 비용 을 찾 는 것 입 니 다.
for(int i = 0; i < (1 << N); i++)
{
if(i & 1)
{
for(j = i & (i - 1); j; j = i & (j - 1))
res[i] = min(res[i], res[j | 1] + res[(i - j) | 1]);
}
}
return back[(1 << n) - 1];이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
124. 두 갈래 나무의 최대 경로와 leetcode비공 두 갈래 트리를 지정하고 최대 경로와 를 되돌려줍니다. 본고에서 경로는 나무의 임의의 노드에서 출발하여 임의의 노드에 도달하는 서열로 정의되었다.이 경로는 루트 노드를 거치지 않고 하나 이상의 노드를 포함합니다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
