gelöscht

[nwp2]

Hatte noch etwas Langeweile.

struct RSPinstance{
	int C; /* Capacity */
	int *w; /* weight */
	int *p; /* profit */
	int n; /* number of elements */
	char *x; /* solution, 0 = dont pack, 1 = pack, 2 = dont know yet */
};

Struktur geändert und x hinzugefügt. Bin mir aber nicht sicher ob das so gedacht ist.

struct RSPinstance *RSPinstanceCopy(struct RSPinstance *RSPI){
	/* copy the RSP-Instance */
	struct RSPinstance *newRSPI = malloc(sizeof *newRSPI);
	int i;
	newRSPI->C = RSPI->C;
	newRSPI->n = RSPI->n;
	newRSPI->x = malloc(sizeof *newRSPI->x * newRSPI->n);
	newRSPI->p = malloc(sizeof *newRSPI->p * newRSPI->n);
	newRSPI->w = malloc(sizeof *newRSPI->w * newRSPI->n);
	if (!(newRSPI->x && newRSPI->p && newRSPI->w)){
		free(newRSPI->x);
		free(newRSPI->p);
		free(newRSPI->w);
		return 0;
	}
	for (i = 0; i < RSPI->n; i++){
		newRSPI->p[i] = RSPI->p[i];
		newRSPI->w[i] = RSPI->w[i];
		newRSPI->x[i] = RSPI->x[i];
	}
	return newRSPI;
}

Braucht man nicht für die Aufgabe, wird aber für Preprocessing benötigt. Man kann es auch reinkopieren und optimieren, wenn man die Funktion sonst nirgends gebrauchen kann.

struct RSPinstance *Preprocessing(struct RSPinstance *RSPI){
	/* simplify an RSP-instance */
	/* TODO: Join all cases into a single for loop */
	struct RSPinstance *newRSPI = RSPinstanceCopy(RSPI);
	int j;
	/* 1. Falls n <= 0, Abbruch! (Instanz nicht sinnvoll definiert) */
	if (newRSPI->n <= 0){
		free(newRSPI);
		return 0;
	}
	/* 2. Für alle j element J0 := {j element [n] | pj <= 0, wj <= 0}: Fixiere x*j = 0
			(Solche Objekte würden ohnehin nie eingepackt werden, da sie gleichzeitig die Kapazität verringern und den
			Zielfunktionswert verschlechtern) */
	for (j = 0; j < newRSPI->n; j++)
		if (RSPI->p[j] <= 0 && RSPI->w[j] >= 0)
			RSPI->x[j] = 0;
	/* 3. Für alle j element J1 := {j element [n] | pj >= 0, wj <= 0}: Fixiere x*j = 1
			(Solche Objekte können immer nutzenbringend eingepackt werden) */
	for (j = 0; j < newRSPI->n; j++)
		if (RSPI->p[j] >= 0 && RSPI->w[j] <= 0)
			RSPI->x[j] = 1;
	/* 4. TODO */
	/* 5. TODO */
	/* 6. Filter out object that are bigger than the capacity */
	/* TODO: Check if that is sufficient for 6. (probably not) */
	for (j = 0; j < newRSPI->n; j++)
		if (RSPI->w[j] > RSPI->C)
			RSPI->x[j] = 0;
	/* 7. TODO */
	return newRSPI;
}

Ein Teil der Preprocessing-Funktion. 4. bis 7. verstehe ich nicht wirklich, bin auch zu faul. Sollte aber für dich nicht schwer sein den Rest hinzuzufügen.

struct RSPinstance *ReadData(FILE *instancefile){
	/* open file */
	struct RSPinstance *instance;
	int i;
	if (!instancefile){
		fprintf(stderr, "Failed opening file\n");
		return 0;
	}
	/* fill instance */
	instance = malloc(sizeof *instance);
	if (!instance){
		fprintf(stderr, "Out of memory\n");
		fclose(instancefile);
		return 0;
	}
	if (fscanf(instancefile, "%d", &instance->C) != 1){
		fprintf(stderr, "Wrong instance format in parameter C\n");
		free(instance);
		fclose(instancefile);
		return 0;
	}
	if (fscanf(instancefile, "%d", &instance->n) != 1){
		fprintf(stderr, "Wrong instance format in paramenter n\n");
		free(instance);
		fclose(instancefile);
		return 0;
	}
	if (instance->n <= 0){
		fprintf(stderr, "Wrong instance format in paramenter n must not be <= 0\n");
		free(instance);
		fclose(instancefile);
		return 0;
	}
	instance->w = malloc(sizeof *instance->w * instance->n);
	instance->p = malloc(sizeof *instance->p * instance->n);
	instance->x = malloc(sizeof *instance->x * instance->n);
	if (!instance->w || !instance->p || !instance->x){
		fprintf(stderr, "Out of memory\n");
		free(instance->w);
		free(instance->p);
		free(instance->x);
		free(instance);
		fclose(instancefile);
		return 0;
	}
	for (i = 0; i < instance->n; i++)
		if (fscanf(instancefile, "%d %d", &instance->w[i], &instance->p[i]) != 2){
			fprintf(stderr, "Wrong instance format in element %d\n", i + 1);
			free(instance->w);
			free(instance->p);
			free(instance);
			fclose(instancefile);
			return 0;
		}
	fclose(instancefile);
	for (i = 0; i < instance->n; i++)
		instance->x[i] = 2; /* we dont know what to pack yet */
	return instance;
}

