1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include "structs.h"
#include "common.h"
struct data * input(char fp[]){
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;
}
fclose(f);
return d;
}
int cmp_items_ratio(const void * a, const void * b){
struct item c = *(struct item *)a;
struct item d = *(struct item *)b;
if(c.p / c.w < d.p / d.w){
return 1;
}
return -1;
}
int cmp_items_random(const void *a, const void *b) {
if(rand() % 2 == 0){
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");
}
void print_front(struct front_item * b){
struct front_item * beg = b;
printf("Profit, Weight, Time\n");
while(b!=NULL){
clock_t t = b->time - beg->time;
printf("%.02f,%.02f,%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);
}
void free_front(struct front_item * b){
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;
f->time = clock();
return f;
}
struct tree_item * new_tree_item(long int depth, long int itemi, double w, double p, struct tree_item * prev, struct tree_item * next) {
struct tree_item * t = (struct tree_item *)malloc(sizeof(struct tree_item));
t->depth = depth;
t->itemi = itemi;
t->values.w = w;
t->values.p = p;
t->prev = prev;
t->next = next;
return t;
}
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));
}
int len_front(struct front_item * f){
int N;
for(N=0;f!=NULL;f=f->next,N++);
return N;
}
|
