A ver si me podéis aportar alguna idea sobre cómo afrontar esto:
Resúmen del problema...

Con lo cuál tengo 2 tablas tal que así:

El beneficio del que se habla se genera de la siguiente forma:

amistad[i][j]+amistad[j][i])*(trabajo[i][j]+trabajo[j][i]

Tengo que seguir obligatoriamente un esquema de backtracking iterativo ( y es lo que me está matando )...
Llevo más o menos el siguiente esqueleto:
** Intento plantearme esto como un árbol permutacional sin repetición **

			do{
				genera(nivel,sol);
 
				if(solucion(sol,nalum)){
					/* Sumar beneficios  y actualizar voa/soa */
 
				}
 
 
				if(criterio(nivel,sol,nalum)==true){
					nivel++;
				}else {
					while((masHermanos(nivel,nalum)==false) && (nivel>0)) {
						retroceder(nivel,sol);
						nivel --;
					}
				}
 
			}while(nivel!=0);
 

Dónde las funciones:

Genera(nivel,sol) debería generar el siguiente hermano, o el
primero, para el nivel actual.

Criterio (nivel, sol): Debería comprobar si a partir de sol[0-nivel] se puede alcanzar una solución válida. En caso de que no, podar.

MasHermanos (nivel, sol): Devuelve true si hay más hermanos del nodo actual que todavía no han sido generados.

Retrocede(nivel,sol): Retrocede la solucion y hace nivel--
--------------------------------------------------------------

Hasta ahora, todos mis intentos han acabado en un bucle infinito o bien en un falso backtrack, ya que recorría malamente.
¿Podría tratar de hacerlo aprovechando STL algorithm con la función para permutaciones?


A ver si alguien me puede echar un cable, que estoy más perdido que un ciego en el océano.

*Cualquier idea, será bien recibida *

Gracias y perdón por la biblia.

Um, es más o menos lo que llevo intentando todo el tiempo, reducir el problema primero a las permutas y/o parejas para luego maximizar, pero no había pensando en un planteamiento recursivo inicial y como dices, el planteamiento iterativo es la muerte a pellizcos. Me pondré a ello, a ver si saco algo en claro.

Para los curiosos, os dejo la funcion de backtrack ya resuelta.

void backtrack(int nalum){
	int voa = -1; /* valor optimo actual */
	int *soa; /* Solucion optima actual */
	int temp = 0;
	soa = new int[MAX+1];
	nivel = 1; /* Inicializa el nivel */
	hermanos[1] = nalum; /* Ramas */
 
	do {
		generar(nalum);
		if (solucion(nalum)) {
			temp = beneficio(nalum);
			if (temp > voa) { /* Actualizamos el valor optimo y la solucion optima */
				voa = temp;
				for (int i = 1; i<=nalum; i++) soa[i] = sol[i]; 
			}
		}
 
		if (criterio(nalum)) nivel++;
		else while((!masHermanos()) && (nivel > 0)) retroceso();
 
 
	} while (nivel!=0);
 
	cout<< voa << endl;
	for (int i=1; i<nalum; i++)
		cout << soa[i]-1 << " ";					
 
	cout << soa[nalum]-1<< endl;	
 
 
	delete [] soa;
}
 

* Generar(): Obtiene permutaciones posibles según el nº de alumnos.

Saludos y gracias por la ayuda.