R/brute_force_knapsack.R

In mpirmoradiyan/knapsack: Three approaches to deal with knapsack problem

#' Brute force algorithm for solving knapsack problem
#' 
#' \code{brute_force_knapsack(x, W)} returns  the solution for knapsack problem
#'     using brute force algorithm.
#' 
#' This function solves the Knapsack probem using brute force approach. 
#' The knapsack problem is a discrete optimization problem where we have a knapsack that can take a
#' limited weight W and we want to fill this knapsack with a number of items i = 1, 2 ,...,n; each with a
#' weight(w) and a value(v). The goal is to find the knapsack with the largest value of the elements added
#' to the knapsack.
#' 
#' @param x A data.frame with two variables ("w" , "v"). Every observation (row)
#'   in this data frame is an item with a weight (w) and a value (v).
#'  
#' @param W A numeric scalar which is the maximum capacity of the knapsack.
#'  
#' @param parallel If TRUE, the "parallel" package will be implemented to parallelize the function. 
#'  
#' @return  A list with names \code{$value}, indicating maximum value of the items picked
#'  into the the knapsack , and \code{$elements} which states which items (rows) in data.frame 
#'  were selected out to put into the knapsack.
#'  
#'  
#' @examples
#'  brute_force_knapsack(data.frame(w=c(3660,3749,1145,3322),v=c(9899,4384,6999,8890)),W =3500)
#'  
#' @references \url{http://en.wikipedia.org/wiki/Knapsack_problem}  
#' @import parallel
#' @import utils
#' @import microbenchmark
#' @import profvis
#' @export

brute_force_knapsack <- function(x, W, parallel = FALSE){
  
  stopifnot(is.data.frame(x))
  stopifnot(names(x) == c("w", "v"))
  stopifnot(x[] > 0)
  stopifnot(is.numeric(W), length(W) == 1, W > 0)
  
  
  # size of the input data frame, n:
  n <- nrow(x)
  
  if(parallel == FALSE){
    
    best_weight <- 0
    best_value <- 0
    elements <- NA
    i = 1
    while (i <= 2 ^ n - 1) {
      binary <- intToBits(i)
      index <- which(binary == 1)
      
      
      total_w = 0
      total_v = 0
      
      for (j in 1:length(index)) {
        total_w = total_w + x$w[index[j]]
        total_v = total_v + x$v[index[j]]
      }
      if (total_w <= W) {
        if (total_v > best_value) {
          best_weight <- total_w
          best_value <- total_v
          elements <- index
          i = i + 1
        } else{
          i = i + 1
        }
        
      } else{
        i = i + 1
      }
      
    }
    return(list(value = round(best_value), elements = elements))
    
  }else{
    
    x$id <- 1:n
    allcores = detectCores()
    cluster = makeCluster(allcores)
    
    
    all_elements <- unlist(parLapply(cluster, 1:nrow(x), function(i){combn(x$id, i, toString)}))
    
    all_weight_comb <- unlist(parLapply(cluster, 1:nrow(x), function(i){combn(x$w, i, sum)}))
    all_value_comb <- unlist(parLapply(cluster, 1:nrow(x), function(i){combn(x$v, i, sum)}))
    
    
    best_value <- max(all_value_comb[which(all_weight_comb <= W)])
    best_element <- all_elements[which(all_value_comb == best_value)]
    elements = as.integer(unlist(strsplit(best_element, ",")))
    
    return(list(value = round(best_value), elements = elements))
    stopCluster(cluster)
    
    
  }
  
}