분할 전략, 동태 계획, 탐욕 선택 과 재 귀 간 의 관계 와 차이 (2)
동전 거스름돈 문제: 현존 하 는 액면가 v1, v2, v3... 단위 의 동전 은 최소 몇 개의 동전 이 있어 야 총액 이 x 단위 의 잔돈 을 찾 을 수 있 습 니까?여기 서 우 리 는 v [] = {0, 1, 2, 5, 10, 20, 50} 을 가정 합 니 다.0 은 자릿수 를 채 우 는 데 쓰 인 다. 이렇게 v1, v2 와 아래 표 시 된 1, 2 가 서로 맞는다.여기 v1 은 1 이 어야 합 니 다. 1 이 아니라면 x 를 지정 하면 풀 수 없 을 수도 있 습 니 다. 즉, 찾 을 수 없습니다.예 를 들 어 v [] = {2, 5, 10, 20, 50}, x = 18, 풀 리 지 않 았 습 니 다.여기 서 우 리 는 편 의 를 위해 배열 v 를 정렬 한 것 으로 설정 합 니 다. 정렬 이 없 으 면 정렬 알고리즘 으로 해결 할 수 있 습 니 다.
1. 분 치 전략
분할 전략 알고리즘 을 설계 하기 전에 우 리 는 이 문 제 를 해결 하 는 전달 식 을 얻어 야 한다. 즉, 큰 문 제 를 어떻게 몇 개의 작은 문제 로 나 누 는 지 하 는 것 이다.
(1) 첫 번 째 방법: (이것 은 내 가 스스로 찾 아 낸 전달 식 이 니 조심 하 세 요. 하하)
f (x, i) 는 v [1], v [2],..., v [i] 로 0 x 에 필요 한 최소 동전 수 를 찾 으 려 면 다음 과 같이 전달 해 야 한다.
f(x, i)=min( f(x, i-1), x/v[i] + f(x%v[i], vmax(x%v[i], v)))
그 중에서 vmax (x, v) 는 i 로 돌아 가 고 i 는 v [i] < = x 를 만족 시 킵 니 다.
여기 서 f (x, i) 라 는 큰 문 제 를 구 할 때 우 리 는 그것 을 분해 합 니 다. (Divide)
case 1, 우 리 는 v [i] 를 건 너 뛰 고 v [1], v [2],..., v [i - 1] 로 0 x, 즉 f (x, i - 1) 를 찾 습 니 다.（Conquer）
case 2, 우 리 는 v [i] 로 0 을 찾 아야 합 니 다. 0 을 x / v [i] + f (x% v [i], vmax (x% v [i], v) (Conquer) 로 찾 아야 합 니 다.
그럼 케이스 1, 케이스 2 의 가장 작은 것 은 f (x, i) 입 니 다.
코드 는 다음 과 같 습 니 다:
/*change.h*/
int min(int a, int b)
{
if(a < b)
return a;
return b;
}
/*
x:
v:
length：
return i, v[i]<=x= v[i]) && (i < length))
{
i++;
}
return i-1;
}
/*
v：
x：
i：f(x,i) i， v[1],v[2],...,v[i]
length：
*/
int change_dc(int v[], int x, int i, int length)
{
if(x == 1)
return 1;
if(x == 0)
return 0;
if(i == 1) // i 1 ， ； f(x,i-1) ，i 0
return x;
return min(change_dc(v, x, i-1, length), x/v[i]+change_dc(v, x%v[i], vmax(x,v, length), length));
} (2) 두 번 째 방법:
따 오다http://www.ccs.neu.edu/home/jaa/CSG713.04F/Information/Handouts/dyn_prog.pdf）
전달 식 은 다음 과 같다.
c (x) = min (1 + c (x - v [i]), i 의 수치 범 위 는 i: x > = v [i] 입 니 다. 이 제한 조건 은 반드시 있어 야 합 니 다. 그렇지 않 으 면 마이너스 가 발생 합 니 다.
위 에서 제시 한 문 서 는 매우 상세 하 게 말 해 야 한다. 더 이상 말 하지 않 고 코드 를 직접 올 려 야 한다.
/*change.h*/
int change_dc2(int v[], int x, int length)
{
int i;
int min;
int temp;
if(x == 0)
return 0;
min = x;
for(i=2; i= v[i])
{
temp = change_dc2(v, x-v[i], length) + 1;
if(temp < min)
min = temp;
}
}
return min;
} 2. 동적 기획
f (1, 1), f (1, 2), c (1), c (2) 등 많은 하위 문제 가 여러 번 계산 되 는 것 을 발 견 했 을 것 이다. 그러면 우 리 는 동적 계획 으로 이런 문 제 를 해결 할 수 있다.여기 에는 두 가지 다른 방식 이 있 는데 하 나 는 위 에서 아래로 비망록 방식 (memoization) 이 고 하 나 는 아래 에서 위로 하 는 방식 이다.
(1) 위 에서 아래로 내 려 오 는 비망록 방식
우 리 는 쉽게 분할 전략 알고리즘 을 위 에서 아래로 비망록 방식 으로 바 꿀 수 있 습 니 다. 분할 전략 알고리즘 은 일반적으로 재 귀 하 는 사상 을 사용 하기 때문에 재 귀 는 위 에서 아래로 하 는 것 입 니 다. 여기 서 우 리 는 비망록 의 체 제 를 가입 하면 ok 입 니 다.바로 한 개의 문 제 를 풀 때마다 우 리 는 이 문 제 를 판단 할 때 이미 풀 었 고 이미 풀 었 다 면 직접 풀 었 다.만약 에 없 으 면 우 리 는 이 문 제 를 풀 고 이 문제 의 해 를 보존 하면 다음 에 이 문 제 를 풀 때 직접 사용 할 수 있다.
분할 정책 (1) 의 위 에서 아래로 비망록 방식:
/*change.h*/
#define MAX 20
/*
v：
x：
i：f(x, i) i， v[1],v[2],...,v[i] x
length：
c： f(x, i) ，c[x][i] f(x, i), -1，
*/
int change_dp_memoization(int v[], int x, int i, int length, int c[][MAX])
{
if(c[x][i] >= 0)
return c[x][i];
if(x == 1)
{
c[x][i] = 1;
return c[x][i];
}
if(x == 0)
{
c[x][i] = 0;
return c[x][i];
}
if(i == 1)
{
c[x][i] = x;
return c[x][i];
}
c[x][i] = (change_dp_memoization(v, x, i-1, length, c), x/v[i]+change_dp_memoization(v, x%v[i], vmax(x,v, length), length, c));
return c[x][i];
}분할 정책 (2) 의 위 에서 아래로 비망록 방식:
/*change.h*/
/*
c: c(x) ，c[i] c(i) ， -1
*/
int change_dp_memoization2(int v[], int x, int length, int c[])
{
int i;
int temp;
if(c[x] >= 0) //if c[x] has caculated
return c[x];
if(x == 0)
return 0;
c[x] = x;
for(i=1; i= v[i])
{
temp = change_dp_memoization2(v, x-v[i], length, c) + 1;
if(temp < c[x])
c[x] = temp;
}
}
return c[x];
} (2) 밑 에서 위로 올 라 가 는 방식
아래 에서 위로 향 하 는 방식 은 위 에서 아래로 향 하 는 것 과 정반 대 이다. 우 리 는 먼저 규모 가 작은 문 제 를 해결 한 다음 에 한 층 한 층 씩 나 아가 규모 가 약간 큰 문 제 를 구 할 때 사용 해 야 할 규모 가 작은 문 제 는 이미 해결 되 었 다.여기 서 우 리 는 위 에서 아래로, 아래 에서 위로 두 가지 다른 방식 을 구분 해 야 한다.위 에서 아래로 내 려 오 는 방식 으로 큰 문 제 를 풀 때 필요 한 작은 문 제 는 아직 해결 되 지 않 았 을 수도 있 고, 다른 약간 큰 문제 에 의 해 해결 되 었 을 수도 있 으 므 로, 우 리 는 이미 풀 린 문 제 를 저장 할 수 있 는 배열 이 필요 하 다.한편, 아래 에서 위로 향 하 는 방식 은 작은 문 제 를 해결 하기 전에 그 규모 보다 작은 모든 문제 가 해결 되 었 음 을 보증한다. 이렇게 큰 문 제 를 해결 할 때 그 에 포 함 된 작은 문 제 는 모두 해결 되 었 고 직접 가 져 와 서 사용한다.또 하 나 는 위 에서 아래로 일반적으로 재 귀적 으로 실현 하 는 것 이다. 큰 문 제 를 해결 할 때 어떤 작은 문 제 는 아직 해결 하지 못 하고 재 귀적 으로 계산 할 수 밖 에 없 기 때문이다. 위 에서 우 리 는 이미 보 았 다. 분 치 전략 을 가 진 알고리즘 에 비망록 체 제 를 더 하면 되 고 아래 에서 위로 일반적으로 반복 적 으로 실현 되 며 한 층 씩 위로 올 라 가 네가 원 하 는 문제 까지 할 수 있다.
분할 정책 (1) 의 아래 에서 위로 향 하 는 방식:
/*change.h*/
//int
#define INFINITY (unsigned int)(1< n)
c[m][n] = min(c[m][n-1], m/v[n] + c[m%v[n]][n]);
else
c[m][n] = min(c[m][n-1], m/v[imax] + c[m%v[imax]][n]);
}
}
return c[x][i];
}정책 (2) 의 아래 에서 위로 나 누 는 방식:
/*change.h*/
int change_dp_bottomup2(int v[], int x, int length, int c[])
{
int i, j;
int temp;
for(i=1; i<=x; i++)
{
c[i] = i;
for(j=2; j= v[j])
{
temp = c[i-v[j]] + 1;
if(c[i] > temp)
c[i] = temp;
}
}
}
return c[x];
} 3. 욕심 선택
여기 서 우리 가 제시 한 거스름돈 배열 v [] 는 욕심 을 만족 시 키 는 선택 성격 이 므 로 여기 서 증명 하지 않 는 다.사실 2v [i] < = v [i + 1] 만 있 으 면 욕심 선택의 성격 을 만족시킨다.2v [i] < = v [i + 1] 을 만족 시 키 지 않 으 면 제로 문 제 를 욕심 산법 으로 해결 할 수 없다.예 를 들 어 v [] = {0, 1, 2, 5, 8, 10, 20, 50}, x = 16 은 2, 즉 8 액면가 의 동전 두 개 로 0 을 찾 아야 하고 욕심 산법 의 해 는 10, 5, 1 이다.다음은 욕심 산법 의 코드 를 드 립 니 다.
/*change.h*/
int change_greedy(int v[], int x, int length)
{
int count = 0;
int i;
while(x > 0)
{
i = vmax(x, v, length);
count += x/v[i];
x = x%v[i];
}
return count;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JZOJ.3432 [GDOI 2014 시뮬레이션] 서버 문제 해결 보고서이 서버의 번호는 1, 2,..., n이다.우선, 우리는 일부 서버를 선택하여 파일을 그것들에 직접 복사할 수 있다.서버 i에 파일을 복사하려면 ci가 필요합니다.직접 복제를 통해 파일을 얻지 못한 서버에 대해 i+...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
