욕심 많은 알고리즘의 기본 아이디어
1. 문제를 설명하기 위해 수학적 모델을 설정하십시오.
2. 해결 된 문제를 여러 하위 문제로 나눕니다.
3. 각 하위 문제를 해결하고 하위 문제에 대한 로컬 최적 솔루션을 얻으십시오.
4. 서브 프로 블렘의 로컬 최적 솔루션을 문제의 원래 솔루션에 대한 솔루션으로 합성하십시오.
이 알고리즘을 구현하는 과정 :
특정 초기 솔루션에서 문제에 이르기까지;
주어진 전체 목표로 나아갈 수 있습니다
실행 가능한 솔루션의 솔루션 요소를 찾으십시오.
문제에 대한 실행 가능한 솔루션은 모든 솔루션 요소로 구성됩니다.
욕심 많은 선택적 특성
소위 욕심 많은 선택 특성은 당신이 찾고있는 문제의 전반적인 최적 솔루션이 일련의 지역 최적 선택을 통해 달성 될 수 있음을 의미합니다. 그것을 고려하지 않고 현재의 문제. 이것은 욕심 많은 알고리즘의 타당성의 첫 번째 기본 요소입니다.
욕심 많은 알고리즘은 반복적으로 탐욕스러운 선택을하고, 탐욕스러운 선택이 이루어질 때마다, 당신이 찾고있는 문제는 더 작은 하위 프로젝트로 줄어 듭니다.
특정 문제의 경우, 탐욕스러운 선택 특성이 있는지 여부를 결정하기 위해서는 각 단계에서 욕심 많은 선택이 궁극적으로 문제에 대한 전반적인 최적 솔루션으로 이어짐을 증명해야합니다.
2. 최적의 하위 구조 특성 <br /> 문제의 최적 솔루션에 하위 문제의 최적 솔루션이 포함되어있을 때,이 문제는 최적의 하위 구조적 특성을 갖는다 고합니다. 문제의 최적의 하위 구조 특성은 욕심 많은 알고리즘으로 해결할 수있는 주요 기능입니다.
탐욕의 일반적인 과정
코드 사본은 다음과 같습니다.
Greedy (c) // c는 문제의 입력 세트, 즉 후보 세트입니다.
{
s = {}; // 초기 솔루션 세트는 빈 세트입니다
whit white (Solution (s)) // 세트는 문제에 대한 해결책을 구성하지 않습니다.
{
x = select (c);
실행 가능한 경우 (S, X) // 세트 S에 X를 추가 한 후 솔루션이 실행 가능한지 판단합니다.
s = s+{x};
c = c- {x};
}
반환 s;
문제 설명 :
현재 2 Jiao 5 센트, 1 Jiao 5 센트, 5 센트 및 1 센트의 동전이 있습니다.
문제 분석 :
Common Sense에 따르면, 우리가 물건을 사고 돈을 찾기 위해 가게에 갈 때, 보스는 항상 충분하지 않다면 더 작은 교파를 찾으십시오. 보스가 당신에게 점수 나 몇 센트를 요구한다면, 당신은 확실히 그렇게하지 않을 것입니다. 실제로 이것은 탐욕스러운 선택의 전형적인 문제입니다.
문제의 알고리즘 설계 및 구현 :
먼저 보스가 나에게 99 센트를 요청하고 싶다면, 그는 25, 10, 5 및 1의 액면가를 가진 위의 동전을 가지고있다. 그는 이렇게 찾아야한다 'T Do IT, 보스는 나에게 3 25 점을 얻었고 24 점을 줄 수 있었기 때문에 2 10 점, 4 1 점을 주어야했습니다.
코드 사본은 다음과 같습니다.
// 변경 사항을 찾기위한 산술
// 입력 : 배열 m, 큰면에서 작은 것에서 정렬 된 수의 수는 찾을 수있는 돈의 수입니다.
// 출력 : 배열 번호, 배열 M에서 다른 명칭 값을 가진 코인 수를 비교하고 돈 계획을 찾으십시오.
public static int [] zhaoqian (int m [], int n)
{
int k = m.length;
int [] num = new int [k];
for (int i = 0; i <k; i ++)
{
num <i> = n/mi;
n = n%mi;
}
Num 리턴;
}
코드 사본은 다음과 같습니다.
공개 클래스 자오키안
{
public static void main (String [] args)
{
int m [] = {25,10,5,1};
int n = 99;
int [] num = new int [m.length];
num = zhaoqian (m, n);
System.out.println (N+"돈 찾기 계획 :");
for (int i = 0; i <m.length; i ++)
System.out.println (num <i>+"zip"+m <i>+"액면가");
}
public static int [] zhaoqian (int m [], int n)
{
int k = m.length;
int [] num = new int [k];
for (int i = 0; i <k; i ++)
{
num <i> = n/mi;
n = n%mi;
}
Num 리턴;
}
}
위는이 기사의 모든 내용입니다. 좋아할 수 있기를 바랍니다.