Trabalho de Programação de Computadores: Problema da Mochila

PONTIFÍCIA UNIVERSIDADE CATÓLICA DE MINAS GERAIS
Curso de Engenharia Mecânica (Ênfase em Mecatrônica)

Trabalho de Programação II
Resolução e comparação do problemas da mochila
Belo Horizonte
Outubro de 2014
Primeiro Algoritmo: Força Bruta
#include <stdio.h>
#include <math.h>
#include <time.h>
//Limite de itens na mochila: 12 int mat[12], iteracoes=0; //Variaveis globais int dec2bin(int n) { /* A função converte um número decimal para binário. Como as soluções são somente em 0 e 1, isso vai calcular cada Possibilidade. n: Numero em decimal Retorna o tamanho do número binário */ int div, i=0; while (n>0) { div = n%2; mat[i]=div; i++; n/=2; } return i;
}
main() { int num, ganho[12], peso[12], peso_max, ganho_ant=0, peso_sol=0, mat_sol[12]; int i, k, p; printf("Qual a quantidade de itens? "); //Quantos itens serão considerados scanf("%d",&num); printf("Qual o peso maximo? "); //Peso máximo da mochila scanf("%d",&peso_max); printf("\n"); for (i=0;i<num;i++) { //O valor de cada item printf("Qual o ganho do item (%d)? ",i); scanf("%d",&ganho[i]); } clock_t ini = clock(); printf("\n"); for (i=0;i<num;i++) { // O peso de cada item printf("Qual o peso do item (%d)? ",i); scanf("%d",&peso[i]); } p = pow(2,num); //Numero de possibilidades: 2^n for (k=0;k<p;k++) { int i, s, ps=0, gn=0; s = dec2bin(k); //Converte nosso numero para binario if (s<num) { //Redimensionando o tamanho do numero decimal, se necessario for (i=s+1;i<num;i++) { //Preenchendo o resto com zeros mat[i]=0; } } for (i=0;i<num;i++) { ps+=peso[i]*mat[num-1-i]; } //Soma os pesos for (i=0;i<num;i++) { gn+=ganho[i]*mat[num-1-i]; } //Soma os ganhos if