Uma Solução Diferente para o Problema da Mochila Binária (Resolvido em 2 horas)

Dada uma mochila de tamanho M e N itens com peso P ={P1, P2...Pn} e Valores V = {V1, V2...Vn}, encontre um vetor de X elementos contidos e não contidos na mochila, onde P.X <= M e V.X é o valor máximo possível.

Programa Mochila {

//itens possuem o mesmo índice para pesos e valores e possui índices e zeros no início.

Int M = 11; 

Int itens[][2] = {{0,0},{1,0},{ 2,0},{3,0}} ; 

int pesos[] = {1, 2, 4, 8}; 

double valores[] = {10, 30, 41, 80}

;

int itens[][] = ObtemItensdaMochila(M, itens, pesos, valores);

Para i=0 até itens[0].tamanho-1 faça

            Para j=0 até itens[1].tamanho-1 faça

                Imprima itens[i][j]; //Imprime índice  + “0” ou “1”

            Fim-Para

Fim-Para

int[][] ObtemItensdaMochila (int M, int[] itens, int[] pesos, double[] valores);

//Coluna 0 – Peso, Coluna 1 – Valores

double mochila[][] = itens.tamanho, 2;

//Atribui valores iniciais

mochila[0,0] = pesos[pesos.tamanho-1]; mochila[0,1] = valores[valores.tamanho-1];

//Coluna 0 – Peso, Coluna 1 – Valores

double mochilaItens[][] = itens.tamanho, 2;

mochilaItens[0,0] = mochila[0,0]; mochilaItens[0,1] = mochila[0,1];

int elemento = 0; int j = 0;

Para i=itens[0].tamanho-2 <=0 faça {

 Se (pesoAtual(mochila) + pesos[i] <= M)

        elemento  = elemento+1;

                      mochila[elemento,0] = pesos[i];

                      mochila[elemento,1] = valores[i];

                       Se (valorAtual(mochila) > mochilaItens[j,1])

                               j = j+1;

                               mochilaItens[j,0] = mochila[elemento,0] + mochilaItens[j,0];

                               mochilaItens[j,1] = mochila[elemento,1] + mochilaItens[j,1];

itens[i,1] = 1;

                    Fim-Se

               Senão

                     elemento = elemento-1;

                Fim-Se

 Fim-Para

retorne itens;}

//verifica peso atual da mochila

int pesoAtual(double mochila[][]){

int peso = 0;

Para i=0 até mochila[0].tamanho-1 faça

peso = peso + mochila[i,0];

retorne peso; }

//verifica valor atual da mochila

double valorAtual(double mochila[][]){

double valor = 0;

Para i=0 até mochila[1].tamanho-1 faça

                valor = valor + mochila[i,1];

retorne valor;}

Follow @jaguaracisilva