In mariatreesa/RLab6: Knapsack algorithm

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)

The Usage of Package

brute_force_knapsack(X,W)

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)

dynamic_knapsack(x,W)

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)

greedy_knapsack(x,W)

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)

Speed of Algorithms

brute_force_knapsack(x,W)

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

dynamic_knapsack(x,W)

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

dynamic_knapsack(x,W,fast=TRUE)

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

greedy_knapsack(x,W)

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

greedy_knapsack(x,W,fast=TRUE) - usingRcpp

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.

mariatreesa/RLab6 documentation built on May 24, 2019, 7:35 a.m.