C++ 그리디 알고리즘(장소 배치, 간격 선택) 예

알고리즘 강좌를 듣고 처음으로 녹음을 해보니 프로그램 설계에서 고려해야 할 요소가 점점 많아졌습니다. 프로그램 = 데이터 구조 + 알고리즘을 통해 깊이 이해하게 되었습니다. 간단한 C++ 프로그래밍부터 적절한 데이터 구조 선택까지, 이제 한 단계 더 나아가 알고리즘 수준에서 프로그램 실행의 효율성을 고려해야 합니다. 알고리즘에 대한 나의 이해는 더 적은 오버헤드로 더 나은 실행 결과를 얻는 것입니다.

그리디 알고리즘을 배울 때 분할 정복 방법과 동적 프로그래밍은 이전에 기록되지 않았습니다. 더 잘 이해할 수 있도록 배운 내용을 요약해야 한다고 느꼈습니다. 동적 프로그래밍의 설계는 최적의 하위 구조 속성과 중첩되는 하위 문제를 충족해야 하며, 상향식 전략을 채택하여 최적의 값을 계산하고 전체 최적 솔루션을 찾아야 합니다. 이 과정은 때때로 매우 어렵습니다. 가장 중요한 것은 재귀 표현식을 작성하고 테이블을 아래에서 위로 채우는 것입니다. 그리디 전략은 동적 프로그래밍과 약간 비슷하지만 어떤 면에서는 다릅니다. 그리디 알고리즘이라는 개념이 더 쉽게 생각될 때도 있습니다. 하위 문제 최적성을 만족하고 전체 최적성을 획득해야 합니까? 두 가지 조건: 최적의 하부 구조 속성과 탐욕스러운 선택 속성. 탐욕적 선택 속성을 만족하려면 최적의 하위 구조 속성을 만족해야 하지만, 최적의 하위 구조 속성을 만족한다고 해서 반드시 탐욕적 선택 속성을 만족하는 것은 아닙니다. 예를 들어 배낭 문제는 탐욕 알고리즘으로 풀 수 있지만 0-1 배낭 문제는 다이나믹 프로그래밍으로 풀어보세요.

전형적인 탐욕스러운 문제 활동 배열은 n개의 활동이 있고 시작 시간과 종료 시간이 주어지며 가능한 한 많은 활동을 배열해야 합니다(시간이 서로 충돌하지 않음). 이 문제를 해결하기 위한 올바른 그리디 아이디어는 각 활동의 종료 시간을 비교 변수로 삼아 종료 시간의 오름차순으로 활동을 정렬한 후 비교 및 ​​선택을 수행하는 것입니다. 장소 배치 문제와 활동에는 약간의 차이가 있습니다. 다음은 저의 문제 해결 과정입니다.

7-2 장소 배치 문제(20점)

충분한 장소에서 일련의 활동을 준비하고 가능한 한 적은 수의 장소를 사용하기를 원한다고 가정해 보겠습니다. 스케줄링을 위한 효율적인 탐욕 알고리즘을 설계합니다. (이 문제는 사실 유명한 그래프 색칠 문제이다. 각 활동을 그래프의 꼭지점으로 간주하면 호환되지 않는 활동은 모서리로 연결된다. 인접한 꼭지점을 서로 다른 색상으로 만드는 최소 색칠 횟수가 발견되는 것에 해당한다. )

입력 형식:

첫 번째 줄에는 1개의 양의 정수 k가 포함되어 있으며, 이는 준비할 이벤트가 k개 있음을 나타냅니다. 다음 k 줄의 각 줄에는 각각 예약될 k 활동의 시작 시간과 종료 시간을 나타내는 2개의 양의 정수가 있습니다. 시간은 0시부터 분 단위로 측정됩니다.

출력 형식:

최소 장소 수를 출력합니다.

입력 샘플:

5
1 23
12 28
25 35
27 80
36 50

출력 샘플:

3

#include<iostream>
#include<algorithm>
using namespace std;
struct node {
    int begin;
    int end;
    int flag;//标记该活动是否被安排，0表示未安排，1表示已安排 
}t[10001];
int cmp(const node &a,const node &b)//比较规则：以结束时间升序排列 
{ 
    return a.end<b.end;
 } 
