3

No acabo de ver como hacerlo.

Si tengo monedas de 2€, billetes de 5€ y de 10€ infinitos, ¿Cómo puedo sacar cuál es la mejor manera de dar el cambio?, lo he buscado por intenret cómo hacerlo con programación dinámica pero no me entero muy bien...

He intentado esto pero me he topado que no puede calcular todos los resultados...

function optimalChange($s) 
{
$error = false;
if ($s >= 0 && $s <= 2147483647) {
    if ($s % 10 === 0) {
        $bill10 = $s / 10;
        $bill5 = 0;
        $coin2 = 0;
    } else {
        $res = $s /10;
        $arr = explode('.', $res);
        $bill10 = (int) $arr[0];
        $dec = $arr[1];
        if ($dec % 5 === 0) {
            $bill5 = $dec / 5;
            $coin2 = 0;
        } else {
            var_dump($dec);
            if ($dec > 5) {
                $res = $dec / 5;
                var_dump($res);
                $arr = explode('.', $res);
                $bill5 = (int) $arr[0];
                $dec = (int) $arr[1];
                if ($dec % 2 === 0) {
                    var_dump($dec);
                    $coin2 = $dec / 4;
                } else {
                    $error = true;
                }
            } else {
                var_dump($dec.' 42');
                if ($dec % 2 === 0) {
                    $bill5 = 0;
                    $coin2 = $dec / 2;
                } else {
                    if ($dec >= 2) {
                        if ($dec % 2 === 0) {
                            var_dump($dec.' 49');
                            $bill5 = 0;
                            $coin2 = $dec / 2;
                        }
                    } else {
                        $return = 'impossible';
                    }
                }
            }
        }
    }
    if (true === $error) {
        $return = 'impossible';
    } else {
        $change = new Change();
        $change->bill10 = $bill10;
        $change->bill5 = $bill5;
        $change->coin2 = $coin2;
        $return = $change;
    }
    } else {
        $return = 'impossible';
    }

    return $return;
}
4
  • No se entiende muy bien. ¿Dar el cambio de qué, de cuánto?
    – A. Cedano
    Commented el 14 oct. 2019 a las 14:13
  • de la variable que le pasas ocmo parámetro.
    – Pavlo B.
    Commented el 14 oct. 2019 a las 14:19
  • deberias plantearte usar arrays. Piensa que tienes un listado de monedas y billetes (De 10, 5 y 2), puedes ir recorriendo ese listado (de mayor a menor), e ir dividiendo por cada valor. de esa manera sabes cuantos billetes de 10 en una iteracion, en la siguiente sabras cuantos de 5 y en la siguiente de cuantas monedas. Ten en cuenta que existen combinaciones que no vas a poder devolver con esas cantidades...
    – Jakala
    Commented el 14 oct. 2019 a las 14:56
  • Eso es lo que quería hacer pero llega un punto en el que el resto que queda no es divisible por 2 que es el más pequeño, en tal caso se da por imposible. He visto por ahí esta solución pero no la entiendo jcsis.wordpress.com/2013/12/22/… Ahí habla de rellenar una tabla pero no veo el cómo rellenarla...
    – Pavlo B.
    Commented el 14 oct. 2019 a las 14:58

1 respuesta 1

2

Quizá esta solución te puede servir, la función devuelve un array indicando cuántas monedas de cada una hay que dar en el cambio.

Este es el código, he explicado en comentarios lo básico:

function bestChange($coinValues,$mTotal)
{
    #Total de monedas existentes
    $n=count($coinValues);
    #Array donde iremos guardando cuántas monedas de cada una hay que dar
    $arr=array();
    for( $i=0; $i< $n; $i++ ) {
      while($mTotal >= $coinValues[$i])
      {
        #Vamos reduciendo el total  
        $mTotal= $mTotal - $coinValues[$i];
        #Verificamos si la moneda está en el array final  
        if (!isset($arr[$coinValues[$i]])) {
            #Si no está creamos una clave para esa moneda y le asignamos 0
            $arr[$coinValues[$i]]  = 0;
        }
        #Incrementamos en 1 el contador para la moneda actual  
        $arr[$coinValues[$i]] ++;
      }
    }
    return $arr;
}

Prueba

Vamos a cambiar 27 euros:

$mTotal=27;
$allCoins=array(10,5,2);
$r=bestChange($allCoins,$mTotal);
var_dump($r);

Salida:

array(3) {
  [10]=>
  int(2)
  [5]=>
  int(1)
  [2]=>
  int(1)
}

Tenemos que dar al usuario: 2 billetes de 10, 1 billete de 5 y una moneda de 2.

Algunas notas

  • Si el array de monedas es dinámico, conviene ordenarlo de mayor a menor, porque de lo contrario la función no dará el resultado esperado.

  • En el planteamiento del problema quedan quizá algunas lagunas. Por ejemplo, ¿qué ocurre con lo que resta en el caso de que sobre dinero? La función no aborda ese posible problema, porque no viene explicado en la pregunta.

Fuente

Este código es una adaptación al lenguaje PHP de una solución similar planteada en Java, y la fuente se encuentra en este enlace.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.