Backpack Algorithm - Exhaustion Resolution(Tentativa e Erro)

/************************************************
CENTRO FEDERAL DE EDUCAÇÃO TECNOLÓGICA DE MINAS GERAIS (CEFET-MG)
LAED1 - Trabalho Pratico 1
Aluno: Ana Maria M. Brito
Matricula: 201622040414
Descricao do programa: Algoritmo de tentativa e erro que encontra a solução da mochila por exaustão através de uma sequência binária
Data: 19/04/2018
************************************************/

/************************************************

FEDERAL CENTER FOR TECHNOLOGICAL EDUCATION OF MINAS GERAIS (CEFET-MG)
LAED1 - Practical Work 1
Student: Ana Maria M. Brito
Enrollment: 201622040414
Program description: Trial and error algorithm that finds the solution of the rucksack by exhaustion through a binary sequence
Date: 04/19/2018
************************************************ /

#include <stdio.h>
#include <string.h>
#include <sys/time.h>
#include <unistd.h>
#include <sys/resource.h>
#include <math.h>


typedef struct ITEM{

    int peso;
    int valor;
    int posicao;

}item;

item mochila[100];
int valorMochila = 0;
unsigned int mochilaBin[64000];
unsigned int vBin[64000];
int tam;
int capacidade;


void escreveArquivo(int);

void binarioREC(int indice, item* vProd){

   /*
    PARTE I: Criação do vetor binário
   */

    int i, controle, binario, decimal, resto;
    decimal = indice;

    for(i=0, binario=0; decimal>0;  decimal=decimal/2,i++){ //converte um número decimal em binário //
        resto=decimal%2;
        vBin[i] = resto;
    }

    for(;i<tam;i++) //zera as outras posições do vBin que não estão sendo utilizadas
    vBin[i]=0;

    /*
    PARTE II: Combinação entre o vBin e o vProd para testar cada possibilidade
    */

    int limite = pow(2, tam);
    int somaValor = 0, somaPeso = 0, j;

    //printf("Indice %d\n", indice);

    if(indice <= limite){ //enquanto o indice for menor que o limite de combinações

        for(i=0;i<tam;i++){ //segundo a combinação do vBin é feita a soma dos valores dos respectivos produtos
            if(vBin[i] == 1){
            somaValor +=  vProd[i].valor;
            somaPeso  +=  vProd[i].peso;
            }
        }

        if((somaValor > valorMochila) && (somaPeso <= capacidade)){ //se valor da combinação atual é maior q valorMochila,
            valorMochila = somaValor;                               // e somaPeso obedece a capacidade, temos o valor ótimo
            for(i=0;i<tam;i++)
            mochilaBin[i] = vBin[i];
        }

        indice++;
        binarioREC(indice, vProd);
    }

    else{ //condição de parada para salvar no arquivo o vetor solução
        for(i=0, j=0;i<tam;i++){
            if(mochilaBin[i] == 1){
                mochila[j].peso    = vProd[i].peso;
                mochila[j].valor   = vProd[i].valor;
                mochila[j].posicao = vProd[i].posicao;
                j++;
                escreveArquivo(j);
            }
        }
    }
}

void escreveArquivo(int tamanho){ //escreve o vetor solução no arquivo "resultadosTentativaErro.txt"

    int i;
    int pesoMochila = 0;
    FILE *arquivo;

    arquivo = fopen("resultadoTentativaErro.txt", "w");

    fprintf(arquivo,"Mochila - posição/peso/valor:\n");
    for(i=0;i<tamanho;i++){
        fprintf(arquivo,"%d %d %d\n", mochila[i].posicao, mochila[i].peso, mochila[i].valor);
    }


    fprintf(arquivo,"\nSomatório dos pesos dos itens escolhidos:\n");
    for(i=0;i<tamanho;i++){
        fprintf(arquivo,"%d", mochila[i].peso);
        if((i+1) < tamanho)
        fprintf(arquivo," + ");
        pesoMochila += mochila[i].peso;
    }
    fprintf(arquivo, " = %d\n", pesoMochila);

    fprintf(arquivo,"\nSomatório dos valores dos itens escolhidos:\n");
    for(i=0;i<tamanho;i++){
        fprintf(arquivo,"%d", mochila[i].valor);
        if((i+1) < tamanho)
        fprintf(arquivo," + ");
    }
    fprintf(arquivo, " = %d\n", valorMochila);

    fclose(arquivo);

}

int main(int argc, char*argv[]) {


    struct rusage usage;
    struct timeval now, start, end;
    double inicio, fim;


    getrusage (RUSAGE_SELF, &usage);
    start = usage.ru_utime;

    gettimeofday(&now,NULL);
    inicio = ((double) now.tv_usec)/1000000;
    inicio += ((double) now.tv_sec);


    FILE *arquivo;

    //Abrir arquivo
    arquivo = fopen("arquivo.txt","r");
    if (arquivo==NULL){
        printf("Impossivel abrir o arquivo\n");
        return 1;
    }

    //Lê do arquivo e grava no vetor

    item vProd[100];

    fscanf(arquivo, "%d\n%d", &capacidade, &tam);

    int i;

    //carrega os produtos do arquivos no vetor struct produto

    for (i=0;i<tam;i++){
        fscanf(arquivo, "%d %d\n", &vProd[i].peso, &vProd[i].valor);
        vProd[i].posicao = i;
    }

    fclose(arquivo);

    int indice = 1;
    binarioREC(indice, vProd);

    gettimeofday(&now,NULL);
    fim = ((double) now.tv_usec)/1000000 ;
    fim += ((double) now.tv_sec);

    getrusage(RUSAGE_SELF, &usage);
    end = usage.ru_utime;

    printf("Tempos gastos no algoritmo TENTATIVA ERRO: \n");
    printf("Tempo de computação: %.4f \n", fim - inicio);
    printf("Tempos de entrada e saída: %ld.%lds\n",  end.tv_sec-start.tv_sec,  end.tv_usec-start.tv_usec);

    return 0;

}