// Descomenta la version que quieras probar

#include <iostream>
#include <vector>

using namespace std;

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

/*
float maximoValorAcumulable(const vector<int> & puntos,
			    const vector<float> & valor,
			    int saldo) {

   // Maximo valor acumulable eligiendo objetos cuya suma de puntos no supere ese saldo

   float resultado = 0;
   for (int i = 0; i < puntos.size(); i++)
      if (saldo >= puntos[i])
	 resultado = max(resultado,
			 valor[i] + maximoValorAcumulable(puntos, valor, saldo - puntos[i]));
   
   return resultado;
   
}
*/

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

/*
float maximoValorAcumulable(const vector<int> & puntos,
			    const vector<float> & valor,
			    int saldo,
			    vector<float> & resultado) {

   if (resultado[saldo] == -1) {
      resultado[saldo] = 0;
      for (int i = 0; i < puntos.size(); i++)
	 if (saldo >= puntos[i])
	    resultado[saldo] = max(resultado[saldo],
				   valor[i] + maximoValorAcumulable(puntos, valor, saldo - puntos[i], resultado));
   }

   return resultado[saldo];

}

float maximoValorAcumulable(const vector<int> & puntos,
			    const vector<float> & valor,
			    int saldoDePuntos) {

   vector<float> resultado(saldoDePuntos + 1, -1);

   return maximoValorAcumulable(puntos, valor, saldoDePuntos, resultado);
   
}
*/

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

/*
float maximoValorAcumulable(const vector<int> & puntos,
			    const vector<float> & valor,
			    int saldoDePuntos) {

   vector<float> resultado(saldoDePuntos + 1);
   
   for (int saldo = 0; saldo <= saldoDePuntos; saldo++) {
      resultado[saldo] = 0;
      for (int i = 0; i < puntos.size(); i++)
	 if (saldo >= puntos[i])
	    resultado[saldo] = max(resultado[saldo],
				   valor[i] + resultado[saldo - puntos[i]]);
   }
   
   return resultado[saldoDePuntos];
   
}
*/

/***************************************************************************
 EJEMPLO
 ***************************************************************************/

int main () {

   vector<int> ejemploPuntos = {12, 8, 5, 3, 15};
   vector<float> ejemploValor = {400, 350, 180, 100, 500};

   float resultado = maximoValorAcumulable(ejemploPuntos, ejemploValor, 15);
   cout << "Maximo valor acumulable: " << resultado << endl;
   if (resultado == 550)
      cout << "OK" << endl;
   else
      cout << "MAL" << endl;

}