summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/common.c96
-rw-r--r--src/main/dfs.c18
-rw-r--r--src/main/nem_ull.c32
-rw-r--r--src/nem_ull.c172
4 files changed, 159 insertions, 159 deletions
diff --git a/src/common.c b/src/common.c
index d6f1eb3..2cfd44f 100644
--- a/src/common.c
+++ b/src/common.c
@@ -6,25 +6,25 @@
#include "common.h"
struct data * input(char fp[]){
- int i,j;
- FILE *f;
- struct data * d = (struct data *)malloc(sizeof(struct data));
+ int i,j;
+ FILE *f;
+ struct data * d = (struct data *)malloc(sizeof(struct data));
- f = fopen(fp,"r");
- j = fscanf(f,"%ld",&(d->N));
- if(j!=1){
- printf("Error reading data\n");
- exit(0);
- }
- d->items = (struct item *)malloc(d->N*sizeof(struct item));
- for(i=0;i<d->N;++i){
- j = fscanf(f,"%lf %lf",&(d->items[i].p),&(d->items[i].w));
- d->allp += d->items[i].p;
- d->allw += d->items[i].w;
- }
+ f = fopen(fp,"r");
+ j = fscanf(f,"%ld",&(d->N));
+ if(j!=1){
+ printf("Error reading data\n");
+ exit(0);
+ }
+ d->items = (struct item *)malloc(d->N*sizeof(struct item));
+ for(i=0;i<d->N;++i){
+ j = fscanf(f,"%lf %lf",&(d->items[i].p),&(d->items[i].w));
+ d->allp += d->items[i].p;
+ d->allw += d->items[i].w;
+ }
- fclose(f);
- return d;
+ fclose(f);
+ return d;
}
int cmp_items_ratio(const void * a, const void * b){
@@ -33,60 +33,60 @@ int cmp_items_ratio(const void * a, const void * b){
if(c.p / c.w < d.p / d.w){
return 1;
}
- return -1;
+ return -1;
}
void print_data(struct data * d){
- int i;
- printf("### PRINTING DATA - BEGINNING ###\n");
- printf("N:\t%ld\n\n",d->N);
- printf("Profit\tWeight\n");
- for(i=0;i<d->N;++i){
- printf("%.02f\t%.02f\n",d->items[i].p,d->items[i].w);
- }
- printf("### PRINTING DATA - ENDING ###\n");
+ int i;
+ printf("### PRINTING DATA - BEGINNING ###\n");
+ printf("N:\t%ld\n\n",d->N);
+ printf("Profit\tWeight\n");
+ for(i=0;i<d->N;++i){
+ printf("%.02f\t%.02f\n",d->items[i].p,d->items[i].w);
+ }
+ printf("### PRINTING DATA - ENDING ###\n");
}
void print_front(struct front_item * b){
struct front_item * beg = b;
- while(b!=NULL){
+ while(b!=NULL){
clock_t t = b->time - beg->time;
- printf("%.02f,\t%.02f,\t%f\n", b->i.p, b->i.w, ((double)t)/CLOCKS_PER_SEC);
- b = b->next;
- }
+ printf("%.02f,\t%.02f,\t%f\n", b->i.p, b->i.w, ((double)t)/CLOCKS_PER_SEC);
+ b = b->next;
+ }
}
void free_data(struct data * d){
- free(d->items);
- free(d);
+ free(d->items);
+ free(d);
}
void free_front(struct front_item * b){
- struct front_item * tmp;
- for(;b!=NULL;){
- tmp = b;
- b = b->next;
- free(tmp);
- }
+ struct front_item * tmp;
+ for(;b!=NULL;){
+ tmp = b;
+ b = b->next;
+ free(tmp);
+ }
}
struct front_item * new_front_item(double p, double w, struct front_item * prev, struct front_item * next){
- struct front_item * f = (struct front_item *)malloc(sizeof(struct front_item));
- f->i.p = p;
- f->i.w = w;
- f->next = next;
- f->prev = prev;
+ struct front_item * f = (struct front_item *)malloc(sizeof(struct front_item));
+ f->i.p = p;
+ f->i.w = w;
+ f->next = next;
+ f->prev = prev;
f->time = clock();
- return f;
+ return f;
}
double dist_items(struct item * a, struct item * b){
- return sqrt((a->p - b->p)*(a->p - b->p) + (a->w - b->w)*(a->w - b->w));
+ return sqrt((a->p - b->p)*(a->p - b->p) + (a->w - b->w)*(a->w - b->w));
}
int len_front(struct front_item * f){
- int N;
- for(N=0;f!=NULL;f=f->next,N++);
- return N;
+ int N;
+ for(N=0;f!=NULL;f=f->next,N++);
+ return N;
}
diff --git a/src/main/dfs.c b/src/main/dfs.c
index 36faa25..ca796c5 100644
--- a/src/main/dfs.c
+++ b/src/main/dfs.c
@@ -5,23 +5,23 @@
#include "dfs.h"
int main(int argc, char * argv[]){
- struct data * d;
+ struct data * d;
struct front_item * b;
- if(argc!=2){
- printf("Wrong number of arguments!\n");
- printf("Example usage: %s data_file\n",argv[0]);
- return 0;
- }
+ if(argc!=2){
+ printf("Wrong number of arguments!\n");
+ printf("Example usage: %s data_file\n",argv[0]);
+ return 0;
+ }
- d = input(argv[1]);
+ d = input(argv[1]);
clock_t t = clock();
b = dfs(d);
t = clock() - t;
- printf("%f,%d\n",((float)t)/CLOCKS_PER_SEC,len_front(b));
-
+ printf("%f,%d\n",((float)t)/CLOCKS_PER_SEC,len_front(b));
+
print_front(b);
free_front(b);
diff --git a/src/main/nem_ull.c b/src/main/nem_ull.c
index b267422..2bf29a6 100644
--- a/src/main/nem_ull.c
+++ b/src/main/nem_ull.c
@@ -5,27 +5,27 @@
#include "nem_ull.h"
int main(int argc, char * argv[]){
- struct data * d;
- struct front_item * b;
+ struct data * d;
+ struct front_item * b;
- if(argc!=2){
- printf("Wrong number of arguments!\n");
- printf("Example usage: %s data_file\n",argv[0]);
- return 0;
- }
+ if(argc!=2){
+ printf("Wrong number of arguments!\n");
+ printf("Example usage: %s data_file\n",argv[0]);
+ return 0;
+ }
- d = input(argv[1]);
-
+ d = input(argv[1]);
+
clock_t t = clock();
- b = nem_ull(d);
+ b = nem_ull(d);
- t = clock() - t;
- printf("%f,%d\n",((float)t)/CLOCKS_PER_SEC,len_front(b));
+ t = clock() - t;
+ printf("%f,%d\n",((float)t)/CLOCKS_PER_SEC,len_front(b));
- print_front(b);
+ print_front(b);
- free_front(b);
- free_data(d);
+ free_front(b);
+ free_data(d);
- return 0;
+ return 0;
}
diff --git a/src/nem_ull.c b/src/nem_ull.c
index 9a6b328..f08506b 100644
--- a/src/nem_ull.c
+++ b/src/nem_ull.c
@@ -4,96 +4,96 @@
#include "common.h"
struct front_item * nem_ull(struct data * d){
- struct front_item * begin;
- int i;
+ struct front_item * begin;
+ int i;
- begin = new_front_item(0,0,NULL,NULL);
+ begin = new_front_item(0,0,NULL,NULL);
- for(i=0;i<d->N;++i){
- begin = nem_ull_step(begin,d,i);
- }
+ for(i=0;i<d->N;++i){
+ begin = nem_ull_step(begin,d,i);
+ }
- return begin;
+ return begin;
}
struct front_item * nem_ull_step(struct front_item * b, struct data * d, int it){
- unsigned long int i,l0t,l1t,n;
- double pmax;
- struct item * l0;
- struct item * l1;
- struct front_item * p = b;
-
- for(n=0;p!=NULL;p=p->next,++n);
- p = b;
-
- l0 = (struct item *)malloc(n*sizeof(struct item));
- l1 = (struct item *)malloc(n*sizeof(struct item));
-
- for(i=0;i<n;++i){
- l0[i].p=p->i.p;
- l0[i].w=p->i.w;
-
- l1[i].p=p->i.p + d->items[it].p;
- l1[i].w=p->i.w + d->items[it].w;
-
- b = p;
- p = p->next;
- free(b);
- }
-
- pmax = -1;
- l0t = 0;
- l1t = 0;
- p = new_front_item(0,0,NULL,NULL);
-
- while(1){
- for(;l0t<n;++l0t){
- if(l0[l0t].p > pmax){
- break;
- }
- }
-
- for(;l1t<n;++l1t){
- if(l1[l1t].p > pmax){
- break;
- }
- }
-
- if(l0t == n){
- for(;l1t<n;++l1t){
- p = new_front_item(l1[l1t].p, l1[l1t].w, p, NULL);
- p->prev->next = p;
- }
- break;
- }
-
- if(l1t == n){
- for(;l0t<n;++l0t){
- p = new_front_item(l0[l0t].p, l0[l0t].w, p, NULL);
- p->prev->next = p;
- }
- break;
- }
-
- if((l0[l0t].w < l1[l1t].w) || ((l0[l0t].w == l1[l1t].w) && (l0[l0t].p > l1[l1t].p))){
- p = new_front_item(l0[l0t].p, l0[l0t].w , p, NULL);
- p->prev->next = p;
- pmax = l0[l0t].p;
- ++l0t;
- } else {
- p = new_front_item(l1[l1t].p, l1[l1t].w , p, NULL);
- p->prev->next = p;
- pmax = l1[l1t].p;
- ++l1t;
- }
- }
-
- free(l0);
- free(l1);
-
- for(;p->prev!=NULL;p=p->prev);
- p=p->next;
- free(p->prev);
- p->prev=NULL;
- return p;
+ unsigned long int i,l0t,l1t,n;
+ double pmax;
+ struct item * l0;
+ struct item * l1;
+ struct front_item * p = b;
+
+ for(n=0;p!=NULL;p=p->next,++n);
+ p = b;
+
+ l0 = (struct item *)malloc(n*sizeof(struct item));
+ l1 = (struct item *)malloc(n*sizeof(struct item));
+
+ for(i=0;i<n;++i){
+ l0[i].p=p->i.p;
+ l0[i].w=p->i.w;
+
+ l1[i].p=p->i.p + d->items[it].p;
+ l1[i].w=p->i.w + d->items[it].w;
+
+ b = p;
+ p = p->next;
+ free(b);
+ }
+
+ pmax = -1;
+ l0t = 0;
+ l1t = 0;
+ p = new_front_item(0,0,NULL,NULL);
+
+ while(1){
+ for(;l0t<n;++l0t){
+ if(l0[l0t].p > pmax){
+ break;
+ }
+ }
+
+ for(;l1t<n;++l1t){
+ if(l1[l1t].p > pmax){
+ break;
+ }
+ }
+
+ if(l0t == n){
+ for(;l1t<n;++l1t){
+ p = new_front_item(l1[l1t].p, l1[l1t].w, p, NULL);
+ p->prev->next = p;
+ }
+ break;
+ }
+
+ if(l1t == n){
+ for(;l0t<n;++l0t){
+ p = new_front_item(l0[l0t].p, l0[l0t].w, p, NULL);
+ p->prev->next = p;
+ }
+ break;
+ }
+
+ if((l0[l0t].w < l1[l1t].w) || ((l0[l0t].w == l1[l1t].w) && (l0[l0t].p > l1[l1t].p))){
+ p = new_front_item(l0[l0t].p, l0[l0t].w , p, NULL);
+ p->prev->next = p;
+ pmax = l0[l0t].p;
+ ++l0t;
+ } else {
+ p = new_front_item(l1[l1t].p, l1[l1t].w , p, NULL);
+ p->prev->next = p;
+ pmax = l1[l1t].p;
+ ++l1t;
+ }
+ }
+
+ free(l0);
+ free(l1);
+
+ for(;p->prev!=NULL;p=p->prev);
+ p=p->next;
+ free(p->prev);
+ p->prev=NULL;
+ return p;
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-15 12:30:57 +0000