Algorithmic Toolbox_Greedy Algorithm

一、What is Greedy Algorithm

Greedy algorithm means that when solving a problem we always make the best choice in the current view. However, greedy algorithm does not get the overall optimal solution to all problems, the key is the choice of greedy strategy. That is to say, without considering the overall optimality, what is made is only a local optimal solution in a certain sense.

二、Step of Greedy Algorithm

Construct a judge function to make sure that each move is safe.Construct a function to check if the candidate object is an answer of the question.As the algorithm progresses, two other sets will be accumulated: one contains candidates that have been considered and selected, and the other contains candidates that have been considered but discarded .Just analyze these sets, then return the correct answer.

三、Seven Typical Answer to Help us Understanding

This is my code.

inp=int(input()) denomination=[1,5,10] def plan(m): oup_1=m//denomination[2] m=m-oup_1*denomination[2] oup_2=m//denomination[1] oup_3=m-oup_2*denomination[1] return oup_1+oup_2+oup_3 print(plan(inp))

import sys data = list(map(lambda x:int(x), sys.stdin.read().split())) n,capacity=data[0:2] values,weights = data[2:len(data)-1:2],data[3:len(data):2] def most_cost(n,capacity,values,weights): ecv=[[values[i]/weights[i],weights[i]] for i in range(len(values))] ecv_cur=sorted(ecv,reverse=True) sum_w=sum([ecv_cur[i][1] for i in range(len(ecv))]) if sum_w<=capacity: return sum([ecv_cur[i][0]*ecv_cur[i][1] for i in range(len(ecv))]) else: sum_c,sum_w,i=0,0,0 while True: if capacity<=sum_w: break else: sum_w += ecv_cur[i][1] i+=1 continue sum_c=sum([ecv_cur[k][0]*ecv_cur[k][1] for k in range(i-1)])+ecv_cur[i-1][0]*(capacity+ecv_cur[i-1][1]-sum_w) return sum_c print(round(most_cost(n,capacity,values,weights),4))

import sys data = list(map(lambda x:int(x), sys.stdin.read().split())) d,m,n,sta=data[0],data[1],data[2],data[3:] sta_de=[sta[i+1]-sta[i] for i in range(n-1)] sta_de.append(d-sta[len(sta)-1]) def st_times(d,m,n,sta): if m>d: return 0 else: if m<max(sta_de): return -1 else: st_t,a=0,0 sta.append(d) for k in range(n+1): if m<sta[k]-a: st_t+=1 a=sta[k-1] if d-a<m: break return st_t print(st_times(d,m,n,sta))

import sys data = list(map(lambda x:int(x), sys.stdin.read().split())) tol=data[0] id_click=data[1:int((len(data)+1)/2)] id_profit=data[int((len(data)+1)/2):] def income(tol,id_click,id_profit): id_c_sort=sorted(id_click,reverse=True) id_p_sort=sorted(id_profit,reverse=True) income_lst=sorted([id_c_sort[i]*id_p_sort[i] for i in range(len(id_c_sort))],reverse=True) return sum([income_lst[i] for i in range(tol)]) print(income(tol,id_click,id_profit))

import sys data = list(map(lambda x:int(x), sys.stdin.read().split())) n,lst_org=data[0],[[data[i],data[i+1]] for i in range(1,len(data),2)] def mini_set(n,lst_org): answer,mid1,mid2,res=[],0,0,[] lst_deal2=sorted(lst_org,reverse=False,key=lambda i:i[1]) # print(lst_deal2) i,j=0,0 a,answer,b=lst_deal2[0][1],[],0 while j<len(lst_deal2): if j==len(lst_deal2)-1: answer.append(lst_deal2[i][1]) if lst_deal2[i][1]<lst_deal2[j][0]: answer.append(lst_deal2[i][1]) i=j if j==len(lst_deal2)-1: answer.append(lst_deal2[i][1]) j+=1 else: j+=1 return answer ans=mini_set(n,lst_org) ans=list(set(ans)) print(len(ans)) print(ans[0],end="") for i in range(1,len(ans)): print(" "+str(ans[i]),end="")

import sys import math data = int(list(map(lambda x:int(x), sys.stdin.read().split()))[0]) def decline(data1): ans,i=[],0 while True: data1=data1-i i+=1 if i<data1/2: ans.append(i) else: ans.append(data1) break return ans ans=decline(data) print(len(ans)) print(ans[0],end="") for i in range(1,len(ans)): print(" "+str(ans[i]),end="")

import sys import copy data = list(map(lambda x:str(x), sys.stdin.read().split())) n,num_lst=int(data[0]),data[1:] def my_salary(n,num_lst): num_lst_deal=sorted(num_lst,reverse=True,key=lambda x:int(x[0])) for i in range(len(num_lst_deal)-1): for j in range(len(num_lst_deal)-i-1): if int(str(num_lst_deal[j+1])+str(num_lst_deal[j]))>int(str(num_lst_deal[j])+str(num_lst_deal[j+1])): u=num_lst_deal[j] num_lst_deal[j]=num_lst_deal[j+1] num_lst_deal[j+1]=u return num_lst_deal o=my_salary(n,num_lst) result="" for i in range(len(o)): result+=o[i] print(result)

To sum up , the fundamental thing in greedy algorithm is that confirming the standard of comparing two different object, then following the help of this function we can find a set of objects which is correct. Then analyze the requirement of the project, give out the correct answer.