In Elmahi92/knpa: The knapsack package

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

This package implements three different algorithms for solving the knapsack problem.

Load the package and generate sample data

Start by loading the package and generate some sample data.

library(knpa)

RNGversion(min(as.character(getRversion()),"3.5.3"))
set.seed(42, kind = "Mersenne-Twister", normal.kind = "Inversion")
n <- 2000
knapsack_objects <- data.frame(
  w=sample(1:4000, size = n, replace = TRUE),
  v=runif(n = n, 0, 10000)
  )

brute_force_knapsack()

brute_force_knapsack() finds and calculates the total value of all possible subsets whose weight is less or equal to the knapsack’s maximum capacity, and then returns the subset with the largest value. The algorithm returns the best, possible solution but can be very time-consuming when handling large data sets.

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

The algorithm takes about 5 seconds to run for n=16 objects.

If the argument parallel is set to TRUE, the brute_force_knapsack()-function will parallize over the detected cores.

brute_force_knapsack(x = knapsack_objects[1:16,], W = 3500, parallel = TRUE)

By using parallel=TRUE, the algorithm takes about 2.5 seconds to run for n=16 objects.

dynamic_knapsack()

dynamic_knapsack() finds the best, possible solution to the knapsack problem. This algorithm is more time-efficient than the brute_force_knapsack()-method.

dynamic_knapsack(x = knapsack_objects[1:500,], W = 3500)

The algorithm takes about 95 seconds to run for n=500 objects.

greedy_knapsack()

greedy_knapsack() returns an approximation for the knapsack problem. However, the algorithms do not always return the best, possible solution to the problem.

greedy_knapsack(x = knapsack_objects[1:8,], W = 3500)

The algorithm takes about 2.5 seconds to run for n=1000000 objects.

Profiling and optimizing the code

By profiling the code with profvis, the following bottlenecks are found in the following rows:

bute_force_knapsack():

if( sum(x[which(intToBits(i) == 1), 1]) <= W && sum(x[which(intToBits(i) == 1), 2]) > res[["value"]] )

dynamic_knapsack():

if(x[i,1] > j)

and:

m[i+1,j] <- max(m[i,j], m[i, j-x[i,1]] + x[i,2])

In the greedy_knapsack()-function no bottle necks are found.

The brute_force_knapsack()-function can be optimized by changing the line:

if( sum(x[which(intToBits(i) == 1), 1]) <= W & sum(x[which(intToBits(i) == 1), 2]) > res[["value"]] )

to:

if( sum(x[which(intToBits(i) == 1), 1]) <= W && sum(x[which(intToBits(i) == 1), 2]) > res[["value"]] )

&& means that the if statement first checks if the first condition is TRUE or FALSE, and if it is not the second condition will not be checked which means that the number of calculations needed are reduced. This reduces the time with over 50%.

By implementing parallelization in the brute_force_knapsack() the time is reduced by approximately 50%.

Elmahi92/knpa documentation built on Dec. 17, 2021, 6:28 p.m.