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
|
#include <stdlib.h>
#include "nem_ull.h"
#include "structs.h"
#include "common.h"
struct front_item * nem_ull(struct data * d){
struct front_item * begin;
int i;
begin = new_front_item(0,0,NULL,NULL);
for(i=0;i<d->N;++i){
begin = nem_ull_step(begin,d,i);
}
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;
}
|
