How to implement greedy algorithm using Python

We know that the principle of the greedy algorithm is to always make the best choice at the moment when solving the problem. In other words, without considering the overall optimal solution, what he made was only a local optimal solution in a certain sense. The greedy algorithm cannot obtain the overall optimal solution for all problems, but it can produce the overall optimal solution or an approximate solution to the overall optimal solution for a wide range of problems.

Features: The greedy algorithm uses top-down and iterative methods to make successive greedy choices. Each time a greedy choice is made, the desired problem is simplified into a smaller sub-problem. Through each step Greedy selection can obtain an optimal solution to the problem. Although each step must ensure that a local optimal solution can be obtained, the resulting global solution may not necessarily be optimal, so do not backtrack with the greedy method. Problems that can be solved by greedy algorithms generally have two important properties: greedy selection properties and optimal substructure properties.

For example: Given a set of activities, tell the start time and end time of each activity, and ask to calculate the maximum number of activities that can be participated in or the start and end time of the activity

Greedy algorithm idea:

Use two arrays s and f to store the start and end times of the activities respectively. A non-decreasing activity sequence is performed on the activities based on the end time of the activities. The same activity start time list is also done. Corresponding adjustment, bloggers here are exchanged synchronously through bubble sorting, for example: activities (1, 4) (2, 3) (3, 5) then we get

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

By comparing the start time of the next activity with the end time of the previous activity, determine whether the two activities are compatible. If the start time is greater than the end time, they are compatible. , on the contrary, it is incompatible. The code is as follows #Use bubble sort to sort the end time and get the corresponding start time list

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))

I believe you have mastered the method after reading these cases. Please pay attention for more exciting things. Other related articles on php Chinese website!

Related reading:

Detailed code examples of how to implement stack data structure and bracket matching algorithm in php

The most popular in php Simple string matching algorithm, php matching algorithm_PHP tutorial

The simplest string matching algorithm tutorial in php

The above is the detailed content of How to implement greedy algorithm using Python. For more information, please follow other related articles on the PHP Chinese website!