From 3c8f9385498611df123d5f07d0e52035b568d415 Mon Sep 17 00:00:00 2001 From: Alexandre Jesus Date: Mon, 22 Aug 2016 16:35:31 +0100 Subject: Initial code --- .gitignore | 67 ++++++++++++++++++++++++++++++++++++ CMakeLists.txt | 61 +++++++++++++++++++++++++++++++++ README.md | 8 +++++ include/common.h | 19 +++++++++++ include/nem_ull.h | 9 +++++ include/structs.h | 20 +++++++++++ src/common.c | 88 ++++++++++++++++++++++++++++++++++++++++++++++++ src/main/nem_ull.c | 31 +++++++++++++++++ src/nem_ull.c | 99 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 9 files changed, 402 insertions(+) create mode 100644 .gitignore create mode 100644 CMakeLists.txt create mode 100644 include/common.h create mode 100644 include/nem_ull.h create mode 100644 include/structs.h create mode 100644 src/common.c create mode 100644 src/main/nem_ull.c create mode 100644 src/nem_ull.c diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..40a1124 --- /dev/null +++ b/.gitignore @@ -0,0 +1,67 @@ + +# Created by https://www.gitignore.io/api/vim,linux,osx,cmake + +### Vim ### +# swap +[._]*.s[a-w][a-z] +[._]s[a-w][a-z] +# session +Session.vim +# temporary +.netrwhist +*~ +# auto-generated tag files +tags + + +### Linux ### +*~ + +# temporary files which can be created if a process still has a handle open of a deleted file +.fuse_hidden* + +# KDE directory preferences +.directory + +# Linux trash folder which might appear on any partition or disk +.Trash-* + + +### OSX ### +*.DS_Store +.AppleDouble +.LSOverride + +# Icon must end with two \r +Icon + +# Thumbnails +._* + +# Files that might appear in the root of a volume +.DocumentRevisions-V100 +.fseventsd +.Spotlight-V100 +.TemporaryItems +.Trashes +.VolumeIcon.icns +.com.apple.timemachine.donotpresent + +# Directories potentially created on remote AFP share +.AppleDB +.AppleDesktop +Network Trash Folder +Temporary Items +.apdisk + + +### CMake ### +CMakeCache.txt +CMakeFiles +CMakeScripts +Makefile +cmake_install.cmake +install_manifest.txt +CTestTestfile.cmake +_build +_install diff --git a/CMakeLists.txt b/CMakeLists.txt new file mode 100644 index 0000000..fa1ad6c --- /dev/null +++ b/CMakeLists.txt @@ -0,0 +1,61 @@ +################################################################################ +# Cmake directives +################################################################################ +cmake_minimum_required(VERSION 2.8) + +################################################################################ +# Project information +################################################################################ +project(libuknapsack) + +set(PROJECT_MAJOR_VERSION 1) +set(PROJECT_MINOR_VERSION 0) +set(PROJECT_PATCH_VERSION 0) +set(PROJECT_VERSION ${PROJECT_MAJOR_VERSION}.${PROJECT_MINOR_VERSION}.${PROJECT_PATCH_VERSION}) + +################################################################################ +# Dependencies +################################################################################ + +################################################################################ +# CMake +################################################################################ +set(C_FLAGS_WARNING "-Wall -pedantic") +set(C_CXX_FLAGS_DEFAULT "${C_FLAGS_WARNING} -O2") + +set(CMAKE_C_FLAGS "${C_CXX_FLAGS_DEFAULT} ${CMAKE_C_FLAGS}") +set(CMAKE_C_FLAGS_DEBUG "${CMAKE_C_FLAGS} -O0 -g -DDEBUG=1") +set(CMAKE_C_FLAGS_RELEASE "${CMAKE_C_FLAGS}") +set(CMAKE_C_FLAGS_RELWITHDEBINFO "${CMAKE_C_FLAGS_RELEASE} -g -DDEBUG=1") + +set(CMAKE_BUILD_TYPE Release CACHE STRING "default to Release") + +set(CMAKE_INSTALL_PREFIX ${CMAKE_CURRENT_SOURCE_DIR}/_install) + +################################################################################ +# Files and install +################################################################################ +set(INCLUDE_DIR ${CMAKE_CURRENT_SOURCE_DIR}/include) +set(INCLUDE_FILES + ${INCLUDE_DIR}/nem_ull.h + ${INCLUDE_DIR}/structs.h + ${INCLUDE_DIR}/common.h +) + +set(SRC_DIR ${CMAKE_CURRENT_SOURCE_DIR}/src) +set(SRC_FILES + ${SRC_DIR}/nem_ull.c + ${SRC_DIR}/common.c +) + +set(MAIN_SRC_DIR ${CMAKE_CURRENT_SOURCE_DIR}/src/main) + +include_directories (${INCLUDE_DIR}) + +add_library(nem_ull_lib STATIC ${SRC_FILES}) +add_executable(nem_ull ${MAIN_SRC_DIR}/nem_ull.c) +target_link_libraries(nem_ull nem_ull_lib) + +install(TARGETS nem_ull DESTINATION bin) +install(TARGETS nem_ull_lib DESTINATION lib) +install(FILES ${INCLUDE_FILES} DESTINATION include) diff --git a/README.md b/README.md index 1e4bbb9..57bdad8 100644 --- a/README.md +++ b/README.md @@ -6,3 +6,11 @@ Library with various solutions (optimal and approximations) for the unconstraine The **unconstrained knapsack problem** is a version of the knapsack problem where there is no constraint on the weight. Therefore, at the very least we have a bi-objective problem where we try to minimize the weight and maximize the profit. + +### Building the project + +1. Create a `_build` directory: `mkdir _build` +2. Go to the `_build` directory: `cd _build` +3. Run cmake: `cmake ..` +4. Run make install: `make install` +5. Library will be located on the `_install` folder, to go there: `cd ../_install` if you are still on the `_build` folder diff --git a/include/common.h b/include/common.h new file mode 100644 index 0000000..c61ac4d --- /dev/null +++ b/include/common.h @@ -0,0 +1,19 @@ +#ifndef _COMMON_H +#define _COMMON_H + +#include "structs.h" + +#define MIN(X,Y) ((X) < (Y) ? (X) : (Y)) +#define MAX(X,Y) ((X) > (Y) ? (X) : (Y)) + +struct data * input(char[]); +void print_data(struct data *); +void print_front(struct front_item *); +void free_data(struct data *); +void free_front(struct front_item *); +struct front_item * new_front_item(double, double, struct front_item *, struct front_item *); +double dist_items(struct item *, struct item *); +int len_front(struct front_item *); +int cmp_items_ratio(const void * a, const void * b); + +#endif diff --git a/include/nem_ull.h b/include/nem_ull.h new file mode 100644 index 0000000..fd1b829 --- /dev/null +++ b/include/nem_ull.h @@ -0,0 +1,9 @@ +#ifndef _NEM_ULL_H +#define _NEM_ULL_H + +#include "structs.h" + +struct front_item * nem_ull(struct data *); +struct front_item * nem_ull_step(struct front_item *, struct data *, int); + +#endif diff --git a/include/structs.h b/include/structs.h new file mode 100644 index 0000000..cb1bca9 --- /dev/null +++ b/include/structs.h @@ -0,0 +1,20 @@ +#ifndef _STRUCTS_H +#define _STRUCTS_H +struct item { + double p; + double w; +}; + +struct data { + long int N; + struct item * items; + double allp; + double allw; +}; + +struct front_item { + struct item i; + struct front_item * next; + struct front_item * prev; +}; +#endif diff --git a/src/common.c b/src/common.c new file mode 100644 index 0000000..92bd467 --- /dev/null +++ b/src/common.c @@ -0,0 +1,88 @@ +#include +#include +#include +#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;iN;++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; +} + +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;iN;++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){ + while(b!=NULL){ + printf("%.02f\t%.02f\n",b->i.p,b->i.w); + 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; + + return f; +} + +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; +} diff --git a/src/main/nem_ull.c b/src/main/nem_ull.c new file mode 100644 index 0000000..1bf183a --- /dev/null +++ b/src/main/nem_ull.c @@ -0,0 +1,31 @@ +#include +#include +#include "common.h" +#include "structs.h" +#include "nem_ull.h" + +int main(int argc, char * argv[]){ + struct data * d; + struct front_item * b; + + if(argc!=2){ + printf("Wrong number of arguments!\n"); + printf("Example usage: %s data_file\n",argv[0]); + return 0; + } + + d = input(argv[1]); + + clock_t t = clock(); + b = nem_ull(d); + + t = clock() - t; + printf("%f,%d\n",((float)t)/CLOCKS_PER_SEC,len_front(b)); + + //print_front(b); + + free_front(b); + free_data(d); + + return 0; +} diff --git a/src/nem_ull.c b/src/nem_ull.c new file mode 100644 index 0000000..9a6b328 --- /dev/null +++ b/src/nem_ull.c @@ -0,0 +1,99 @@ +#include +#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;iN;++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;ii.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 pmax){ + break; + } + } + + for(;l1t pmax){ + break; + } + } + + if(l0t == n){ + for(;l1tprev->next = p; + } + break; + } + + if(l1t == n){ + for(;l0tprev->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; +} -- cgit v1.2.3