diff options
author | Alexandre Jesus <adbjesus@gmail.com> | 2016-09-16 01:16:28 +0100 |
---|---|---|
committer | Alexandre Jesus <adbjesus@gmail.com> | 2016-09-16 01:16:28 +0100 |
commit | 8865d83090d9820380af95bfdc121b42e60ac62f (patch) | |
tree | 68db8fc792d8af45ac4b022c6b63a61f1791f695 /src/nem_ull.c | |
parent | 80b7a8116d821aeae489086a403a6cdfd64d801a (diff) | |
download | libuknapsack-8865d83090d9820380af95bfdc121b42e60ac62f.tar.gz libuknapsack-8865d83090d9820380af95bfdc121b42e60ac62f.zip |
Retab to spaces
Diffstat (limited to 'src/nem_ull.c')
-rw-r--r-- | src/nem_ull.c | 172 |
1 files changed, 86 insertions, 86 deletions
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; } |