In boxizhang/boxknapsack: Three different algorithm for knapsack problem

knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>"
)

The boxknapsack package contains three different algorithm to solve the knapsack problem: - brute force - dynamic programming - greedy approach

The data we will use is generated in the following way:

set.seed(42)
n <- 2000
knapsack_objects <-
  data.frame(
    w=sample(1:4000, size = n, replace = TRUE),
    v=runif(n = n, 0, 10000)
  )

library(boxknapsack)

Brute force search

Question How much time does it takes to run the algorithm for n = 16 objects?

Question What performance gain could you get by parallelizing brute force search?

brute_force_knapsack(x = knapsack_objects[1:16,], W = 3500)
st <- system.time(brute_force_knapsack(x = knapsack_objects[1:16,], W = 3500))
st
brute_force_knapsack(x = knapsack_objects[1:16,], W = 3500, parallel = TRUE)
st <- system.time(brute_force_knapsack(x = knapsack_objects[1:16,], W = 3500, parallel = TRUE))
st

The time is measured by system.time(). By using parallelizing brute force, the user time is saved around 24 fold.

Question How much time does it takes to run the algorithm for n = 500 objects? Dynamic programming

knapsack_dynamic(x = knapsack_objects[1:16,], W = 2000)
system.time(knapsack_dynamic(x = knapsack_objects[1:16,], W = 2000))

knapsack_dynamic(x = knapsack_objects[1:500,], W = 2000)
system.time(knapsack_dynamic(x = knapsack_objects[1:16,], W = 2000))

When n = 500, it seems the time uesd is even less.

Question How much time does it takes to run the algorithm for n = 1000000 objects? Greedy heuristic

set.seed(42)
n <- 1000000
knapsack_objects <-
 data.frame(
   w=sample(1:4000, size = n, replace = TRUE),
   v=runif(n = n, 0, 10000))
system.time(greedy_knapsack(x = knapsack_objects[1:1000000,], W = 2000))