Bugfix in der alten Zeile 44, da sollte einmal instance->p hin (noob_lolo hat meinen Bug kopiert ). Außerdem wurde x hinzugefügt.

So wie ich das sehe ist Teilaufgabe 1 erfüllt, Teilaufgabe 5 kann man auch leicht erfüllen. Sind schonmal 25 Punkte. Die Preprocessing-Funktion kriegst du bestimmt auch halbwegs zum laufen sodass du ein paar Punkte kriegst.

Teilaufgabe 4 sollte einfach sein, eine Printfunktion ist ja schon da. Musst nur nochmal nachsehen ob auch alles im richtigen Format ausgegeben wird.

Damit sollte es kein Problem sein über 50 Punkte zu kommen, das reicht laut Vorlesungsseite.

Wenn du nach Berlin kommst musst du mir einen ausgeben :p

[noob_lolo]

nwp2 schrieb:

Damit sollte es kein Problem sein über 50 Punkte zu kommen, das reicht laut Vorlesungsseite.

schade das es keine punkte für ästhetik gibt

[nwp2]

Meinst du mein Code würde Ästhetikpunkte kriegen? Es ist malloc drin und kein char buffer[irgendwas]. Da fragt man sich ob das überhaupt C-Code ist

In Preprocessing sollte zwischen Zeile 6 und 7 noch abgefragt werden, ob das Kopieren funktioniert hat, if (!newRSP)return 0; oder so.

[julieann]

Also, nicht dass ihr denkt, ich wäre verschollen

Ich habe an dem Code weitergearbeitet und zeige euch mal, was ich bis jetzt als relativ vollständiges ergebnis der aufgabe habe:

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

typedef struct {
	int C; /* Capacity */  
	int *w; /* weight */  
	int *p; /* profit */  
	int n; /* number of elements */  
	char *x; /* solution, 0 = dont pack, 1 = pack, 2 = dont know yet */  

} RSPinstance; 

RSPinstance *RSPinstanceCopy(RSPinstance *RSPI){  
	/* copy the RSP-Instance */  
	RSPinstance *newRSPI = (RSPinstance*) malloc(sizeof(RSPinstance));  
	int i;  
	newRSPI->C = RSPI->C;  
	newRSPI->n = RSPI->n;  
	newRSPI->x = (char*) malloc(sizeof(char) * newRSPI->n);  
	newRSPI->p = (int*) malloc(sizeof(int) * newRSPI->n);  
	newRSPI->w = (int*) malloc(sizeof(int) * newRSPI->n);  

	for (i = 0; i < RSPI->n; i++){  
		newRSPI->p[i] = RSPI->p[i];  
		newRSPI->w[i] = RSPI->w[i];  
		newRSPI->x[i] = RSPI->x[i];  
	}  
	return newRSPI;  
} 

