library(knapsack)
The goal of knapsack package is to find the combination of objects with maximum value without exceeding a given weight.
This package has the solutions for Knapsack problem using three algorithms. 1. Brute Force Algorithm 2. Dynamic Algorithm 3. Greedy Algorithm
The object used in knapsack_objects. This is a data frame with 2000 rows and 2 columns. The column data cointains the weight and value of objects.
set.seed(42) n = 1000000 knapsack_objects <- data.frame( w=sample(1:4000, size = n, replace = TRUE), v=runif(n = n, 0, 10000) )
head(knapsack_objects)
This algorithm can be invoked as given below:
brute_force_knapsack(x = knapsak_objects[1:8,],W=2000)
Output
brute_force_knapsack(x = knapsack_objects[1:8,],W=2000)
This algorithm can be invoked as given below:
dynamic_knapsack(x = knapsack_objects[1:8,],W=2000)
Output
dynamic_knapsack(x = knapsack_objects[1:8,],W=2000)
This algorithm can be invoked as given below:
greedy_knapsack(x = knapsack_objects[1:8,],W=2000)
Output
greedy_knapsack(x = knapsack_objects[1:8,],W=2000)
Time taken to run the algorithm for 16 objects
starttime <- Sys.time() brute_force_knapsack(x = knapsack_objects[1:16,],W=2000) endtime <- Sys.time() bruteforce_time = endtime - starttime
bruteforce_time
Time taken to run the algorithm for 500 objects
starttime <- Sys.time() dynamic_knapsack(x = knapsack_objects[1:500,],W=3500) endtime <- Sys.time() dynamic_time = endtime - starttime
dynamic_time
Time taken to run the algorithm for 500 objects using Rcpp
starttime <- Sys.time() dynamic_knapsack(x = knapsack_objects[1:500,],W=3500,fast = TRUE) endtime <- Sys.time() dynamic_time = endtime - starttime
dynamic_time
Time taken to run the algorithm for 1000000 objects
starttime <- Sys.time() greedy_knapsack(x = knapsack_objects[1:1000000,],W=3500) endtime <- Sys.time() greedy_time = endtime - starttime
greedy_time
Time taken to run the algorithm for 1000000 objects using Rcpp
starttime <- Sys.time() greedy_knapsack(x = knapsack_objects[1:1000000,],W=3500, fast = TRUE) endtime <- Sys.time() greedy_time = endtime - starttime
greedy_time
We can clearly observe the advantage of using cpp function in above two examples. The code that used cpp in both Greedy Algorithm and Dynamic algorithm takes less time compared to the normal R algorithms.
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.