Problema de cambio en monedas en C# determinar el número mínimo a devolver

[delicado95]

Necesito ayuda con el TÍPICO ejercicio de cambio en monedas(no sabia que era tan típico hasta que lo googleé)...

Estoy dando C# y solo encuentro el ejercicio en c/c++/java... me gustaria ver el planteamiento del problema e intentar solucionarlo yo, especificamente del problema que planteo ahora: (enunciado que adjunto)

ENUNCIADO

El abuelo de Quique es eldueño de una tienda en la esquina de mi calle. Este verano ha pedido a su nieto que le ayude encargándose de cobrar. Quique está muy preocupado, porque su abuelo tiene muchas manías. Para empezar
no tiene caja registradora, sino que realiza las cuentas de cabeza. Además para agradar a sus clientes les entrega siempre el menor número posible de monedas para que no se les llene el bolsillo.
Como a Quique no se le da muy bien eso de las cuentas, ha decidido llevarse  su ordenador sin que se entere su abuelo. Ahora necesita un programa que le calcule cuántas monedas de cada tipo debe dar de cambio.


Entrada

La entrada comienza con un entero que indica el número de casos de prueba que vendrán a continuación. Cada caso consta de dos valores. El primero indica el coste de la compra expresado en céntimos de euro y el segundo el dinero entregado por el cliente, expresado también en céntimos de euro.

Salida

Para cada caso de prueba se indicará en una línea independiente el número de monedas de 2 euros, 1euro, 50 cts, 20 cts, 10 cts, 5 cts, 2 cts y 1 céntimo que debe entregar Quique al cliente. En caso de que el dinero entregado no cubra el coste de la compra se escribirá en la salida DEBE seguido de la cantidad que queda por pagar

Ejemplo ejecución:


ENTRADA         SALIDA
3                     0 1 0 2 0 0 0 0
60
200   
_______________________________________
461                    2 1 0 1 1 1 2 0
1000
_______________________________________   
3000             DEBE 3000
0   

Esto es lo que he deducido...

Código: [Seleccionar]

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Abuelo_de_kike
{
    class Program
    {
        static void Main(string[] args)
        {
            int nCasos, nCompra, nEntrega, nTotal;
            int n2euros, n1euro, n50cent, n20cent, n10cent, n5cent, n2cent, n1cent;
            Console.WriteLine("Introduce el numero de casos de prueba");
            nCasos = int.Parse(Console.ReadLine());
            while (nCasos !=0)
            {
               
            Console.WriteLine("Introduce el coste de la compra(en céntimos)");
            nCompra = int.Parse(Console.ReadLine());
            Console.WriteLine("Introduce el dinero entregado (en céntimos)");
            nEntrega = int.Parse(Console.ReadLine());
            nTotal = nEntrega - nCompra;
                if (nTotal > 0);
                {
                n2euros = nTotal / 200;
                nTotal = nTotal - n2euros * 200;

                n1euro = nTotal / 100;
                nTotal = nTotal - n1euro * 100;

                n50cent = nTotal / 50;
                nTotal = nTotal - n50cent * 50;

                n20cent = nTotal / 20;
                nTotal = nTotal - n20cent * 20;

                n10cent = ( nTotal / 10);
                nTotal = nTotal - n10cent * 10;

                n5cent = nTotal / 5;
                nTotal = nTotal - n5cent * 5;

                n2cent = nTotal / 2;
                nTotal = nTotal - n2cent * 2;

                n1cent = nTotal / 1;
                nTotal = nTotal - n1cent * 1;
                }
                else
                    Console.WriteLine("Debe dinero");

            }
           
        }
    }
}

[Ogramar]