RSPinstance *ReadData(FILE *instancefile){  
	/* open file */  
	RSPinstance *instance;  
	int i;  

	/* fill instance */  
	instance = malloc(sizeof *instance);  
	if (!instance){  
		fprintf(stderr, "Out of memory\n");  
		fclose(instancefile);  
		return 0;  
	}  
	if (fscanf(instancefile, "%d", &instance->C) != 1){  
		fprintf(stderr, "Wrong instance format in parameter C\n");  
		free(instance);  
		fclose(instancefile);  
		return 0;  
	}  
	if (fscanf(instancefile, "%d", &instance->n) != 1){  
		fprintf(stderr, "Wrong instance format in paramenter n\n");  
		free(instance);  
		fclose(instancefile);  
		return 0;  
	}  
	if (instance->n <= 0){  
		fprintf(stderr, "Wrong instance format in parameter n must not be <= 0\n");  
		free(instance);  
		fclose(instancefile);  
		return 0;  
	}  
	/* allocate memory for the elements of the instance */
	instance->w = (int*) malloc(sizeof(int) * instance->n);  
	instance->p = (int*) malloc(sizeof(int) * instance->n);  
	instance->x = (char*) malloc(sizeof(char) * instance->n);  
	/*if (!instance->w || !instance->p || !instance->x){  
		fprintf(stderr, "Out of memory\n");  
		free(instance->w);  
		free(instance->p);  
		free(instance->x);  
		free(instance);  
		fclose(instancefile);  
		return 0;  
		}  */

	for (i = 0; i < instance->n; i++) {
		if (fscanf(instancefile, "%d %d", &instance->w[i], &instance->p[i]) != 2) {  
			fprintf(stderr, "Wrong instance format in element %d\n", i + 1);  
			free(instance->w);  
			free(instance->p);  
			free(instance);  
			fclose(instancefile);  
			return 0;  
		}  
	}
	fclose(instancefile);  
	for (i = 0; i < instance->n; i++)  
		instance->x[i] = 2; /* we don´t know what to pack yet */  
	return instance;  
} 

void printInstance(RSPinstance *RSPI){  
	int i;  
	printf("Printing RSP instance\n");  
	printf("Capacity: %d\n", RSPI->C);  
	printf("Number of Elements: %d\n", RSPI->n);  
	for (i = 0; i < RSPI->n; i++)  
		printf("Element %d: Weight: %d, Profit: %d\n", i, RSPI->w[i], RSPI->p[i]);  
} 

