// === esercizio 3 del 18/9/06

typedef struct {
  int peso;       // peso del gruppo
  int valore;     // valore del gruppo
  char *membri;   // array booleano che indica chi e' presente
} gruppo;

void ladroric(int *v, int *p, int k, int V, int da_mettere, 
              gruppo *corr, gruppo *best, int next);


void LadroPigro(int *v, int *p, int k, int V)
{
  gruppo corrente;   // gruppo corrente
  gruppo migliore;   // miglior gruppo trovato
  int maxgruppo;     // dimensione massima di un gruppo (5 o k)

  maxgruppo = 5;    // mettere k per la seconda parte dell'esercizio
  corrente.membri = (char *) calloc(k,sizeof(char)); // sono inizializzati a 0
  migliore.membri = (char *) calloc(k,sizeof(char)); // sono inizializzati a 0
  if( corrente.membri == NULL ||  migliore.membri == NULL)
    exit(1);  
  // inizializzo il gruppo corrente all'insieme vuoto
  corrente.peso=corrente.valore=0;
  // inizializzo migliore con il peso + infinito
  migliore.valore = 0;  // questo valore in realta' non interessa
  migliore.peso = INT_MAX;

  ladroric(v,p,k,V,maxgruppo,&corrente,&migliore,0);
  if(migliore.peso<INT_MAX)
    stampa_sol();
  else no_sol();
  free(corrente.membri); 
  free(migliore.membri);
}


void ladroric(int *v, int *p, int k, int V, int da_mettere, 
              gruppo *corr, gruppo *best, int next)
{
  if(next==k) 
    return;  // nessun oggetto da inserire
  // ora provo a includere next (se non supera il peso)
  if(corr->peso+p[next]< best->peso) {
    // aggiunge oggetto next
    corr->peso+=p[next];
    corr->valore+=v[next];
    corr->membri[next]=1;
    if(corr->valore>=V) { // questa soluzione e' migliore di best
      int i;
      best->peso=corr->peso;
      best->valore=corr->valore;
      for(i=0;i<k;i++)
	best->membri[i] = corr->membri[i];
    }
    else { // sono sotto V: provo a estendere la soluzione
      if(da_mettere>1) {
	ladroric(v,p,k,V,da_mettere-1,corr,best,next+1);
      }
    }
    // elimino oggetto next
    corr->peso-=p[next];
    corr->valore-=v[next];
    corr->membri[next]=0;
  }
  // ora procedo senza includere next
  ladroric(v,p,k,V,da_mettere-1,corr,best,next+1);
  return;
}