Buenas, aquí tienes el algoritmo expresado en php (en c# hay que adaptarlo)

Hay que pasarle los valores de cantidad (por ejemplo 100) y de monedas disponibles (por ejemplo 1, 5, 10, 25)

Código: [Seleccionar]

function make_change ($amount, $coins)
{
  $coin_count = count($coins);
 
  $table = array();
 
  for ($i = -1; $i <= $amount; $i++) {
    for($j = -1; $j <= $coin_count; $j++) {
      // Rules
      // 1: table[0,0] or table[0,x] = 1
      // 2: talbe[i <= -1, x] = 0
      // 3: table[x, j <= -1] = 0
     
      $total = 0;
         
      // first sub-problem
      // count(n, m-1)
      $n = $i;
      $m = $j-1;
      if ($n == 0) // rule 1
        $total += 1;
      else if ($n <= -1) // rule 2
        $total += 0;
      else if (($m <= 0) && ($n >= 1))
        $total += 0;
      else
        $total += $table[$n][$m];
     
      // second sub-problem
      // count(n-S[m], m)
      if (($j-1) <= -1)
        $total += 0;
      else {
        $n = $i - $coins[$j - 1];
        $m = $j;
        if ($n == 0) // rule 1
          $total += 1;
        else if ($n <= -1) // rule 2
          $total += 0;
        else if (($m <= 0) && ($n >= 1)) // rule 3
          $total += 0;
        else
          $total += $table[$n][$m];
      }
     
      $table[$i][$j] = $total;
    }
  }
  return $table[$i-1][$j-1];
}

En C# he encontrado este:

Código: [Seleccionar]

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

class Program
{
    static void Main()
    {
List<int> coins = new List<int>();
List<int> amounts = new List<int>() { 1, 5, 10, 25, 50 };
//
// Compute change for 51 cents.
//
Change(coins, amounts, 0, 0, 51);
    }

    static void Change(List<int> coins, List<int> amounts, int highest, int sum, int goal)
    {
//
// See if we are done.
//
if (sum == goal)
{
    Display(coins, amounts);
    return;
}
//
// See if we have too much.
//
if (sum > goal)
{
    return;
}
//
// Loop through amounts.
//
foreach (int value in amounts)
{
    //
    // Only add higher or equal amounts.
    //
    if (value >= highest)
    {
List<int> copy = new List<int>(coins);
copy.Add(value);
Change(copy, amounts, value, sum + value, goal);
    }
}
    }

    static void Display(List<int> coins, List<int> amounts)
    {
foreach (int amount in amounts)
{
    int count = coins.Count(value => value == amount);
    Console.WriteLine("{0}: {1}",
amount,
count);
}
Console.WriteLine();
    }
}

Salidas

Salidas

1: 51
5: 0
10: 0
25: 0
50: 0

1: 46
5: 1
10: 0
25: 0
50: 0

1: 41
5: 2
10: 0
25: 0
50: 0

1: 41
5: 0
10: 1
25: 0
50: 0

1: 36
5: 3
10: 0
25: 0
50: 0

[Voxxii]

Te hize una solución a lo que pides, eso sí no controlé que cuando pides coste o lo que entregas metas un entero. Es decir, si donde pone "introduce el coste" pones algo que no sea de tipo int te dará una excepción no controlada, Ej meter 'a'.

Tampoco te controlé los casos pues es hacer un while (caso > 0) que englobe el codigo disminuyendo uno "caso--;" al final de cada vuelta al bucle.

Código: [Seleccionar]

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MinimoMonedas
{
    class ConversionMonedas
    {
        static void Main(string[] args)
        {
            int[] totalMonedas = new int[8]; //Aqui guardamos el total de monedas. Abajo se pone que posición ocupa cada moneda.
            string[] nombreMonedas = { "2 Euros", "1 Euro", "50 Céntimos", "20 Céntimos", "10 Céntimos", "5 Céntimos", "2 Céntimos", "1 Céntimo" }; //Guardamos el nombre de cada moneda en este array.

            //Las monedas no cambiarán, por lo tanto  guardamos el valor como constante. (Se podría utilizar otro array para esto pero creo que así se ve más claro).
            const int MONEDA2E = 200;   //totalMonedas [0]
            const int MONEDA1E = 100;   //totalMonedas [1]
            const int MONEDA50C = 50;   //totalMonedas [2]
            const int MONEDA20C = 20;   //totalMonedas [3]
            const int MONEDA10C = 10;   //totalMonedas [4]
            const int MONEDA5C = 5;     //totalMonedas [5]
            const int MONEDA2C = 2;     //totalMonedas [6]
            const int MONEDA1C = 1;     //totalMonedas [7]




            int coste;
            int entrega;
            int vuelta = 0;
            int auxVuelta = 0; //Para aplicar las cuentas y dejar el valor de vuelta almacenado.

            Console.Write("Introduce el precio del artículo: ");
            coste = int.Parse(Console.ReadLine());
            Console.Write("\nIntroduce cuanto entrega el cliente: ");
            entrega = int.Parse(Console.ReadLine());
            {

                if (entrega > coste)
                {
                    vuelta = entrega - coste;
                    auxVuelta = vuelta;

                    do
                    {
                        if (auxVuelta >= MONEDA2E)
                        {
                            auxVuelta -= MONEDA2E; //Restamos a la vuelta la moneda que vamos a dar.
                            totalMonedas[0]++; //Sumamos 1 a la posicion de la moneda de 2€ en el array de int.
                            continue; //Con cada continue volvemos a la condición booleana del DO WHILE, y volvemos a iniciar el bucle desde el principio.
                        }
                        if (auxVuelta >= MONEDA1E)
                        {
                            auxVuelta -= MONEDA1E;
                            totalMonedas[1]++;
                            continue;
                        }
                        if (auxVuelta >= MONEDA50C)
                        {
                            auxVuelta -= MONEDA50C;
                            totalMonedas[2]++;
                            continue;
                        }
                        if (auxVuelta >= MONEDA20C)
                        {
                            auxVuelta -= MONEDA20C;
                            totalMonedas[3]++;
                            continue;
                        }
                        if (auxVuelta >= MONEDA10C)
                        {
                            auxVuelta -= MONEDA10C;
                            totalMonedas[4]++;
                            continue;
                        }
                        if (auxVuelta >= MONEDA5C)
                        {
                            auxVuelta -= MONEDA5C;
                            totalMonedas[5]++;
                            continue;
                        }
                        if (auxVuelta >= MONEDA2C)
                        {
                            auxVuelta -= MONEDA2C;
                            totalMonedas[6]++;
                            continue;
                        }
                        if (auxVuelta >= MONEDA1C)
                        {
                            auxVuelta -= MONEDA1C;
                            totalMonedas[7]++;
                            continue;
                        }
                    } while (auxVuelta != 0);
                    Console.WriteLine("\nEntrega {0} centimos y el coste es {1} centimos por lo tanto la vuelta es {2} centimos.", entrega, coste, vuelta);
                    Console.WriteLine("\nPara devolver {0} Céntimos con el mínimo de monedas hay que dar:", vuelta);
                }
                else
                    Console.WriteLine("\nEntrega {0} centimos y el coste es {1} centimos por lo tanto DEBE {2} centimos", entrega, coste, coste - entrega);

                for (int i = 0; i < totalMonedas.Length; i++) //Recorremos el array de monedas para ver cuantas hay.
                {
                    if (totalMonedas[i] != 0) //Si hay mas de 0 monedas de esa clase, las escribimos, sino, pasamos al siguiente tipo de moneda.
                        if (totalMonedas[i] == 1) //Controlamos el plural y singular en las monedas con este if.
                            Console.WriteLine("[{0}] moneda de {1}\n", totalMonedas[i], nombreMonedas[i]);
                        else
                            Console.WriteLine("[{0}] monedas de {1}\n", totalMonedas[i], nombreMonedas[i]);
                }

                Console.WriteLine("\nPulsa Enter para salir."); //Para poder leer las monedas al final sin que acabe la ejecución. Con el caso saltaría al otro caso.
                Console.ReadLine();
            }
        }
    }
}


Espero que te sea de ayuda.