RSPinstance *Preprocessing(RSPinstance *RSPI, int *Jm, int *Jp, int *J0y){  
	/* simplify an RSP-instance */  

	RSPinstance *newRSPI;
	int j,k, *J0, *J1;
	int nJp, nJm, nJ0y;	/* variables to count the number of elements in the J_+, J_-, and J_0¯y  sets*/
	int sumJ1Jm, sumJ; /* sum over the weights in the J sets*/
	int nFixed, sumW, sumP; /* variables to count the number of fixed variables, total weight and total profit during preprocessing*/

    /* PREPROCESSING */

    /* 1. if n <= 0 => EXIT and return NULL,because instance does not make sense */  
	if (RSPI->n <= 0){  
		free(newRSPI);  
		return NULL;  
	} 
	J0 = (int*) calloc( RSPI->n, sizeof( int)); 
	J1 = (int*) calloc( RSPI->n, sizeof( int)); 
	newRSPI = malloc( sizeof( RSPinstance));
	sumJ1Jm = 0;
	nJp = 0;
	nJm = 0;
	nFixed = 0;
	sumW = 0;
	sumP = 0;

	for (j = 0; j < RSPI->n; j++) { 

        /* 2.  For all j element of J_0 :=  {j element [n] | p_j <= 0, w_j <= 0}: fix x_j = 0, 
    as those elements would never be packed */

		if (RSPI->p[j] <= 0 && RSPI->w[j] >= 0) { 
			RSPI->x[j] = 0;
			nFixed++; 
			J0[ j] = 1; 
		}
		/* 3. For all j element of J_1 := {j element [n] | p_j >= 0, w_j <= 0}: fix x_j = 1,  
			 as those elements can always be packed gainfully */ 

		if (RSPI->p[j] >= 0 && RSPI->w[j] <= 0) {
			RSPI->x[j] = 1;  
			J1[ j] = 1;
			nFixed++; 
			sumW = sumW + RSPI->w[j]; 
			sumP = sumP + RSPI->p[j]; 
			sumJ1Jm = sumJ1Jm + RSPI->w[j];
		}
		/* 4.  transformation of variables */  

		if (RSPI->p[j] < 0 && RSPI->w[j] < 0) {
			Jm[j] = 1;
			nJm++;
			sumJ1Jm = sumJ1Jm + RSPI->w[j];
		}

		if (RSPI->p[j] > 0 && RSPI->w[j] > 0) {
			Jp[j] = 1;
			nJp++;
		}
	}

	/* 5. if the capacity C < sum over the weights in the union of J_1 and J_m => EXIT
       as the instance has no valid solution */	

	if (RSPI->C < sumJ1Jm) {
		free(J0);
		free(J1);
		free(Jp);
		free(Jm);
		free(J0y);
		free(newRSPI);
		return NULL;
	}
	/* 6. for all j element of J_0¯y : fix y_j = 0 => accordingly fix x_j,
    as those objects violate the capacity restriction */
	sumJ = 0;
	nJ0y = 0;

	for (j=0; j < RSPI->n; j++) {
        /* find out if the element is in J_0¯y */
		if (abs(RSPI->w[j]) > RSPI->C - sumJ1Jm)
		{
            /* fix x_j = 1 - y_j = 1 (pack) if j is element of J_- */                
			if (Jm[j]==1) {
				RSPI->x[j]=1;
				nFixed++;
				sumW = sumW + RSPI->w[j];
				sumP = sumP + RSPI->p[j];
				nJ0y++;
				J0y[j]=1;
			}
			/* fix x_j = y_j = 0 (don´t pack) if j is element of J_+ */
			else if (Jp[j]==1) {
				RSPI->x[j]=0;
				nFixed++;
				nJ0y++;
				J0y[j]=1;
			}
		}

	}
	/* 7. if the sum over the weights of the elements j in J < Capacity C - the 
    sum of the weights of the elements of the union of J_1 and J_- => fix y_j= 1 
    and x_j accordingly, as all objects left can either be packed gainfully or  
    will not be packed */

	/* sum over the weights of the elements j in J */
	for (j=0; j < RSPI->n; j++) {
		if ((Jm[j]==1 || Jp[j]==1) && J0y[j]==0)
			sumJ = sumJ + abs(RSPI->w[j]);
	}

	if (sumJ <= (RSPI->C - sumJ1Jm)) {
		for(j=0; j <= RSPI->n; j++)
		{
            /* fix x_j = 1 - y_j = 0 (don´t pack) if j is element of J_- */ 
			if (Jm[j]==1 && J0y[j]==0) {
				RSPI->x[j]=0;
				nFixed++;
			}
			/* fix x_j = y_j = 1 (pack) if j is element of J_- */
			else if (Jp[j]==1 && J0y[j]==0) {
				RSPI->x[j]=1;
				nFixed++;
				sumW = sumW + RSPI->w[j];
				sumP = sumP + RSPI->p[j];
			}
		}
		free(J0);
		free(J1);
		free(Jp);
		free(Jm);
		free(J0y);
		free(newRSPI);
		printf("The problem is optimally solved\n");
		printf("Number of fixed variables: %i\n", nFixed);
		printf("Total weight: %i, total gain: %i.\n", sumW, sumP);
		exit( 0);	
	}

   /* construct residual instance */
	newRSPI->C = RSPI->C - sumJ1Jm;
	newRSPI->n = nJm + nJp - nJ0y;
	newRSPI->x = (char*) malloc(sizeof(char) * newRSPI->n);  
	newRSPI->p = (int*) malloc(sizeof(int) * newRSPI->n);  
	newRSPI->w = (int*) malloc(sizeof(int) * newRSPI->n);  

	k =0 ;
	for (j=0; j < RSPI->n; j++)
	{
		if ((Jm[j]==1 || Jp[j]==1) && J0y[j]==0)
		{
			newRSPI->p[k] = abs(RSPI->p[j]);
			newRSPI->w[k] = abs(RSPI->w[j]);
			k++;
		}
	}

	printf("Residual capacity: %i.\n", newRSPI->C); 
	printf("Number of fixed variables: %i\n", nFixed);
	printf("Current weight: %i, current gain: %i.\n", sumW, sumP);

	free(J0);
	free(J1);
	return newRSPI;  
}

void TransformSolution(RSPinstance *RSPI_org,RSPinstance *RSPI_residual,int *Jm, int *Jp, int *J0y)
{
	int j, k;

	k = 0;
	/* transformation of x for j in J */
	for (j=0; j < RSPI_org->n; j++) {
        /* if j is in J_- => x_j = 1 - x_residual_k */
		if (Jm[j]==1 && J0y[j]==0) {
			RSPI_org->x[j] = 1 - RSPI_residual->x[k]; 
			k++;
		}
		/* if j is in J_+ => x_j = x_residual_k */
		else if (Jp[j]==1 && J0y[j]==0) {
			RSPI_org->x[j]= RSPI_residual->x[k];
			k++;
		}
	}

	free(J0y);
	free(Jm);
	free(Jp);
	free(RSPI_residual->x);
	free(RSPI_residual->p);
	free(RSPI_residual->w);
	free(RSPI_residual);

}

