summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--.gitignore67
-rw-r--r--CMakeLists.txt61
-rw-r--r--README.md8
-rw-r--r--include/common.h19
-rw-r--r--include/nem_ull.h9
-rw-r--r--include/structs.h20
-rw-r--r--src/common.c88
-rw-r--r--src/main/nem_ull.c31
-rw-r--r--src/nem_ull.c99
9 files changed, 402 insertions, 0 deletions
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 <stdlib.h>
+#include <stdio.h>
+#include <math.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;
+}
+
+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){
+ 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 <stdio.h>
+#include <time.h>
+#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 <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;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-22 06:51:36 +0000