/************************************************************************\
* Programa: b_b.cpp                                                      *
* Descripción: Programa que resuelve un problema de capacidad variable   *
*              mediante el alg. branch and bound                         *
* Autor: Pedro Corcuera                                                  *
* Revisión: 1.0 2/02/2008                                                *
\************************************************************************/

#include <iostream>
#include <iomanip>
using namespace std;

const int N=15;
const int LIM_INF=10;
const int PASO=10;
const int LIM_SUP=120;

struct object {
  int valor;
  int peso;
};

struct object obj[]={ 18,10,
		      20,11,
		      17,12,
		      19,13,
		      25,14,
		      21,15,
		      27,16,
		      23,17,
		      25,18,
		      24,19,
		      };
void intentar(int i,int x,int y);
int limw,totv,maxv;
int w1,w2,w3;
int s[N];
int opts[N];
int n;

int main(void)
{
 int i;
 int capi, vali;
 char objetos[N];

 totv=0;

 n=(int)sizeof( obj)/sizeof( obj[0]);
 for(i=0; i<n; i++)
   totv += obj[i].valor;
 w1=LIM_INF; w2=PASO; w3=LIM_SUP;

 cout << "Numero de objetos: " << n << "  Valor Total: " << totv << endl;
 cout << "Obj.   Valor    Peso \n" ;
 for(i=0; i<n; i++)
    cout << i+1 << "\t" << obj[i].valor << "\t" << obj[i].peso << endl;
 cout << "\n===========================\n" << "Cap." ;

 for(i=0;i<n;i++)
    cout << setw(3) << i+1;

 cout << "\tPeso\tValor\n";

 do {
  limw=w1;
  maxv=0;
  for(i=0;i<n;i++)
  {
    s[i]=-1;
    opts[i]=-1;
  }
  intentar(0,0,totv);
  cout << setw(4) << limw;
  capi = 0; vali = 0;
  for(i=0;i<n;i++)
  {
	  capi += obj[opts[i]].peso;
	  vali += obj[opts[i]].valor;
  }
  for(i=0;i<n;i++)
    objetos[i]=' ';

  for(i=0;i<n;i++)
    if(opts[i]>=0 && opts[i]<n)
      objetos[opts[i]]='*';
  for(i=0;i<n;i++)
    cout << setw(3) << objetos[i];

  cout << "\t" << capi << "\t" << vali << endl;
  w1 += w2;
 }
 while (w1<=w3);
}

void intentar(int i,int tw,int av)
{
 int av1;
 int l;
 static int j;

  if ((tw+obj[i].peso) <= limw)
  {
   s[j++]=i; /* se prueba a incluir el objeto i */
   if (i<n)
    intentar(i+1,tw+obj[i].peso,av);
   else
    if (av>maxv)
    {
     maxv=av;
     for(l=0;l<j;l++)
       opts[l]=s[l];
    }
   s[--j]=-1;
  }
  av1=av-obj[i].valor;  /* se prueba a excluir el objeto i */
  if (av1>maxv)
  {
   if (i<n)
    intentar(i+1,tw,av1);
   else
    {
     maxv=av1;
     for(l=0;l<j;l++)
       opts[l]=s[l];
    }
  }
}