void Solve(RSPinstance *RSPI)
{

	int j;
    /* A real solve function will be implemented later */
	for (j=0; j < RSPI->n; j++)
		RSPI->x[j]=0;

}

int main(int argc, char *argv[]){  
	RSPinstance *RSPI, *RSPI_residual;
	int i;
	int *Jm, *Jp, *J0y;
	int ZFW, TW;
	FILE *instancefile;
	if (argc != 2){  
		printf("Wrong number of parameters, there must be exactly one file name\n");  
		exit(-1);  
	} 
	instancefile = fopen( argv[1], "r");
	if (NULL ==instancefile){  
		fprintf(stderr, "Failed opening file\n");  
		exit(-1);  
	}

	RSPI = ReadData(fopen(argv[1], "r"));  
	Jm = (int*) malloc(sizeof(int) * RSPI->n);  
	Jp = (int*) malloc(sizeof(int) * RSPI->n);  
	J0y = (int*) malloc(sizeof(int) * RSPI->n);  

	/* call the preprocessing function */
	RSPI_residual = Preprocessing( RSPI, Jm, Jp, J0y);

	if (NULL == RSPI_residual) {
		fprintf( stderr, "There is no valid solution\n");
		exit( -1);
	}

	Solve( RSPI_residual);

	TransformSolution( RSPI, RSPI_residual, Jm, Jp, J0y);

	ZFW = 0;
	TW = 0;
	for (i=0; i < RSPI->n; i++) {
		ZFW = ZFW + RSPI->p[i] * RSPI->x[i];
		TW = TW + RSPI->w[i] * RSPI->x[i];
	}

	printf("Zielfunktionswert: %i, total weight: %i\n", ZFW, TW);

  /* display the indices of the packed variables*/
	for (i=0; i < RSPI->n; i++)
	{
		if(RSPI->x[i]==1) {
			printf("%i\n", i+1);
		}
	}

	exit( 0);
}

Was meint ihr dazu so weit?

[nwp2]

Wieso hast du denn die Zeilen 68-76 auskommentiert?
In den Zeilen 254ff und 342ff castest du malloc, das sehen die bestimmt nicht gern.
sizeof(int) und sizeof(char) würde ich in diesen Zeilen vermeiden, lieber sizeof variable benutzen. Das hat den Vorteil, dass man mal eben den Datentyp in RSPinstance ändern kann ohne den Code überall anpassen zu müssen.
Der Stil ist auch nicht durchgängig gleich, man sollte meinen dir hätte jemand geholfen . Benutze Tools wie Astyle die dem Programm automatisch einen einheitlichen Stil verpassen.

[volkard]

nwp2 schrieb:

Benutze Tools wie Astyle die dem Programm automatisch einen einheitlichen Stil verpassen.

Benutze so Tools nur, wenn Du von unten kommend das Mittelmaß anstrebst.

[julieann]

Also, hier noch einmal eine aktualisierte Version.

Ich habe die Ausgabe in Z 68-76 auskommentiert, weil wir sie in der Aufgabe eben nicht ausgeben sollen. Ja, der Stil ist ja schon deshalb nicht durchgängig, weil ich mit den Grundlagen aus diesem Thread weitergearbeitet habe. Und ja, ich habe auch mit den anderen aus meinem Kurs zusammengearbeitet. Ist doch nicht verboten. Ich habe aber trotzdem daran gearbeitet und werde die nächsten Aufgaben auch erarbeiten. Mit dem sizeof werde ich es morgen nochmal ausprobieren.

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

typedef struct {
	int C; /* Capacity */  
	int *w; /* weight */  
	int *p; /* profit */  
	int n; /* number of elements */  
	char *x; /* solution, 0 = dont pack, 1 = pack, 2 = dont know yet */  

} RSPinstance; 

RSPinstance *RSPinstanceCopy(RSPinstance *RSPI){  
	/* copy the RSP-Instance */  
	RSPinstance *newRSPI = (RSPinstance*) malloc(sizeof(RSPinstance));  
	int i;  
	newRSPI->C = RSPI->C;  
	newRSPI->n = RSPI->n;  
	newRSPI->x = (char*) malloc(sizeof(char) * newRSPI->n);  
	newRSPI->p = (int*) malloc(sizeof(int) * newRSPI->n);  
	newRSPI->w = (int*) malloc(sizeof(int) * newRSPI->n);  

	for (i = 0; i < RSPI->n; i++){  
		newRSPI->p[i] = RSPI->p[i];  
		newRSPI->w[i] = RSPI->w[i];  
		newRSPI->x[i] = RSPI->x[i];  
	}  
	return newRSPI;  
} 

