R/bruteForce.R

In nourqweder/AdvRLab6: The knapsack package

#' @title knapsack problem by brute_force method
#' @name  brute_force_knapsack
#' @param x A takes a data.frame cx with two variables v and w
#' @param W The variable W is the knapsack size.
#' @param parallel in brute force knapsack() that is FALSE by default (so it works with the test
#' suite where we have not specifed the argument parallel). If set to TRUE, the function should parallelize
#' over the detected cores.
#' $elements which indicates which row objects in data.frame x was put in the knapsack.
#' @return the maximum knapsack 
#' @examples
#' data(knapsack_objects)
#' 
#' brute_force_knapsack(x = knapsack_objects[1:8,], W = 3500)
#' brute_force_knapsack(x = knapsack_objects[1:12,], W = 3500)
#' brute_force_knapsack(x = knapsack_objects[1:8,], W = 2000)
#' brute_force_knapsack(x = knapsack_objects[1:12,], W = 2000)
#' @importFrom utils head
#' @references \url{http://en.wikipedia.org/wiki/Knapsack_problem}
#' @import parallel
#' @export
#' 

library(parallel)
brute_force_knapsack <-function(x , W, parallel= FALSE)
{
  
  stopifnot(names(x) == c("w","v"), is.data.frame(x),W > 1)
  
  lWeight <- list()
  lValue <- list()
  lRowNo <- list()
  
  if (parallel == FALSE) {
    #generate all available situation
    #get a list of all valid weight
    #get the max value according the pervious list
    #get the index of value list
    #  x <- head(knapsack_objects,n = 3)
    #W <-4900
    
    for (i in 1:nrow(x)) {
      # ?combn; Generate All Combinations of n Elements, Taken m at a Time
      lWeight[[i]] <- combn(x$w, i, sum)
      #print(paste("w",lWeight[[i]]))
      lValue[[i]] <- combn(x$v, i, sum)
      #print(paste("v", lValue[[i]]))
      lRowNo[[i]] <- combn(rownames(x), i, paste, collapse="")
      #print( paste("row",lRowNo[[i]]))
    }
    weightList <- unlist(lWeight)
    valueList <- unlist(lValue)
    rowList <- unlist(lRowNo)
    validWegiht<- which(weightList < W)
    
    validValue<- valueList[validWegiht]
    
    maxValue <- max(validValue)
    validRowNo <- which(valueList == maxValue)
    #just to decombin "13" -> "1" "3"
    #strsplit(rowList[validRowNo],"")
    validElemntsList <- as.numeric(unlist(strsplit(rowList[validRowNo],"")))
    #gathering value and elements
    result <- list(value = round(maxValue), elements = validElemntsList)
    
  }
  else if (parallel == TRUE)
  {
    cores <- parallel::detectCores() - 1  #check the number of cores on the computer
    cluster <- parallel::makeCluster(cores) #to set up the cluster
    clusterExport(cluster, c("x"), envir = environment())
    
    clusterEvalQ(cluster, {
      library(parallel)
    })
    
    lRowNo <- parLapplyLB(cluster, 1:nrow(x), fun =  function(y) {
      combn(rownames(x) , y , paste, collapse = "")
    })
    lWeight <- parLapplyLB(cluster, 1:nrow(x), fun =  function(y) {
      combn(x$w , y, sum)
    })
    Values <- parLapplyLB(cluster,1:nrow(x), fun =  function(y) {
      combn(x$v , y , sum)
      
    })
    stopCluster(cluster) #to shutdown cluster
    rowList <- unlist(lRowNo) # creating vectors by unlisting
    weightList <- unlist(lWeight)
    valueList <- round(unlist(Values))
    
    validWegiht <- which(weightList < W) #using which to get the indexes of weight
    validValues <- valueList[validWegiht]
    maxValue <- max(validValues)
    
    validRowNo <- which(valueList == maxValue) # using which to get the maximum Value
    validElemntsList <- as.numeric(unlist(strsplit(rowList[validRowNo],"")))
    
    result <- list(value = maxValue, elements = validElemntsList) #creating a list
  }
  return(result)
}


#lineprof library for profileing 
# system.time(brute_force_knapsack(x = knapsack_objects[1:16,], W = 3500))
# user  system elapsed 
# 0.45    0.00    0.46 

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