Python을 사용하여 그리디 알고리즘을 구현하는 방법

그리디 알고리즘의 원리는 문제를 해결하는 순간 항상 최선의 선택을 하는 것이라는 것을 우리는 알고 있습니다. 즉, 그가 만든 것은 전체 최적해를 고려하지 않은 채 어떤 의미에서는 국소적 최적해에 불과했다. 그리디 알고리즘은 모든 문제에 대해 전체 최적해를 얻을 수는 없지만 광범위한 문제에 대해 전체 최적해 또는 전체 최적해에 대한 대략적인 해를 생성할 수 있습니다.

특징: 탐욕 알고리즘은 하향식 접근 방식을 채택하고 반복적인 방법을 사용하여 탐욕스러운 선택을 할 때마다 원하는 문제를 각 탐욕 단계를 통해 더 작은 하위 문제로 단순화합니다. 문제에 대한 최적의 솔루션을 얻으려면 각 단계에서 로컬 최적 솔루션을 얻을 수 있어야 하지만, 결과로 얻은 전역 솔루션이 항상 최적이 아닐 수도 있으므로 그리디 방법으로 역추적하지 마세요. 그리디 알고리즘으로 해결할 수 있는 문제에는 일반적으로 탐욕 선택 속성과 최적 하위 구조 속성이라는 두 가지 중요한 속성이 있습니다.

질문 예: 일련의 활동이 주어지면 각 활동의 시작 시간과 종료 시간을 알려주고, 참여할 수 있는 최대 활동 수 또는 활동의 시작 및 종료 시간을 계산해 달라고 요청하세요

Greedy 알고리즘 아이디어:

두 개의 배열을 사용하여 활동의 시작 및 종료 시간을 각각 저장합니다. 활동의 종료 시간을 기준으로 감소하지 않는 일련의 활동이 수행됩니다. 여기에 따라 블로거는 bubble sorting동기 교환을 사용합니다. 예: Activity (1, 4) (2, 3) (3, 5) 그런 다음 시작 시간을 비교하여

s = [2,1,3]
f = [3,4,5]

을 얻습니다. 다음 활동과 이전 활동의 종료 시간이 결정됩니다. 이 두 활동은 호환됩니까? 시작 시간이 종료 시간보다 크면 호환되지 않습니다. 코드는 다음과 같습니다. #버블 정렬 사용 종료 시간을 정렬하고 해당 시작 시간 목록을 얻으려면

def bubble_sort(s,f):
  for i in range(len(f)):
    for j in range(0,len(f)-i-1):
      if f[j] > f[j+1]:
        f[j], f[j+1] = f[j+1],f[j]
        s[j],s[j+1] = s[j+1],s[j]
  return s,f
 
def greedy(s,f,n):
  a = [True for x in range(n)]
  #初始选择第一个活动
  j = 0
  for i in range(1,n):
    #如果下一个活动的开始时间大于等于上个活动的结束时间
    if s[i] >= f[j]:
      a[i] = True
      j = i
    else:
      a[i] = False
  return a
 
n = int(input())
arr = input().split()
s = []
f = []
for ar in arr:
  ar = ar[1:-1]
  start = int(ar.split(',')[0])
  end = int(ar.split(',')[1])
  s.append(start)
  f.append(end)
 
s,f = bubble_sort(s,f)
A = greedy(s,f,n)
 
res = []
for k in range(len(A)):
  if A[k]:
    res.append('({},{})'.format(s[k],f[k]))
print(' '.join(res))

이 사례를 읽으신 후 방법을 마스터하셨다고 생각합니다. 더 흥미로운 정보를 보려면 PHP 중국어 웹사이트의 다른 관련 기사에 주목하세요!

관련 읽기:

PHP가 스택 데이터 구조 및 대괄호 일치 알고리즘을 구현하는 방법에 대한 자세한 코드 예제

PHP에서 가장 간단한 문자열 일치 알고리즘, PHP 일치 알고리즘_PHP 튜토리얼

가장 간단한 문자열 일치 알고리즘 튜토리얼 PHP에서

위 내용은 Python을 사용하여 그리디 알고리즘을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!