SHARE
TWEET

Untitled

NaFer May 25th, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #define INF 1000000
  3.  
  4. using namespace std;
  5.  
  6. int voa, bAct, it, m, n, aumento;
  7.  
  8. int* sol;
  9. int* soa;
  10. int* itAnterior;
  11. int* mejorasAnteriores;
  12. int** poblacion;
  13.  
  14. bool solucion(int nivel){
  15.     return nivel<=m;
  16. }
  17.  
  18. bool criterio(int nivel){
  19.     return (nivel<m) && (n-it)>=(m-nivel);
  20. }
  21.  
  22. bool masHermanos(int nivel){
  23.     return sol[nivel]<=m;
  24. }
  25.  
  26. void retroceder(int nivel){
  27.     sol[nivel]=0;
  28.     nivel--;
  29.     it=itAnterior[nivel];
  30.     aumento=mejorasAnteriores[nivel];
  31. }
  32.  
  33. int mejora(int nivel){
  34.     int cantidad = 0;
  35.     for(int i=i; i<nivel; i++){
  36.         cantidad += poblacion[sol[i]-1][it-1];
  37.         cantidad += poblacion[it-1][sol[i]-1];
  38.     }
  39.     return cantidad;
  40. }
  41.  
  42. void generar(int nivel){
  43.     it++;
  44.     bAct-=aumento;
  45.     sol[nivel]=it;
  46.     aumento=mejora(nivel);
  47.     bAct-=aumento;
  48. }
  49.  
  50. void inicializar_arrays(){
  51.     for(int i=0; i<(m+1); i++){
  52.         sol[i]=0;
  53.         soa[i]=0;
  54.         mejorasAnteriores[i]=0;
  55.         itAnterior[i]=0;
  56.     }
  57. }
  58.  
  59. int backtracking(){
  60.     int nivel = 1;
  61.     voa = -INF;
  62.     bAct = it = aumento = 0;
  63.     inicializar_arrays();
  64.     do{
  65.         generar(nivel);
  66.         if(solucion(nivel) && bAct>voa){
  67.             voa = bAct;
  68.             soa = sol;
  69.         } else if(criterio(nivel)){
  70.             mejorasAnteriores[nivel]=bAct;
  71.             itAnterior[nivel] = it;
  72.             nivel++;
  73.             aumento=0;
  74.         } else {
  75.             while(!masHermanos(nivel)) retroceder(nivel);
  76.         }
  77.     } while(nivel==0);
  78.  
  79.     return voa;
  80. }
  81.  
  82. void leerMatriz(){
  83.     int k;
  84.     for(int i = 0; i<n; i++){
  85.         for(int j = 0; j<n; j++){
  86.             cin >> k;
  87.             poblacion[i][j] = k;
  88.         }
  89.     }
  90. }
  91.  
  92. int main(int argc, char const *argv[]){
  93.  
  94.     int ncasos;
  95.     cin >> ncasos;
  96.     for(int k=0; k<ncasos; k++){
  97.         cin >> n >> m;
  98.         sol = new int[m+1];
  99.         soa = new int[m+1];
  100.         itAnterior = new int[m+1];
  101.         mejorasAnteriores = new int[m+1];
  102.         poblacion = new int*[n];
  103.         for(int i=0; i<n; i++){
  104.             poblacion[i]=new int[n];
  105.         }
  106.  
  107.         leerMatriz();
  108.  
  109.         cout << backtracking() << "\n";
  110.  
  111.  
  112.     }
  113.  
  114. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top