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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
#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;
}
/* Shuffle data items starting on a certain index, in place */
void shuffle_items(struct data * d, int start) {
int i, ind;
struct item * new_items;
if (start < 0) return;
if (start >= d->N) return;
new_items = (struct item *)malloc(d->N * sizeof(struct item));
/* These stay the same */
for(i = 0; i < start; i++) {
new_items[i].p = d->items[i].p;
new_items[i].w = d->items[i].w;
}
/* Shuffle the rest */
for(i = start; i < d->N; i++) {
ind = rand() % (d->N - i);
new_items[i].p = d->items[i+ind].p;
new_items[i].w = d->items[i+ind].w;
d->items[i+ind].p = d->items[i].p;
d->items[i+ind].w = d->items[i].w;
}
/* Replace old array */
free(d->items);
d->items = new_items;
}
|
