Greedy es un paradigma algorítmico que construye una solución pieza por pieza, eligiendo siempre la siguiente pieza que ofrece el beneficio más obvio e inmediato. Los algoritmos codiciosos se utilizan para problemas de optimización. Un problema de optimización se puede resolver usando Greedy si el problema tiene la siguiente propiedad: en cada paso, podemos elegir la opción que se ve mejor en ese momento y obtenemos la solución óptima del problema completo .
Si un Algoritmo Greedy puede resolver un problema, generalmente se convierte en el mejor método para resolver ese problema ya que los algoritmos Greedy son en general más eficientes que otras técnicas como la Programación Dinámica. Pero los algoritmos Greedy no siempre se pueden aplicar. Por ejemplo, el problema de la mochila fraccional se puede resolver usando Greedy, pero0-1 Mochila no se puede resolver usando Greedy.
Los siguientes son algunos algoritmos estándar que son algoritmos codiciosos.
1) Árbol de expansión mínimo (MST) de Kruskal : en el algoritmo de Kruskal, creamos un MST seleccionando los bordes uno por uno. The Greedy Choice es elegir el borde de peso más pequeño que no provoque un ciclo en el MST construido hasta ahora.
2) Árbol de expansión mínimo de Prim : también en el algoritmo de Prim, creamos un MST seleccionando los bordes uno por uno. Mantenemos dos conjuntos: un conjunto de los vértices ya incluidos en MST y el conjunto de los vértices aún no incluidos. The Greedy Choice es elegir el borde de peso más pequeño que conecta los dos conjuntos.
3) El camino más corto de Dijkstra :El algoritmo de Dijkstra es muy similar al algoritmo de Prim. El árbol del camino más corto se construye, borde por borde. Mantenemos dos conjuntos: un conjunto de los vértices ya incluidos en el árbol y el conjunto de los vértices aún no incluidos. The Greedy Choice es elegir el borde que conecta los dos conjuntos y está en la ruta de peso más pequeña desde la fuente hasta el conjunto que contiene vértices aún no incluidos.
4) Codificación Huffman : La codificación Huffman es una técnica de compresión sin pérdidas. Asigna códigos de bits de longitud variable a diferentes caracteres. The Greedy Choice es asignar el código de menor longitud de bit al carácter más frecuente.
Los algoritmos codiciosos a veces también se usan para obtener una aproximación para problemas de optimización difíciles. Por ejemplo, Problema del viajante de comercioes un problema NP-Difícil. Una opción Greedy para este problema es elegir la ciudad no visitada más cercana de la ciudad actual en cada paso. Estas soluciones no siempre producen la mejor solución óptima, pero pueden usarse para obtener una solución aproximadamente óptima.
Consideremos el problema de selección de actividad como nuestro primer ejemplo de algoritmos codiciosos. A continuación se presenta el enunciado del problema.
Se le dan n actividades con sus horas de inicio y finalización. Seleccione el número máximo de actividades que puede realizar una sola persona, suponiendo que una persona solo puede trabajar en una sola actividad a la vez.
Ejemplo:
C++
// C++ program for activity selection problem.
// The following implementation assumes that the activities
// are already sorted according to their finish time
#include <bits/stdc++.h>
using namespace std;
// Prints a maximum set of activities that can be done by a single
// person, one at a time.
// n --> Total number of activities
// s[] --> An array that contains start time of all activities
// f[] --> An array that contains finish time of all activities
void printMaxActivities(int s[], int f[], int n)
{
int i, j;
cout <<"Following activities are selected "<< endl;
// The first activity always gets selected
i = 0;
cout <<" "<< i;
// Consider rest of the activities
for (j = 1; j < n; j++)
{
// If this activity has start time greater than or
// equal to the finish time of previously selected
// activity, then select it
if (s[j] >= f[i])
{
cout <<" " << j;
i = j;
}
}
}
// driver program to test above function
int main()
{
int s[] = {1, 3, 0, 5, 8, 5};
int f[] = {2, 4, 6, 7, 9, 9};
int n = sizeof(s)/sizeof(s[0]);
printMaxActivities(s, f, n);
return 0;
}
//this code contributed by shivanisinghss2110
C
// C program for activity selection problem.
// The following implementation assumes that the activities
// are already sorted according to their finish time
#include<stdio.h>
// Prints a maximum set of activities that can be done by a single
// person, one at a time.
// n --> Total number of activities
// s[] --> An array that contains start time of all activities
// f[] --> An array that contains finish time of all activities
void printMaxActivities(int s[], int f[], int n)
{
int i, j;
printf ("Following activities are selected n");
// The first activity always gets selected
i = 0;
printf("%d ", i);
// Consider rest of the activities
for (j = 1; j < n; j++)
{
// If this activity has start time greater than or
// equal to the finish time of previously selected
// activity, then select it
if (s[j] >= f[i])
{
printf ("%d ", j);
i = j;
}
}
}
// driver program to test above function
int main()
{
int s[] = {1, 3, 0, 5, 8, 5};
int f[] = {2, 4, 6, 7, 9, 9};
int n = sizeof(s)/sizeof(s[0]);
printMaxActivities(s, f, n);
return 0;
}
Java
// The following implementation assumes that the activities
// are already sorted according to their finish time
import java.util.*;
import java.lang.*;
import java.io.*;
class ActivitySelection
{
// Prints a maximum set of activities that can be done by a single
// person, one at a time.
// n --> Total number of activities
// s[] --> An array that contains start time of all activities
// f[] --> An array that contains finish time of all activities
public static void printMaxActivities(int s[], int f[], int n)
{
int i, j;
System.out.print("Following activities are selected : n");
// The first activity always gets selected
i = 0;
System.out.print(i+" ");
// Consider rest of the activities
for (j = 1; j < n; j++)
{
// If this activity has start time greater than or
// equal to the finish time of previously selected
// activity, then select it
if (s[j] >= f[i])
{
System.out.print(j+" ");
i = j;
}
}
}
// driver program to test above function
public static void main(String[] args)
{
int s[] = {1, 3, 0, 5, 8, 5};
int f[] = {2, 4, 6, 7, 9, 9};
int n = s.length;
printMaxActivities(s, f, n);
}
}
C#
// The following implementation assumes
// that the activities are already sorted
// according to their finish time
using System;
class GFG
{
// Prints a maximum set of activities
// that can be done by a single
// person, one at a time.
// n --> Total number of activities
// s[] --> An array that contains start
// time of all activities
// f[] --> An array that contains finish
// time of all activities
public static void printMaxActivities(int[] s,
int[] f, int n)
{
int i, j;
Console.Write("Following activities are selected : ");
// The first activity always gets selected
i = 0;
Console.Write(i + " ");
// Consider rest of the activities
for (j = 1; j < n; j++)
{
// If this activity has start time greater than or
// equal to the finish time of previously selected
// activity, then select it
if (s[j] >= f[i])
{
Console.Write(j + " ");
i = j;
}
}
}
// Driver Code
public static void Main()
{
int[] s = {1, 3, 0, 5, 8, 5};
int[] f = {2, 4, 6, 7, 9, 9};
int n = s.Length;
printMaxActivities(s, f, n);
}
}
// This code is contributed
// by ChitraNayal
Python3
"""The following implementation assumes that the activities
are already sorted according to their finish time"""
"""Prints a maximum set of activities that can be done by a
single person, one at a time"""
# n --> Total number of activities
# s[]--> An array that contains start time of all activities
# f[] --> An array that contains finish time of all activities
def printMaxActivities(s , f ):
n = len(f)
print ("The following activities are selected")
# The first activity is always selected
i = 0
print (i,end=' ')
# Consider rest of the activities
for j in range(n):
# If this activity has start time greater than
# or equal to the finish time of previously
# selected activity, then select it
if s[j] >= f[i]:
print (j,end=' ')
i = j
# Driver program to test above function
s = [1 , 3 , 0 , 5 , 8 , 5]
f = [2 , 4 , 6 , 7 , 9 , 9]
printMaxActivities(s , f)
# This code is contributed by Nikhil Kumar Singh
PHP
<?php
// PHP program for activity selection problem.
// The following implementation assumes that
// the activities are already sorted according
// to their finish time
// Prints a maximum set of activities
// that can be done by a single
// person, one at a time.
// n --> Total number of activities
// s[] --> An array that contains start
// time of all activities
// f[] --> An array that contains finish
// time of all activities
function printMaxActivities($s, $f, $n)
{
echo "Following activities are selected " . "\n";
// The first activity always gets selected
$i = 0;
echo $i . " ";
// Consider rest of the activities
for ($j = 1; $j < $n; $j++)
{
// If this activity has start time greater
// than or equal to the finish time of
// previously selected activity, then select it
if ($s[$j] >= $f[$i])
{
echo $j . " ";
$i = $j;
}
}
}
// Driver Code
$s = array(1, 3, 0, 5, 8, 5);
$f = array(2, 4, 6, 7, 9, 9);
$n = sizeof($s);
printMaxActivities($s, $f, $n);
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// The following implementation assumes that the activities
// are already sorted according to their finish time
// Prints a maximum set of activities that can be done by a single
// person, one at a time.
// n --> Total number of activities
// s[] --> An array that contains start time of all activities
// f[] --> An array that contains finish time of all activities
function printMaxActivities(s,f,n)
{
let i, j;
document.write("Following activities are selected : n");
// The first activity always gets selected
i = 0;
document.write(i+" ");
// Consider rest of the activities
for (j = 1; j < n; j++)
{
// If this activity has start time greater than or
// equal to the finish time of previously selected
// activity, then select it
if (s[j] >= f[i])
{
document.write(j+" ");
i = j;
}
}
}
// Driver program to test above function
let s = [1, 3, 0, 5, 8, 5]
let f = [2, 4, 6, 7, 9, 9]
let n = s.length;
printMaxActivities(s, f, n);
// This code is contributed by avanitrachhadiya2155
</script>
C++
// C++ program for activity selection problem
// when input activities may not be sorted.
#include <bits/stdc++.h>
using namespace std;
// A job has a start time, finish time and profit.
struct Activitiy
{
int start, finish;
};
// A utility function that is used for sorting
// activities according to finish time
bool activityCompare(Activitiy s1, Activitiy s2)
{
return (s1.finish < s2.finish);
}
// Returns count of the maximum set of activities that can
// be done by a single person, one at a time.
void printMaxActivities(Activitiy arr[], int n)
{
// Sort jobs according to finish time
sort(arr, arr+n, activityCompare);
cout << "Following activities are selected n";
// The first activity always gets selected
int i = 0;
cout << "(" << arr[i].start << ", " << arr[i].finish << "), ";
// Consider rest of the activities
for (int j = 1; j < n; j++)
{
// If this activity has start time greater than or
// equal to the finish time of previously selected
// activity, then select it
if (arr[j].start >= arr[i].finish)
{
cout << "(" << arr[j].start << ", "
<< arr[j].finish << "), ";
i = j;
}
}
}
// Driver program
int main()
{
Activitiy arr[] = {{5, 9}, {1, 2}, {3, 4}, {0, 6},
{5, 7}, {8, 9}};
int n = sizeof(arr)/sizeof(arr[0]);
printMaxActivities(arr, n);
return 0;
}
Java
// Java program for activity selection problem
// when input activities may not be sorted.
import java.io.*;
import java.util.*;
// A job has a start time, finish time and profit.
class Activity
{
int start, finish;
// Constructor
public Activity(int start, int finish)
{
this.start = start;
this.finish = finish;
}
}
// class to define user defined comparator
class Compare
{
// A utility function that is used for sorting
// activities according to finish time
static void compare(Activity arr[], int n)
{
Arrays.sort(arr, new Comparator<Activity>()
{
@Override
public int compare(Activity s1, Activity s2)
{
return s1.finish - s2.finish;
}
});
}
}
// Driver class
class GFG {
// Returns count of the maximum set of activities that
// can
// be done by a single person, one at a time.
static void printMaxActivities(Activity arr[], int n)
{
// Sort jobs according to finish time
Compare obj = new Compare();
obj.compare(arr, n);
System.out.println(
"Following activities are selected :");
// The first activity always gets selected
int i = 0;
System.out.print("(" + arr[i].start + ", "
+ arr[i].finish + "), ");
// Consider rest of the activities
for (int j = 1; j < n; j++)
{
// If this activity has start time greater than
// or equal to the finish time of previously
// selected activity, then select it
if (arr[j].start >= arr[i].finish)
{
System.out.print("(" + arr[j].start + ", "
+ arr[j].finish + "), ");
i = j;
}
}
}
// Driver code
public static void main(String[] args)
{
int n = 6;
Activity arr[] = new Activity[n];
arr[0] = new Activity(5, 9);
arr[1] = new Activity(1, 2);
arr[2] = new Activity(3, 4);
arr[3] = new Activity(0, 6);
arr[4] = new Activity(5, 7);
arr[5] = new Activity(8, 9);
printMaxActivities(arr, n);
}
}
// This code is contributed by Dharanendra L V.
Python3
''' Python program for activity selection problem
when input activities may not be sorted.'''
def MaxActivities(arr, n):
selected = []
# Sort jobs according to finish time
Activity.sort(key = lambda x : x[1])
# The first activity always gets selected
i = 0
selected.append(arr[i])
for j in range(1, n):
'''If this activity has start time greater than or
equal to the finish time of previously selected
activity, then select it'''
if arr[j][0] >= arr[i][1]:
selected.append(arr[j])
i = j
return selected
# Driver code
Activity = [[5, 9], [1, 2], [3, 4], [0, 6],[5, 7], [8, 9]]
n = len(Activity)
selected = MaxActivities(Activity, n)
print("Following activities are selected :")
print(selected)
# This cde is contributed by kshitijjainm
Javascript
<script>
/* JavaScript program for activity selection problem
when input activities may not be sorted.*/
function MaxActivities(arr, n){
let selected = [];
// Sort jobs according to finish time
Activity = Activity.sort(function(a,b) {
return a[1] - b[1];
});
// The first activity always gets selected
let i = 0
selected.push(arr[i]);
for(let j=1;j<n;j++){
/*If this activity has start time greater than or
equal to the finish time of previously selected
activity, then select it*/
if( arr[j][0] >= arr[i][1]){
selected.push(arr[j]);
i = j;
}
}
return selected;
}
// Driver code
Activity = [[5, 9], [1, 2], [3, 4], [0, 6],[5, 7], [8, 9]];
n = Activity.length;
selected = MaxActivities(Activity, n);
document.write("Following activities are selected : <br>")
console.log(selected)
for(let i = 0;i<selected.length;i++)
document.write("("+selected[i]+"), ")
</script>
CPP
// C++ program for activity selection problem
// when input activities may not be sorted.
#include <bits/stdc++.h>
using namespace std;
void SelectActivities(vector<int>s,vector<int>f){
// Vector to store results.
vector<pair<int,int>>ans;
// Minimum Priority Queue to sort activities in ascending order of finishing time (f[i]).
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>p;
for(int i=0;i<s.size();i++){
// Pushing elements in priority queue where the key is f[i]
p.push(make_pair(f[i],s[i]));
}
auto it = p.top();
int start = it.second;
int end = it.first;
p.pop();
ans.push_back(make_pair(start,end));
while(!p.empty()){
auto itr = p.top();
p.pop();
if(itr.second >= end){
start = itr.second;
end = itr.first;
ans.push_back(make_pair(start,end));
}
}
cout << "Following Activities should be selected. " << endl << endl;
for(auto itr=ans.begin();itr!=ans.end();itr++){
cout << "Activity started at: " << (*itr).first << " and ends at " << (*itr).second << endl;
}
}
// Driver program
int main()
{
vector<int>s = {1, 3, 0, 5, 8, 5};
vector<int>f = {2, 4, 6, 7, 9, 9};
SelectActivities(s,f);
return 0;
}
Java
// java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// Pair class
static class Pair {
int first;
int second;
Pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
static void SelectActivities(int s[], int f[])
{
// Vector to store results.
ArrayList<Pair> ans = new ArrayList<>();
// Minimum Priority Queue to sort activities in
// ascending order of finishing time (f[i]).
PriorityQueue<Pair> p = new PriorityQueue<>(
(p1, p2) -> p1.first - p2.first);
for (int i = 0; i < s.length; i++) {
// Pushing elements in priority queue where the
// key is f[i]
p.add(new Pair(f[i], s[i]));
}
Pair it = p.poll();
int start = it.second;
int end = it.first;
ans.add(new Pair(start, end));
while (!p.isEmpty()) {
Pair itr = p.poll();
if (itr.second >= end) {
start = itr.second;
end = itr.first;
ans.add(new Pair(start, end));
}
}
System.out.println(
"Following Activities should be selected. \n");
for (Pair itr : ans) {
System.out.println(
"Activity started at: " + itr.first
+ " and ends at " + itr.second);
}
}
// Driver Code
public static void main(String[] args)
{
int s[] = { 1, 3, 0, 5, 8, 5 };
int f[] = { 2, 4, 6, 7, 9, 9 };
// Function call
SelectActivities(s, f);
}
}
// This code is contributed by Kingash.
Python3
# Python program for activity selection problem
# when input activities may not be sorted.
from heapq import heappop, heappush
# Function to select activites
def SelectActivities(s, f):
ans = []
p = []
# Pushing elements in the list
for i, j in zip(s, f):
heappush(p, (j, i))
it = heappop(p)
start = it[1]
end = it[0]
ans.append(it)
# Sorting process
while p:
it = heappop(p)
if it[1] >= end:
start = it[1]
end = it[0]
ans.append(it)
print("Following Activities should be selected.\n")
for f, s in ans:
print(f"Activity started at {s} and ended at {f}")
if __name__ == "__main__":
s = [1, 3, 0, 5, 8, 5]
finish = [2, 4, 6, 7, 9, 9]
SelectActivities(s, finish)
# This code is contribute by kraanzu.
Javascript
<script>
// javascript program for the above approach
// Pair class
class Pair
{
constructor(first,second)
{
this.first = first;
this.second = second;
}
}
function SelectActivities(s,f)
{
// Vector to store results.
let ans = [];
// Minimum Priority Queue to sort activities in
// ascending order of finishing time (f[i]).
let p = [];
for (let i = 0; i < s.length; i++) {
// Pushing elements in priority queue where the
// key is f[i]
p.push(new Pair(f[i], s[i]));
}
p.sort(function(a,b){return a.first-b.first;});
let it = p.shift();
let start = it.second;
let end = it.first;
ans.push(new Pair(start, end));
while (p.length!=0) {
let itr = p.shift();
if (itr.second >= end) {
start = itr.second;
end = itr.first;
ans.push(new Pair(start, end));
}
}
document.write(
"Following Activities should be selected. <br>");
for(let itr of ans.values()) {
document.write(
"Activity started at: " + itr.first
+ " and ends at " + itr.second+"<br>");
}
}
// Driver Code
let s=[1, 3, 0, 5, 8, 5 ];
let f=[2, 4, 6, 7, 9, 9 ];
// Function call
SelectActivities(s, f);
// This code is contributed by rag2127
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA