// Descomenta la version que quieras probar

#include <iostream>
#include <vector>

using namespace std;

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

/*
float maximoValor(const vector<int> & peso,
		  const vector<float> & valor,
		  int objeto,
		  int pesoDisponible) {

   // Maximo valor acumulable con los objetos desde el 0 hasta ese objeto sin superar pesoDisponible

   int resultado;
   
   if (objeto == 0 && peso[objeto] > pesoDisponible)
      resultado = 0;
   else if (objeto == 0)
      resultado = valor[objeto];
   else if (peso[objeto] > pesoDisponible)
      resultado = maximoValor(peso, valor, objeto - 1, pesoDisponible);
   else
      resultado = max(valor[objeto] + maximoValor(peso, valor, objeto - 1, pesoDisponible - peso[objeto]),
		      maximoValor(peso, valor, objeto - 1, pesoDisponible));

   return resultado;

}

float maximoValor(const vector<int>  & peso,
		  const vector<float> & valor,
		  int pesoMaximo) {
   
   int ultimoObjeto = peso.size() - 1;
   return maximoValor(peso, valor, ultimoObjeto, pesoMaximo);

}
*/

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

/*
#define DESCONOCIDO -1

float maximoValor(const vector<int> & peso,
		  const vector<float> & valor,
		  int objeto,
		  int pesoDisponible,
		  vector<vector<float> > & resultado) {
   
   if (resultado[objeto][pesoDisponible] == DESCONOCIDO)
      if (objeto == 0 && peso[objeto] > pesoDisponible)
         resultado[objeto][pesoDisponible] = 0;
      else if (objeto == 0)
         resultado[objeto][pesoDisponible] = valor[objeto];
      else if (peso[objeto] > pesoDisponible)
         resultado[objeto][pesoDisponible] = maximoValor(peso, valor, objeto - 1, pesoDisponible, resultado);
      else
         resultado[objeto][pesoDisponible] = max(valor[objeto] + maximoValor(peso, valor, objeto - 1, pesoDisponible - peso[objeto], resultado),
						 maximoValor(peso, valor, objeto - 1, pesoDisponible, resultado));

   return resultado[objeto][pesoDisponible];

}

float maximoValor(const vector<int>  & peso,
		  const vector<float> & valor,
		  int pesoMaximo) {
   
   int ultimoObjeto = peso.size() - 1;
   
   vector<vector<float> > resultado(ultimoObjeto + 1, vector<float>(pesoMaximo + 1, DESCONOCIDO));
   
   return maximoValor(peso, valor, ultimoObjeto, pesoMaximo, resultado);
   
}
*/

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


float maximoValor(const vector<int>  & peso,
		  const vector<float> & valor,
		  int pesoMaximo) {
   
   int ultimoObjeto = peso.size() - 1;
   
   vector<vector<float> > resultado(ultimoObjeto + 1, vector<float>(pesoMaximo + 1));

   for (int objeto = 0; objeto <= ultimoObjeto; objeto++)
      for (int pesoDisponible = 0; pesoDisponible <= pesoMaximo; pesoDisponible++)
	 if (objeto == 0 && peso[objeto] > pesoDisponible)
	    resultado[objeto][pesoDisponible] = 0;
	 else if (objeto == 0)
	    resultado[objeto][pesoDisponible] = valor[objeto];
	 else if (peso[objeto] > pesoDisponible)
	    resultado[objeto][pesoDisponible] = resultado[objeto - 1][pesoDisponible];
	 else
	    resultado[objeto][pesoDisponible] = max(valor[objeto] + resultado[objeto - 1][pesoDisponible - peso[objeto]],
						    resultado[objeto - 1][pesoDisponible]);
   
   return resultado[ultimoObjeto][pesoMaximo];
   
}


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

int main () {

   float resultado;

   resultado = maximoValor({100, 40, 50, 80}, {5000, 3600, 4500, 8000}, 100);
   cout << "Primer ejemplo, maximo valor: " << resultado << endl;
   if (resultado == 8100)
      cout << "OK" << endl << endl;
   else
      cout << "MAL" << endl << endl;

   resultado = maximoValor({6, 5, 5}, {8000, 5000, 5000}, 10);
   cout << "Segundo ejemplo, maximo valor: " << resultado << endl;
   if (resultado == 10000) 
      cout << "OK" << endl << endl;
   else
      cout << "MAL" << endl << endl;

   resultado = maximoValor({5, 2, 1, 6, 7}, {1800, 600, 100, 2200, 2800}, 15);
   cout << "Tercer ejemplo, maximo valor: " << resultado << endl;
   if (resultado == 5600)
      cout << "OK" << endl << endl;
   else
      cout << "MAL" << endl << endl;

}