int main()
{
    int i,j,n;
    node temp;
    cin>>n;
    for(i=0;i<n;i++) 
    {
        cin>>t[i].begin>>t[i].end;
        t[i].flag=0;
    }
    sort(t,t+n,cmp);
        
    int sum=0;//总共需要的会场数量 
    for(i=0;i<n;i++)//方法2 
    {
        if(!t[i].flag)//找到未安排的活动，进行场地安排 
        {
            sum++;
            int p=i;
            for(j=p+1;j<n;j++)//当前活动结束时间与下一个活动开始不相交 ，则安排到同一个会场 
            {
                if(t[p].end<=t[j].begin&&!t[j].flag)
                {
                    p=j;t[j].flag=1;
                }
            }
            t[i].flag=1;
        }
    }
    cout<<sum;
    return 0;
}

탐욕스러운 전략은: 한 장소에서 충돌하지 않는 활동을 최대한 많이 배열하는 것입니다. 활동 시간이 겹치는 경우 다른 장소에 배열합니다.

모든 활동을 종료 시간을 기준으로 오름차순으로 정렬하고 정렬 기능을 사용하고 cmp 방법을 사용자 정의하세요. 루프 본문에서는 예정되지 않은 활동을 매번 찾을 수 있으며, 이 활동을 사용하여 동시에 장소에서 수용할 수 있는 다른 활동을 검색할 수 있습니다(이 단계는 두 레이어의 루프 뒤에 중첩됩니다). , 모든 활동이 준비되었습니다. 이제 필요한 장소 수 합계가 계산되었습니다.

비슷한 문제는 간격 점 선택입니다

7-10 점 선택 문제(15점)

수축에 n개의 닫힌 간격[ai, bi]이 있습니다. 각 간격에 최소한 하나의 점이 있도록 가능한 한 적은 수의 점을 선택하십시오(다른 간격의 점은 동일할 수 있음).

입력 형식:

첫 번째 줄의 숫자 n은 n개의 닫힌 구간이 있음을 나타냅니다. 다음 n 줄은 각 줄에 2개의 숫자가 포함되어 있으며 닫힌 간격을 나타냅니다. [ai, bi]

출력 형식:

적어도 필요한 포인트 수를 나타내는 정수

입력 샘플:

Give 여기에 입력 세트를 출력합니다. 예:

3
1 3
2 4
5 6

출력 샘플:

해당 출력은 여기에 제공됩니다. 예: 2

여러 간격의 공통 세그먼트를 찾고 각 공통 세그먼트에 어떤 간격이 포함되어 있는지 기록하여 최소 선택 포인트를 계산하고 싶습니다. 나중에 나는 이 아이디어가 실제로 단순화될 수 있다는 것을 발견했습니다. 전략은 오른쪽 끝을 배플로 사용하여 앞에 다른 간격이 있는지 확인하는 것입니다. 그렇지 않으면 공통점이 없음을 의미합니다. 계속하려면 배플 위치를 계산하고 이동해야 합니다. 그리디 전략은 간격의 올바른 끝점을 선택하여 더 큰 교차 세그먼트를 포함하고 가장 적은 수의 점을 선택할 수 있도록 하는 것입니다.

#include<bits/stdc++.h>
using namespace std;
struct dot{
    int l,r;
    bool v[10001];
}dots[10001];
int cmp(const dot &a,const dot &b)//比较规则，按区间右端点升序排列 
{
    return a.r<b.r;
} 
int main()
{
    int n,i,j,count=1,select;
    cin>>n;
    for(i=0;i<n;i++)
        cin>>dots[i].l>>dots[i].r;
    sort(dots,dots+n,cmp);//预处理，将区间按规则排好序，方便后续比较 
    select=dots[0].r;
    //贪心策略是选择区间右端点，保证能够包含更大交叉段，选的点最少 
    for(i=1;i<n;i++)//每次将当前选择的一个区间的右端点与下一个（或者同一区间，可忽略）左端比较 
    {
        if(dots[i].l>select)//如果没有交叉，选点+1,并以此区间右端为新一轮比较的点 
        {
            count++;
            select=dots[i].r;
        }
    }
    cout<<count;
    return 0;
}

알고리즘을 배우고 나서 문제를 해결하려면 프로그래밍에 앞서 알고리즘을 선택하는 것이 매우 중요하다는 것을 깨달았습니다. 또한 일반적인 알고리즘에 대한 연구와 연구는 정말 광범위하고 심오합니다. !

이 기사는 C#.Net Tutorial 칼럼에서 가져온 것입니다. 배우기를 환영합니다!

위 내용은 C++ 그리디 알고리즘(장소 배치, 간격 선택) 예의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!