glouton.c

以贪吃为基础算法解决背包问题

/*** Algorithme Glouton ***/


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

/*** Table p(price) and Table w(weight) ***/
/*** m is the number of total weights         ***/
/*** n is the numberof total objets          ***/
/*** x is the resultat					   ***/
/*** s is the total prix in the bag       ***/

float knapSack(float* p, float* w, int* x ,float m, int n) {
    int i = 0;
    float s = 0;
    for (i = 0; i < n; i++) x[i] = 0;	
    i = 0;
	/*** to choose the objects to put in the bag ***/
    while (i < n && w[i] <= m) {
        m -= w[i];
        s += p[i];
        x[i] = 1;
        i++;
    }
	
	/*** use the function when w[i] > m and m > 0, because maybe there is certain object can still put in the bag ***/
    	i++;
	while (i < n && m >= 0)
	{
		if (w[i] <= m)
		{
			m -= w[i];
			s += p[i];
			x[i] = 1;
			i++;
		}else { 
			i++;
		}
	}
    printf("\n########################################\n");
    printf("reste weights are:  %d\n",(int)m);
    return s;
};

int main(int argc, char** argv) {
    float m = 0, s = 0; 
    float temp = 0;
    float *p, *w;
    int *x;
    int n = 0, i = 0, flag = 1;
	FILE * f;
	printf("|-----------Algo glouton------------|\n");
	printf("|-----------------------------------|\n");
    f = fopen(argv[1],"r");
	if(f == NULL) {
		printf("The file does not exist!\n");
		return 0;
	}

	fscanf(f, "%d", &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, "%f", &m);
	for (i = 0; i < n; i++)
    {
		fscanf(f, "%f", &w[i]);
    }
	fclose(f);

	/*** in the table p and w, the values are arranged p[i]/w[i] by decroissant order ***/
	while (flag != 0) {
        flag = 0;
        for (i = 0; i < n-1; i++) {
            //if (p[i]/w[i] < p[i+1]/w[i+1]) 	{
             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 = knapSack(p,w,x,m,n);
    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;
}