// Descomenta la version que quieras probar

#include <iostream>
#include <vector>

using namespace std;

/***************************************************************************
 VERSION 1: RECURSIVA, INEFICIENTE
 ***************************************************************************/

/*
int minimaCantidadMonedas(const vector<int> & valoresMonedas,
                          int deudaRestante) {

   // Minima cantidad de monedas necesaria para sumar deudaRestante

   int resultado;

   if (deudaRestante == 0)
      resultado = 0;
   else {
      int minimo = deudaRestante; // Se puede inicializar a numeric_limits<int>::max(),
                                  // pero en este ejercicio tambien sirve esto, que
                                  // corresponde a pagar deudaRestante con monedas de valor 1
      for (int valor :  valoresMonedas)
	 if (deudaRestante - valor >= 0)
	    minimo = min(minimo,
                         1 + minimaCantidadMonedas(valoresMonedas, deudaRestante - valor));
      resultado = minimo;
   }

   return resultado;

}
*/

/***************************************************************************
 VERSION 2: RECURSIVA, EFICIENTE
 ***************************************************************************/

/*
#define DESCONOCIDO -1

int minimaCantidadMonedas(const vector<int> & valoresMonedas,
                          int deudaRestante,
                          vector<int> & resultado) {

   if (resultado[deudaRestante] == DESCONOCIDO)
      if (deudaRestante == 0)
	 resultado[deudaRestante] = 0;
      else {
         int minimo = deudaRestante;
	 for (int valor :  valoresMonedas)
            if (deudaRestante - valor >= 0)
               minimo = min(minimo,
                            1 + minimaCantidadMonedas(valoresMonedas, deudaRestante - valor, resultado));
         resultado[deudaRestante] = minimo;
      }

   return resultado[deudaRestante];

}

int minimaCantidadMonedas(const vector<int> & valoresMonedas,
                          int deudaInicial) {

   vector<int> resultado(deudaInicial + 1, DESCONOCIDO);
   return minimaCantidadMonedas(valoresMonedas, deudaInicial, resultado);

}
*/

/***************************************************************************
 VERSION 3: NO RECURSIVA, EFICIENTE
 ***************************************************************************/

/*
int minimaCantidadMonedas(const vector<int> & valoresMonedas,
                          int deudaInicial) {
   
   vector<int> resultado(deudaInicial + 1);
   
   for (int deudaRestante = 0; deudaRestante <= deudaInicial; deudaRestante++)
      if (deudaRestante == 0)
	 resultado[deudaRestante] = 0;
      else {
         int minimo = deudaRestante;
	 for (int valor :  valoresMonedas)
            if (deudaRestante - valor >= 0)
	       minimo = min(minimo,
			    1 + resultado[deudaRestante - valor]);
         resultado[deudaRestante] = minimo;
      }

   return resultado[deudaInicial];

}
*/

/***************************************************************************
 VERSION 4: NO RECURSIVA, EFICIENTE, MOSTRANDO MONEDAS ELEGIDAS
 ***************************************************************************/

/*
void mostrarMonedasElegidas(const vector<int> & valoresMonedas,
                            const vector<int> & resultado) {

  int deuda = resultado.size() - 1;

  while (deuda > 0)
    for (int valor :  valoresMonedas)
      if (deuda - valor >= 0
	  && resultado[deuda] == resultado[deuda - valor] + 1) {
	cout << "dale " << valor << endl;
	deuda -= valor;
	break;
      }

}

int minimaCantidadMonedas(const vector<int> & valoresMonedas,
                          int deuda) {
   
   vector<int> resultado(deuda + 1);
   
   for (int deudaRestante = 0; deudaRestante <= deuda; deudaRestante++)
      if (deudaRestante == 0)
	 resultado[deudaRestante] = 0;
      else {
         int minimo = deudaRestante;
	 for (int valor :  valoresMonedas)
            if (deudaRestante - valor >= 0)
               minimo = min(minimo,
			    1 + resultado[deudaRestante - valor]);
         resultado[deudaRestante] = minimo;
      }

   mostrarMonedasElegidas(valoresMonedas, resultado);
   return resultado[deuda];

}
*/

/***************************************************************************
 EJEMPLOS
 ***************************************************************************/

int main () {
   vector<int> monedasMordor = {5, 21, 1, 25};
   vector<int> monedasPandora = {1, 4, 6, 10};

   int resultado;

   cout << "Probando monedas de Mordor:" << endl;
   cout << "===========================" << endl << endl;

   cout << "Deuda: 22" << endl;
   resultado = minimaCantidadMonedas(monedasMordor, 22);
   cout << "Total monedas: " << resultado << endl;
   if (resultado == 2)
      cout << "OK" << endl << endl;
   else
      cout << "MAL" << endl << endl;
   
   cout << "Deuda: 63" << endl;
   resultado = minimaCantidadMonedas(monedasMordor, 63);
   cout << "Total monedas: " << resultado << endl;
   if (resultado == 3)
      cout << "OK" << endl << endl;
   else
      cout << "MAL" << endl << endl;
   
   cout << "Deuda: 65" << endl;
   resultado = minimaCantidadMonedas(monedasMordor, 65);
   cout << "Total monedas: " << resultado << endl;
   if (resultado == 5)
      cout << "OK" << endl << endl;
   else
      cout << "MAL" << endl << endl;

   cout << "Probando monedas de Pandora:" << endl;
   cout << "============================" << endl << endl;

   cout << "Deuda: 22" << endl;
   resultado = minimaCantidadMonedas(monedasPandora, 22);
   cout << "Total monedas: " << resultado << endl;
   if (resultado == 3)
      cout << "OK" << endl << endl;
   else
      cout << "MAL" << endl << endl;
   
   cout << "Deuda: 63" << endl;
   resultado = minimaCantidadMonedas(monedasPandora, 63);
   cout << "Total monedas: " << resultado << endl;
   if (resultado == 8)
      cout << "OK" << endl << endl;
   else
      cout << "MAL" << endl << endl;
   
   cout << "Deuda: 65" << endl;
   resultado = minimaCantidadMonedas(monedasPandora, 65);
   cout << "Total monedas: " << resultado << endl;
   if (resultado == 8)
      cout << "OK" << endl << endl;
   else
      cout << "MAL" << endl << endl;

}