RSPinstance *ReadData(FILE *instancefile){  
	/* open file */  
	RSPinstance *instance;  
	int i;  

	/* fill instance */  
	instance = malloc(sizeof *instance);  
	if (!instance){  
		fprintf(stderr, "Out of memory\n");  
		fclose(instancefile);  
		return 0;  
	}  
	if (fscanf(instancefile, "%d", &instance->C) != 1){  
		fprintf(stderr, "Wrong instance format in parameter C\n");  
		free(instance);  
		fclose(instancefile);  
		return 0;  
	}  
	if (fscanf(instancefile, "%d", &instance->n) != 1){  
		fprintf(stderr, "Wrong instance format in paramenter n\n");  
		free(instance);  
		fclose(instancefile);  
		return 0;  
	}  
	if (instance->n <= 0){  
		fprintf(stderr, "Wrong instance format in parameter n must not be <= 0\n");  
		free(instance);  
		fclose(instancefile);  
		return 0;  
	}  
	/* allocate memory for the elements of the instance */
	instance->w = (int*) malloc(sizeof(int) * instance->n);  
	instance->p = (int*) malloc(sizeof(int) * instance->n);  
	instance->x = (char*) malloc(sizeof(char) * instance->n);  
	/*if (!instance->w || !instance->p || !instance->x){  
		fprintf(stderr, "Out of memory\n");  
		free(instance->w);  
		free(instance->p);  
		free(instance->x);  
		free(instance);  
		fclose(instancefile);  
		return 0;  
		}  */

	for (i = 0; i < instance->n; i++) {
		if (fscanf(instancefile, "%d %d", &instance->w[i], &instance->p[i]) != 2) {  
			fprintf(stderr, "Wrong instance format in element %d\n", i + 1);  
			free(instance->w);  
			free(instance->p);  
			free(instance);  
			fclose(instancefile);  
			return 0;  
		}  
	}
	fclose(instancefile);  
	for (i = 0; i < instance->n; i++)  
		instance->x[i] = 2; /* we dont know what to pack yet */  
	return instance;  
} 

void printInstance(RSPinstance *RSPI){  
	int i;  
	printf("Printing RSP instance\n");  
	printf("Capacity: %d\n", RSPI->C);  
	printf("Number of Elements: %d\n", RSPI->n);  
	for (i = 0; i < RSPI->n; i++)  
		printf("Element %d: Weight: %d, Profit: %d\n", i, RSPI->w[i], RSPI->p[i]);  
} 

