R/brute_force_knapsack.R

In rjkhan/RCourse-lab6: Knapsack problem solved by different alogrithms

luid <- "rabsh696 & samza595"
name <- "rabnawaz & saman"
#'Knapsack probelm with brute force algorithm
#'@name brute_force_knapsack
#'@author rabnawaz & saman
#'@param x is a data frame hiaving 2 column 'w' and 'v' where w is weight if items and v is the value of item
#'@param W capacity of knapsack i.e total weight that knapsack can contain in it
#'@param parallel default it set to FALSE , if you have mac/linux or windows you can set it TRUE
#'@return return list which have maxValue and and item number of elemnts that knapsack have in it
#'@description brute force algo going through all possible alternatives and return the
#'maximum value found with element with complexity .
#'
#'@references
#'\url{https://en.wikipedia.org/wiki/Knapsack_problem}
#'@export

library(parallel) #load parallel package
library(combinat) #load comnination package


brute_force_knapsack <- function(x, W, parallel = FALSE){

  if(!(is.data.frame(x)) || !(is.numeric(W)) || W < 0 )
    stop()
  
  #initialization List
  w_v_combination <- list() #combination list
  item_values <- list() #item value list
  if( parallel == TRUE )
  {
    #if paralel is true than run on mulit cores
    if(Sys.info()["sysname"] %in% c("Windows","linux","Darwin"))
    {
    
      cores = parallel::detectCores() #fetch number of cores
      w_v_combination <- unlist(parallel::mclapply(1:nrow(x),
                                    function(k) #assign a task to each core
                                    {
                                      combinat::combn(rownames(x), m = k, simplify = FALSE, fun = as.numeric)
                                    },
                              mc.cores = cores),
                     recursive = FALSE, use.names = FALSE)

      #sum the item result of each core
      item_values <- parallel::mclapply(w_v_combination, function(w_v_combination){
                              ifelse(sum(x[w_v_combination,1]) <= W,
                                     sum(x[w_v_combination,2]),0
                                     )
                            },
                          mc.cores = cores)

    }
    else
    {
      stop("machine is not competiable")
    }
  }
  else
  {
    # simple normal brute force
    w_v_combination <- unlist(lapply(1:nrow(x), function(k){
                            combinat::combn(rownames(x), m = k, simplify = FALSE, fun = as.numeric)}),
                            use.names = FALSE,recursive = FALSE)
    item_values <- lapply(w_v_combination, function(w_v_combination)
      {
        ifelse(sum(x[w_v_combination,1]) <= W , sum(x[w_v_combination,2]),0)
      }
                          )
  }

  max_value_index <- which.max(item_values) #get a max value from list
  selected_item_list <- w_v_combination[[max_value_index]] #select items

  return(list(value=round(item_values[[max_value_index]]),elements = selected_item_list))
  #return a list of value and items
}