R/brute_force_ksack.R

In fbarulli/lib6af: Connecting R to an API

#'@title brute force 
#'@description brute force implementation
#'@name lib6af
#'@docType package 
#'@importFrom utils, combn
#'@export brute_force_knapsack 
#acknowledgement John Lacin, Erick Herwin, Simon Jonsson
#library(lineprof)
library(utils)
brute_force_knapsack <- function(x, W, parallel = FALSE) {
  stopifnot(W > 0 &
              is.data.frame(x) &
              is.vector(x$v) &
              is.vector(x$w) &
              length(x$w) == length(x$v))
  n <- length(x[[1]])
  v <- x$v
  w <- x$w
  best <- replicate(n, 0)
  
  if (parallel) {
    # Checks each row of M if the weight is allowed
    res_vec <- parallel::mclapply(1:(2^n-1), function(x, w, v, W) {
      m <- intToBits(x)
      if (sum(w[m == 1]) <= W) {
        return(m)
      }
    }, w, v, W, mc.cores = parallel::detectCores())
    
    # Takes all the allowed rows and calculates which one has the best value
    lapply(Filter(Negate(is.null), res_vec), function(m) {
      if (sum(v[m == 1]) > sum(v[best == 1])) {
        best <<- m
      }
    })
  } else {
    # Goes through each row of M to find the optimal value
    lapply(1:(2^n-1), function(x) {
      m <- intToBits(x)
      if (sum(v[m == 1]) > sum(v[best == 1]) & sum(w[m == 1]) <= W) {
        best <<- m
      }
    })
  }
  
  res <- list(value = sum(v[best == 1]), elements = which(best == 1))
  return(res)
}