Algoritmos voraces

def cambio(monedas, cantidad):
    """Cambio voraz: siempre la moneda más grande que cabe. monedas, de mayor a menor."""
    usadas = []
    for m in monedas:
        while cantidad >= m:                    # mientras quepa, se coge (y no se replantea nunca)
            usadas.append(m)
            cantidad -= m
    return usadas


euros = [200, 100, 50, 20, 10, 5, 2, 1]
print("289 céntimos con euros:", cambio(euros, 289))
raras = [4, 3, 1]
print(f"6 con monedas de 4, 3 y 1: {cambio(raras, 6)}, pero bastan [3, 3]")

/** Cambio voraz: siempre la moneda más grande que cabe. monedas, de mayor a menor. */
function cambio(monedas, cantidad) {
    const usadas = [];
    for (const m of monedas) {
        while (cantidad >= m) {                   // mientras quepa, se coge (y no se replantea nunca)
            usadas.push(m);
            cantidad -= m;
        }
    }
    return usadas;
}

const texto = (a) => "[" + a.join(", ") + "]";
const euros = [200, 100, 50, 20, 10, 5, 2, 1];
console.log("289 céntimos con euros: " + texto(cambio(euros, 289)));
const raras = [4, 3, 1];
console.log("6 con monedas de 4, 3 y 1: " + texto(cambio(raras, 6)) + ", pero bastan [3, 3]");

using System;
using System.Collections.Generic;

class Program {
    // Cambio voraz: siempre la moneda más grande que cabe. monedas, de mayor a menor.
    static List<int> Cambio(int[] monedas, int cantidad) {
        var usadas = new List<int>();
        foreach (int m in monedas) {
            while (cantidad >= m) {               // mientras quepa, se coge (y no se replantea nunca)
                usadas.Add(m);
                cantidad -= m;
            }
        }
        return usadas;
    }

    static string Texto(List<int> l) => "[" + string.Join(", ", l) + "]";

    static void Main() {
        int[] euros = { 200, 100, 50, 20, 10, 5, 2, 1 };
        Console.WriteLine("289 céntimos con euros: " + Texto(Cambio(euros, 289)));
        int[] raras = { 4, 3, 1 };
        Console.WriteLine("6 con monedas de 4, 3 y 1: " + Texto(Cambio(raras, 6)) + ", pero bastan [3, 3]");
    }
}

<?php
/** Cambio voraz: siempre la moneda más grande que cabe. $monedas, de mayor a menor. */
function cambio(array $monedas, int $cantidad): array {
    $usadas = [];
    foreach ($monedas as $m) {
        while ($cantidad >= $m) {                 // mientras quepa, se coge (y no se replantea nunca)
            $usadas[] = $m;
            $cantidad -= $m;
        }
    }
    return $usadas;
}

function texto(array $a): string { return "[" . implode(", ", $a) . "]"; }

$euros = [200, 100, 50, 20, 10, 5, 2, 1];
echo "289 céntimos con euros: " . texto(cambio($euros, 289)) . "\n";
$raras = [4, 3, 1];
echo "6 con monedas de 4, 3 y 1: " . texto(cambio($raras, 6)) . ", pero bastan [3, 3]\n";

from collections import namedtuple

Charla = namedtuple("Charla", "nombre inicio fin")


def elegir(charlas):
    """El máximo de charlas sin solaparse: se ordena por hora de FIN y se coge cada una que empiece
    cuando acaba la última elegida. Acabar pronto deja el máximo de hueco para las demás."""
    elegidas, libre_desde = [], 0
    for c in sorted(charlas, key=lambda c: c.fin):
        if c.inicio >= libre_desde:
            elegidas.append(c)
            libre_desde = c.fin
    return elegidas


charlas = [Charla("Git", 9, 11), Charla("Docker", 10, 12), Charla("Java", 11, 13),
           Charla("SQL", 12, 14), Charla("Kotlin", 13, 15), Charla("Spring", 9, 15)]
for c in elegir(charlas):
    print(f"{c.nombre} ({c.inicio}-{c.fin})")

/** El máximo de charlas sin solaparse: se ordena por hora de FIN y se coge cada una que empiece
    cuando acaba la última elegida. Acabar pronto deja el máximo de hueco para las demás. */
function elegir(charlas) {
    const elegidas = [];
    let libreDesde = 0;
    for (const c of [...charlas].sort((a, b) => a.fin - b.fin)) {
        if (c.inicio >= libreDesde) {
            elegidas.push(c);
            libreDesde = c.fin;
        }
    }
    return elegidas;
}

const charlas = [
    { nombre: "Git", inicio: 9, fin: 11 }, { nombre: "Docker", inicio: 10, fin: 12 }, { nombre: "Java", inicio: 11, fin: 13 },
    { nombre: "SQL", inicio: 12, fin: 14 }, { nombre: "Kotlin", inicio: 13, fin: 15 }, { nombre: "Spring", inicio: 9, fin: 15 },
];
for (const c of elegir(charlas)) console.log(`${c.nombre} (${c.inicio}-${c.fin})`);

using System;
using System.Collections.Generic;
using System.Linq;

record Charla(string Nombre, int Inicio, int Fin);

class Program {
    // El máximo de charlas sin solaparse: se ordena por hora de FIN y se coge cada una que empiece
    // cuando acaba la última elegida. Acabar pronto deja el máximo de hueco para las demás.
    static List<Charla> Elegir(IEnumerable<Charla> charlas) {
        var elegidas = new List<Charla>();
        int libreDesde = 0;
        foreach (var c in charlas.OrderBy(c => c.Fin)) {
            if (c.Inicio >= libreDesde) {
                elegidas.Add(c);
                libreDesde = c.Fin;
            }
        }
        return elegidas;
    }

    static void Main() {
        var charlas = new List<Charla> {
            new("Git", 9, 11), new("Docker", 10, 12), new("Java", 11, 13),
            new("SQL", 12, 14), new("Kotlin", 13, 15), new("Spring", 9, 15),
        };
        foreach (var c in Elegir(charlas)) Console.WriteLine(
quot;{c.Nombre} ({c.Inicio}-{c.Fin})");
    }
}

<?php
/** El máximo de charlas sin solaparse: se ordena por hora de FIN y se coge cada una que empiece
    cuando acaba la última elegida. Acabar pronto deja el máximo de hueco para las demás. */
function elegir(array $charlas): array {
    usort($charlas, fn($a, $b) => $a["fin"] <=> $b["fin"]);
    $elegidas = [];
    $libreDesde = 0;
    foreach ($charlas as $c) {
        if ($c["inicio"] >= $libreDesde) {
            $elegidas[] = $c;
            $libreDesde = $c["fin"];
        }
    }
    return $elegidas;
}

$charlas = [
    ["nombre" => "Git", "inicio" => 9, "fin" => 11], ["nombre" => "Docker", "inicio" => 10, "fin" => 12],
    ["nombre" => "Java", "inicio" => 11, "fin" => 13], ["nombre" => "SQL", "inicio" => 12, "fin" => 14],
    ["nombre" => "Kotlin", "inicio" => 13, "fin" => 15], ["nombre" => "Spring", "inicio" => 9, "fin" => 15],
];
foreach (elegir($charlas) as $c) echo "{$c['nombre']} ({$c['inicio']}-{$c['fin']})\n";