RSPinstance *Preprocessing(RSPinstance *RSPI, int *Jm, int *Jp, int *J0y){  
	/* simplify an RSP-instance */  

	RSPinstance *newRSPI;
	int j,k, *J0, *J1;
	int nJp, nJm, nJ0y;	/* variables to count the number of elements in the J_+, J_-, and J_0¯y  sets*/
	int sumJ1Jm, sumJ; /* sum over the weights in the J sets*/
	int nFixed0, nFixed1, sumW, sumP; /* variables to count the number of fixed variables, total weight and total profit during preprocessing*/

    /* PREPROCESSING */

    /* 1. if n <= 0 => EXIT and return NULL,because instance does not make sense */  
	if (RSPI->n <= 0){  
		free(newRSPI);  
		return NULL;  
	} 

	J0 = (int*) calloc( RSPI->n, sizeof( int)); 
	J1 = (int*) calloc( RSPI->n, sizeof( int)); 
	newRSPI = malloc( sizeof( RSPinstance));
	sumJ1Jm = 0;
	nJp = 0;
	nJm = 0;
	nFixed0 = 0;
	nFixed1=0;
	sumW = 0;
	sumP = 0;

	for (j = 0; j < RSPI->n; j++) { 

        /* 2.  For all j element of J_0 :=  {j element [n] | p_j <= 0, w_j >= 0}: fix x_j = 0, 
    as those elements would never be packed */

		if (RSPI->p[j] <= 0 && RSPI->w[j] >= 0) { 
			RSPI->x[j] = 0;
			nFixed0++; 
			J0[ j] = 1; 
		}
		/* 3. For all j element of J_1 := {j element [n] | p_j >= 0, w_j <= 0}: fix x_j = 1,  
			 as those elements can always be packed gainfully */ 

		if (RSPI->p[j] >= 0 && RSPI->w[j] <= 0) {
			RSPI->x[j] = 1;  
			J1[ j] = 1;
			nFixed1++; 
			sumW = sumW + RSPI->w[j]; 
			sumP = sumP + RSPI->p[j]; 
			sumJ1Jm = sumJ1Jm + RSPI->w[j];
		}
		/* 4.  transformation of variables */  

		if (RSPI->p[j] < 0 && RSPI->w[j] < 0) {
			Jm[j] = 1;
			nJm++;
			sumJ1Jm = sumJ1Jm + RSPI->w[j];
		}

		if (RSPI->p[j] > 0 && RSPI->w[j] > 0) {
			Jp[j] = 1;
			nJp++;
		}
	}

	/* 5. if the capacity C < sum over the weights in the union of J_1 and J_m => EXIT
       as the instance has no valid solution */	

	if (RSPI->C < sumJ1Jm) {
		free(J0);
		free(J1);
		free(Jp);
		free(Jm);
		free(J0y);
		free(newRSPI);
		return NULL;
	}
	/* 6. for all j element of J_0¯y : fix y_j = 0 => accordingly fix x_j,
    as those objects violate the capacity restriction */
	sumJ = 0;
	nJ0y = 0;

	for (j=0; j < RSPI->n; j++) {
        /* find out if the element is in J_0¯y */
		if (abs(RSPI->w[j]) > RSPI->C - sumJ1Jm)
		{
            /* fix x_j = 1 - y_j = 1 (pack) if j is element of J_- */                
			if (Jm[j]==1) {
				RSPI->x[j]=1;
				nFixed1++;
				sumW = sumW + RSPI->w[j];
				sumP = sumP + RSPI->p[j];
				nJ0y++;
				J0y[j]=1;
			}
			/* fix x_j = y_j = 0 (dont pack) if j is element of J_+ */
			else if (Jp[j]==1) {
				RSPI->x[j]=0;
				nFixed0++;
				nJ0y++;
				J0y[j]=1;
			}
		}

	}
	/* 7. if the sum over the weights of the elements j in J < Capacity C - the 
    sum of the weights of the elements of the union of J_1 and J_- => fix y_j= 1 
    and x_j accordingly, as all objects left can either be packed gainfully or  
    will not be packed */

	/* sum over the weights of the elements j in J */
	for (j=0; j < RSPI->n; j++) {
		if ((Jm[j]==1 || Jp[j]==1) && J0y[j]==0)
			sumJ = sumJ + abs(RSPI->w[j]);
	}

	if (sumJ <= (RSPI->C - sumJ1Jm)) {
		for(j=0; j < RSPI->n; j++)
		{
            /* fix x_j = 1 - y_j = 0 (dont pack) if j is element of J_- */ 
			if (Jm[j]==1 && J0y[j]==0) {
				RSPI->x[j]=0;
				nFixed0++;
			}
			/* fix x_j = y_j = 1 (pack) if j is element of J_- */
			else if (Jp[j]==1 && J0y[j]==0) {
				RSPI->x[j]=1;
				nFixed1++;
				sumW = sumW + RSPI->w[j];
				sumP = sumP + RSPI->p[j];
			}
		}
		free(J0);
		free(J1);
		free(Jp);
		free(Jm);
		free(J0y);
		printf("\nPREPROCESSING:\n\n");
		printf("The problem is optimally solved\n");
		printf("Number of variables fixed to 0: %i\nNumber of variables fixed to 1: %i\n", nFixed0, nFixed1);
		printf("Total weight of objects packed during preprocessing: %i\nTotal profit of objects packed during preprocessing: %i\n", sumW, sumP);
		newRSPI->n = 0;
		return (newRSPI);	
	}

   /* construct residual instance */
	newRSPI->C = RSPI->C - sumJ1Jm;
	newRSPI->n = nJm + nJp - nJ0y;
	newRSPI->x = (char*) malloc(sizeof(char) * newRSPI->n);  
	newRSPI->p = (int*) malloc(sizeof(int) * newRSPI->n);  
	newRSPI->w = (int*) malloc(sizeof(int) * newRSPI->n);  

	k =0 ;
	for (j=0; j < RSPI->n; j++)
	{
		if ((Jm[j]==1 || Jp[j]==1) && J0y[j]==0)
		{
			newRSPI->p[k] = abs(RSPI->p[j]);
			newRSPI->w[k] = abs(RSPI->w[j]);
			k++;
		}
	}
	printf("\nPREPROCESSING:\n\n");
	printf("Residual capacity: %i.\n", newRSPI->C); 
	printf("Number of variables fixed to 0: %i\nNumber of variables fixed to 1: %i\n", nFixed0, nFixed1);
	printf("Total weight of objects packed during preprocessing: %i\nTotal profit of objects packed during preprocessing: %i\n", sumW, sumP);

	free(J0);
	free(J1);
	return newRSPI;  
}

