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
|
#include <stdlib.h>
#include "random_heuristic.h"
#include "structs.h"
#include "common.h"
struct front_item * random_heuristic(struct data * data) {
struct front_item * front = new_front_item(0, 0, NULL, NULL);
struct front_item * front_last = front;
struct tree_item * tree = new_tree_item(0, 0, 0, 0, NULL, NULL);
long int tree_size = 1;
do {
/* Choose tree node randomly */
long int position = rand() % tree_size;
struct tree_item * node = tree;
for(int i = 0; i < position; i++,node=node->next);
/* Check if node is leaf */
if(node->depth == data->N) {
front_last->next = new_front_item(node->values.p, node->values.w, front_last, NULL);
front_last = front_last->next;
struct tree_item * old = node;
if(tree == old) {
tree = node->next;
}
if(node->next != NULL) {
node->next->prev = node->prev;
}
if(node->prev != NULL) {
node->prev->next = node->next;
}
free(old);
/* Reduce tree_size */
tree_size--;
continue;
}
/* Make left node (select item) */
struct tree_item * left = new_tree_item(
node->depth + 1,
node->itemi + 1,
node->values.w + data->items[node->itemi].w,
node->values.p + data->items[node->itemi].p,
node->prev,
node
);
if(node->prev != NULL){
node->prev->next = left;
}
/* Make right node (do not select item) */
struct tree_item * right = new_tree_item(
node->depth + 1,
node->itemi + 1,
node->values.w,
node->values.p,
left,
node->next
);
if(node->next != NULL) {
node->next->prev = right;
}
/* Adjust left->next to right */
left->next = right;
struct tree_item * old = node;
if(node == tree) {
tree = left;
}
free(old);
/* Increment tree_size */
tree_size++;
} while(tree != NULL);
/* Remove first item from front (only a placeholder) */
front=front->next;
free(front->prev);
front->prev = NULL;
return front;
return NULL;
}
|
