recuit.c

使用退火方法解决0-1规划背包问题

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

/**
 * initialisation (Algorithme Glouton)
 */
float init(float* p, float* w, int* x ,int m, int n) {
    int i = 0;
    float s = 0;
    for (i = 0; i < n; i++) x[i] = 0;	
    i = 0;
    while (i < n && w[i] < m) {
        m -= (int)w[i];
        s += (int)p[i];
        x[i] = 1;
        i++;
    }
    while (i < n && m > 0) {
	i++;
	if (i < n && w[i] < m) {
		m -= (int)w[i];
		s += (int)p[i];
		x[i] = 1;
		i++;
	}
    }
    return s;
};

int main(int argc, char** argv) {
    int m = 0; 
    int Rami = 0, Ramj = 0;
    int n = 0, i = 0, flag = 1;
    int *x;
    int loop; // pour chaque T, on peut iteration combien de fois
    float s = 0;
    float temp = 0;
    float *p, *w;
    float dp, dw;
    float t0 = 500;
    float t = t0;
    float tf = 0.95;
    float e = 0.00001;
    float Wsac = 0;
    
    FILE * f;
    printf("|-----------Algo Local search(recuit)------------|\n");
    printf("|-----------------------------------|\n");
    f = fopen(argv[1],"r");
    if(f == NULL) {
	printf("Le fichier n'existe pas !\n");
	return 0;
    }
    fscanf(f, "%d", &n);
    loop = 100*n;
    p = (float*)malloc(n*sizeof(float));
    w = (float*)malloc(n*sizeof(float));
    for (i = 0; i < n; i++) {
	fscanf(f, "%f", &p[i]);
    }
    fscanf(f, "%d", &m);
    for (i = 0; i < n; i++) {
	fscanf(f, "%f", &w[i]);
    }
    
    fclose(f);
	
	/**
	 * we range those valeurs p[i]/w[i] (ordre decroissant)
	 */
    while (flag != 0) {
    flag = 0;
    	for (i = 0; i < n-1; i++) {
    		if (w[i]/p[i] > w[i+1]/p[i+1]) {
		temp = p[i];
        	p[i] = p[i+1];
        	p[i+1] = temp;
        	temp = w[i];
        	w[i] = w[i+1];
        	w[i+1] = temp;
        	flag = 1;
            	}
        }
    }
    
    x = (int*)malloc(n*sizeof(int));
    s = init(p,w,x,m,n);
    for(i = 0; i < n; i++) {
        if(x[i] > 0) {
            Wsac += w[i];
        }
    }

    /**
     * methode recuit
     */
    while(t>e) {
    srand((unsigned)time(NULL));
    for(int k=1;k<=loop;k++){
            Rami = rand()%n;
            if(x[Rami] == 0){
              if((int)(Wsac+w[Rami])<=m){
                          x[Rami] = 1;
                          s += p[Rami];
                          Wsac += w[Rami];            
                          } else {
				 Ramj = rand()%n;
                                 while( x[Ramj]==0 ){
					Ramj = rand()%n;
                                        }
                                dp = p[Rami] - p[Ramj];
                                dw = w[Rami] - w[Ramj];
                                if((int)(Wsac+dw)<=m){
                                   if(dp>0 | (dp/t)>0.1) {
                                            x[Rami] = 1;
                                            x[Ramj] = 0;
					    s += dp;
					    Wsac += dw;
                                            }
                                               }
                                 } 
                          } else {
                                 Ramj = rand()%n;
                                 while(x[Ramj] == 1){
				      Ramj = rand()%n;
                                 }
                                dp = p[Ramj] - p[Rami];
                                dw = w[Ramj] - w[Rami];
                                if((int)(Wsac+dw)<=m){
                                   if(dp>0 | (dp/t)>0.1) {
                                            x[Rami] = 0;
                                            x[Ramj] = 1;
					    s += dp;
					    Wsac += dw;
                                            }
                                               }
                                 }
            } 
    t = t*tf;          
    }
    printf("the max value is %d\n",(int)s);
    printf("########################################\n\n\n");
    printf("We select those Objects are :\n");
    for(i = 0; i < n; i++) {
        if(x[i] > 0) {
            printf("     the p:  %d",(int)p[i]);
            printf("     the w:  %d\n",(int)w[i]);
        }
    }
    return 0;
}