Funçao para Best Fit

[WolfmanZ]

Boas estou a fazer em c os algoritmos de best/worst/first fit mas nao estou a conseguir por o best fit a funcionar?

a funçao recebe dois vectores um vector v de tamanho N que recebe blocos de memoria a alocar e outro vector c de tamanho M com os blocos de memoria disponiveis.

A funçao retorna o numero de operaçoes (memoria alocada) que o best fit consegue fazer!

Ex: v[4] = { 212, 417, 112, 417}

c[5] = {100, 500, 200, 300,600}

Best Fit | 100 | 500 | 200 | 300 | 600

212 100| 500|200|88|600

417 100|83|200|88|600

112 100|83|88|88|600

426 100|83|88|88|174

numero a retornar 4!

int BestF(int v[],int c[],int N, int M){ // v == memoria  c== blocos de memoria disponivel
int b=0,i,j, pos,aux,aux2,n[M];
for(j=0;j<M;j++){
			 n[j]=c[j];				
}


for(i=0;i<N;i++){
for(j=0;j<M;j++){
 if(v[i]<=n[j]){
		aux=n[j];
		pos=j;		  
  }
}
n[pos]=n[pos]-v[i];
if(n[pos]>=0){
b++;
}
}
return b;
}

problema a funçao em vez de ir ao menor elemento de c que consegue alocar memoria vai para o maior .

Edited June 3, 2012 at 10:08 PM by pmg
LP adicionada ao GeSHi

[pmg]

Ve la bem o que estes ciclos fazem

for(i=0;i<N;i++){
for(j=0;j<M;j++){
 if(v[i]<=n[j]){
                       aux=n[j];
                       pos=j;           
  }
}

Quando os ciclos comecam a primeira comparacao, com o exemplo que tu deste, é entre 212 e 100; depois 212 e 500 (que "funciona"), depois 212 e 200, 212 e 300, 212 e 600 (que "funciona" outra vez).

Neste caso, entre os dois que "funcionam" queres escolher o primeiro e por isso detectaste o erro ... mas noutra situacao podera ter de ser escolhido outro qualquer. Tens de arranjar maneira de escolher o mais pequeno.

[WolfmanZ]

Ve la bem o que estes ciclos fazem

for(i=0;i<N;i++){
for(j=0;j<M;j++){
 if(v[i]<=n[j]){
					aux=n[j];
					pos=j;		  
  }
}

Quando os ciclos comecam a primeira comparacao, com o exemplo que tu deste, é entre 212 e 100; depois 212 e 500 (que "funciona"), depois 212 e 200, 212 e 300 (tambem funciona), 212 e 600 (que "funciona" outra vez).

Neste caso, entre os dois que "funcionam" queres escolher o primeiro e por isso detectaste o erro ... mas noutra situacao podera ter de ser escolhido outro qualquer. Tens de arranjar maneira de escolher o mais pequeno.

sim mas o pequeno emendo sao 3 os casos, o mais baixo é o 300 pois é isso que nao tou a conseguir fazer!

if(v<=n[j]){
				    aux=n[j];
				    pos=j;		 
  }

falta aqui essa parte por que tenho de guardar a posiçao do menor e com o auxiliar comparar com os outros valores do vector!

Edited June 4, 2012 at 02:27 AM by WolfmanZ

[pmg]

Ah! pois ... 212 e 300 também funciona.

O que tens que fazer é verificar e guardar a menor diferença positiva.

/* CODIGO NAO TESTADO */
pos = -1;
int mindiferenca = INT_MAX;
for (i = 0; i < N; i++) {
   for (j = 0; j < N; j++) {
       int diferenca = n[j] - v[i];
       if ((diferenca >= 0) && (diferenca < mindiferenca)) {
           mindiferenca = diferenca;
           pos = j;
       }
   }
}
if (pos == -1) /* erro: impossivel encontrar bloco com tamanho suficiente */;

[WolfmanZ]

como declaras o INT_MAX ou vem com alguma biblioteca??

[Baderous]

O INT_MAX está definido através do <limits.h>.