void TransformSolution(RSPinstance *RSPI_org,RSPinstance *RSPI_residual,int *Jm, int *Jp, int *J0y)
{
	int j, k;

	k = 0;
	/* transformation of x for j in J */
	for (j=0; j < RSPI_org->n; j++) {
        /* if j is in J_- => x_j = 1 - x_residual_k */
		if (Jm[j]==1 && J0y[j]==0) {
			RSPI_org->x[j] = 1 - RSPI_residual->x[k]; 
			k++;
		}
		/* if j is in J_+ => x_j = x_residual_k */
		else if (Jp[j]==1 && J0y[j]==0) {
			RSPI_org->x[j]= RSPI_residual->x[k];
			k++;
		}
	}

	free(J0y);
	free(Jm);
	free(Jp);
	free(RSPI_residual->x);
	free(RSPI_residual->p);
	free(RSPI_residual->w);
	free(RSPI_residual);

}

void Solve(RSPinstance *RSPI)
{

	int j;
    /* A real solve function will be implemented later */
	for (j=0; j < RSPI->n; j++)
		RSPI->x[j]=0;

}

int main(int argc, char *argv[]){  
	RSPinstance *RSPI, *RSPI_residual;
	int i;
	int *Jm, *Jp, *J0y;
	int ZFW, TW; 
	FILE *instancefile;
	if (argc != 2){  
		printf("Wrong number of parameters, there must be exactly one file name\n");  
		exit(-1);  
	} 
	instancefile = fopen( argv[1], "r");
	if (NULL ==instancefile){  
		fprintf(stderr, "Failed opening file\n");  
		exit(-1);  
	}

	RSPI = ReadData(fopen(argv[1], "r"));  
	Jm = (int*) calloc(RSPI->n,sizeof(int));  
	Jp = (int*) calloc(RSPI->n,sizeof(int));  
	J0y = (int*) calloc(RSPI->n,sizeof(int));  

	/* call the preprocessing function */
	RSPI_residual = Preprocessing( RSPI, Jm, Jp, J0y);

	if (NULL == RSPI_residual) {
		fprintf( stderr, "There is no valid solution\n");
		exit( -1);
	}

	if (RSPI_residual->n != 0)
	{
	Solve( RSPI_residual);

	TransformSolution( RSPI, RSPI_residual, Jm, Jp, J0y);

	}

	ZFW = 0;
	TW = 0;
	for (i=0; i < RSPI->n; i++) {
		ZFW = ZFW + RSPI->p[i] * RSPI->x[i];
		TW = TW + RSPI->w[i] * RSPI->x[i];
	}

	printf("Profit: %i\nWeight: %i\n", ZFW, TW);

  /* display the indices of the packed variables*/

	printf("Indices of packed objects:\n");
	for (i=0; i < RSPI->n; i++)
	{

		if(RSPI->x[i]==1) {

			printf("%i\t", i+1);
		}
	}
	printf("\n");

	exit( 0);
}

[nwp2]

In Zeile 68-76 ist doch der Test ob malloc Speicher gefunden hat, keine Ausgabe. Zeile 69 kann man rausnehmen wenn man die Nachricht nicht will, aber der Rest sollte bleiben.

Wenn ihr zusammen arbeiten dürft passt das ja alles. Ich habe nur öfters 0 Punkte wegen Plagiat bekommen.

[Bashar]

nwp2 schrieb:

Ich habe nur öfters 0 Punkte wegen Plagiat bekommen.

Öfters?

[nwp2]

Ja, praktische Informatik 1/2, Aufgaben in Java/Prolog/Haskel. Ich fand es ganz nett meine Lösungen auf meine Homepage zu packen, oder generell alles mögliche was ich so schreibe, damit ich irgendwann was vorzuzeigen habe. Irgendwie haben das Leute gefunden und kopiert, ohne wenigstens eine Variable umzubenennen oder AStyle drüber laufen zu lassen. Da man nicht mit letzter Sicherheit sagen kann wer von wem abgeschrieben hat gab es für beide 0 Punkte. Als die Punkte knapp wurden (70% war Voraussetzung) habe ich das online stellen sein gelassen.

Gut zu wissen, dass Gruppenarbeit nicht überall unterdrückt wird.