In fbarulli/lib6af: Connecting R to an API

Introduction

Lib6af consists of a time optimization problem, using knapsack as the target algorithm. Using several methods, such as the brute force method, dynamic programming and greddy heuristics.

Brute Force

The brute force method delivers a guaranteed correct answer by calculating all possible values. With a complexity of O(2^n), all combinations are calculated.

Below is the time it takes to run a knapsack problem of n=16.

brute_force_knapsack(x = knapsack_objects[1:16, ], W = 2000)

$value
[1] 15428

$elements
[1] "3 8"

user  system elapsed 
  0.019   0.000   0.020 

Dynamic Programming Knapsack

The dynamic programing apporach, we iterate all possible weight values. The complexity of this method is O(Wn).

Below is the time it takes to run an algorythm of n=500 for the Dynamic programming:

knapsack_dynamic(x = knapsack_objects[1:12,], W=3500)
$value
[1] 16770.38

$elements
[1] 5 8

user  system elapsed 
  0.028   0.002   0.031 

Greedy Heuristic

The final approach of the different methodologies is the Greedy heuristic. Although it does not provide an exact result, it reduces the computational time due to the complexity, O(nlogn).

n<-1000000
greedy_knapsack(x = knapsack_objects[1:1200,], W = 2000)

   user  system elapsed 
  0.018   0.000   0.017

Parallelize Brute Force

Taking advantage of multiple core computers, parallelize is able to reduce the computational time of the algorythm. Below is the difference between using parallelize argument as TRUE and as FALSE in the brute force algorythm.

system.time(brute_force_knapsack(x = knapsack_objects[1:8,], W = 3500))
user  system elapsed 
0.003   0.000   0.002 


user  system elapsed 
0.021   0.000   0.021 

fbarulli/lib6af documentation built on May 7, 2019, 2:55 a.m.