L08 E02 Dinamic Programmation

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define FILESRC "sequenza.txt"

typedef struct soluzione{
    int nscambi;
    int *indici;
}sol;

void leggiSequenze(int **seq, int *dim);
void seq_frecceDP(int *seq, int dim);
void contaScambi(int i, int j, int *seq, sol *sol);
void stampaSol(sol *sol, int *seq, int dim);

int main()
{
    int *seq, dim=0;
    leggiSequenze(&seq,&dim);
    for(int i=0;i<dim;i++)
        printf("%d ",seq[i]);
    printf("\n\n");
    seq_frecceDP(seq,dim);

    return 0;
}

void leggiSequenze(int **seq, int *dim){
    FILE *fsrc;
    int i;

    fsrc=fopen(FILESRC,"r");
    if(fsrc==NULL){
        printf("Errore apertura file...\n");
        exit(-1);
    }
    fscanf(fsrc," %d",dim);
    *seq=(int*)malloc(*dim*sizeof(int));
    for(i=0;i<*dim;i++){
        fscanf(fsrc," %d",*seq+i);
    }
    return;
}

void seq_frecceDP(int *seq, int dim){
    int i=0,j=dim-1; //estremi sx e dx del vettore di frecce considerato
    int c, k, a;//iterazione
    sol tmp_sol, sol_finale, sol_stampa;

    tmp_sol.indici=(int*)malloc(dim*sizeof(int));
    sol_finale.indici=(int*)malloc(dim*sizeof(int));
    sol_stampa.indici=(int*)malloc(dim*sizeof(int));
    tmp_sol.nscambi=0;
    sol_finale.nscambi=0;
    sol_stampa.nscambi=0;

    while(i<=j){//poi sarà solo <

        sol_finale.nscambi=INT_MAX;
        for(c=i+1;c<=j;c=c+2){
            tmp_sol.nscambi=0;
            //conto scambi necessari su intervallo (i,c), con c variabile nel tempo
            contaScambi(i,c,seq,&tmp_sol);

            //salvo la soluzione migliore corrente
            if(tmp_sol.nscambi<=sol_finale.nscambi){
                sol_finale.nscambi=tmp_sol.nscambi;
                for(a=0;a<sol_finale.nscambi;a++){
                    sol_finale.indici[a]=tmp_sol.indici[a];
                }
                k=c+1;//salvo l'indice dx della sotto soluzione migliore
            }
        }

        for(a=sol_stampa.nscambi;
            a<sol_finale.nscambi+sol_stampa.nscambi; //mi sposto di un delta=sol_finale.nscambi
            a++){
                //accodo gli indici di scambio
                sol_stampa.indici[a]=sol_finale.indici[a-sol_stampa.nscambi];//a-sol_stampa.nscambi: parto dall'indice 0
            }
        sol_stampa.nscambi=sol_stampa.nscambi+sol_finale.nscambi;


        i=k;//riparto dall'indice dx della sotto sol. migliore
    }

    //stampo
    stampaSol(&sol_stampa,seq,dim);

    //libero la memoria
    free(sol_finale.indici);
    free(tmp_sol.indici);
    free(sol_stampa.indici);
    return;
}

void contaScambi(int i, int j, int *seq, sol *sol){
    int conta0=0, conta1=0;
    int start, init=i;

    for(;i<=j;i++){
        if(!seq[i]){
            //limite:
            if(conta0>(j-init)/2){
                //ho troppi zeri, registro gli scambi con 1
                sol->nscambi++;
                sol->indici[sol->nscambi-1]=i;
                conta1++;
            }
            else
                conta0++;
        }
        else{
            if(conta0==0){
                //non posso iniziare uno sconto con un 1
                sol->nscambi++;
                sol->indici[sol->nscambi-1]=i;
                conta0++;
            }
            else{
                //verifico che ci siano tanti 1 quanti sono gli zeri appena contati
                for(start=i;i<start+conta0 && i<=j;i++){
                    if(seq[i]==0){
                        //scambio
                        sol->nscambi++;
                        sol->indici[sol->nscambi-1]=i;
                    }
                    conta1++;
                }
                i--;
            }
            //ho passato uno scontro equilibrato
            if(conta0==conta1){
                conta0=conta1=0;
                init=i+1;
            }
        }
    }
    return;
}

void stampaSol(sol *sol, int *seq, int dim){
    int i, j=0;
    for(i=0;i<dim;i++){
        if(i==sol->indici[j]){
            printf("%d ",!seq[i]);
            j++;
        }
        else
            printf("%d ", seq[i]);
    }
    printf("\nGli scambi effettuati sono: %d\n",sol->nscambi);
    printf("Indici modificati:\n");
    for(i=0;i<sol->nscambi;i++){
        printf("%d ",sol->indici[i]);
    }
    return;
}