lab6: Knapsack Problem Algorithms

##'Bruteforce, dynamimc programming and greedy algorithm for the knapsack problem
##'
##'@name knapsack_class
##'@title Knapsack Algorithms
##'
##'@author Mahmood Siddique
##'@rdname knapsack_class
##' @description  This class will generate a dataset for knapsack in initialized function 
##' @examples
##' \dontrun{
##'obj <- knapsack_class$new()
##' }
##'@rdname knapsack_brute_force
##'@param ks_dataset is a data.frame generated by initialzed function which contain variables W and V, weights and values
##'@param ks_size is the total size of the knapsack
##'@details This algorithm gives all possbile values with good accuracy, and also gives the maximum value for the knapsack
##'@return  This function will return a list of selected elements and their total values
##'@examples
##'\dontrun{
##'obj$brute_force_knapsack(obj$ks_dataset[1:8,],3500)
##'obj$brute_force_knapsack(obj$ks_dataset[1:12,],3500)
##'obj$brute_force_knapsack(obj$ks_dataset[1:8,],3500,Paral = TRUE)
##'}
##'@rdname knapsack_dynamic
##'@details This algorithm gives all possbile values with good accuracy, and also gives the maximum value for the knapsack
##'@return  This function will return a list of selected elements and their total values
##'@examples
##'\dontrun{
##'obj$knapsack_dynamic(obj$ks_dataset[1:8,],3500)
##'obj$knapsack_dynamic(obj$ks_dataset[1:12,],3500)
##'obj$knapsack_dynamic(obj$ks_dataset[1:8,],2000)
##'}
##'@rdname greedy_knapsack
##'@details This algorithm gives all possbile values with good accuracy, and also gives the maximum value for the knapsack
##'@return  This function will return a list of selected elements and their total values
##'@examples
##'\dontrun{
##'obj$greedy_knapsack(obj$ks_dataset[1:8,],3500)
##'obj$greedy_knapsack(obj$ks_dataset[1:12,],3500)
##'obj$greedy_knapsack(obj$ks_dataset[1:8,],2000)
##'}
##'@references
##'\url{https://en.wikipedia.org/wiki/Knapsack_problem}
##'@export knapsack_class
##'@import devtools
##'@import RcppAlgos
##'@import profvis


 knapsack_class <- setRefClass("knapsack_class", fields = list(ks_dataset = "data.frame"),
                                                              
                              methods = list(
                                
                                initialize = function(){
              
                                  suppressWarnings(RNGkind(sample.kind = "Rounding"))
                                  set.seed(42)
                                  n_items <- 2000
                                  ks_dataset <<-data.frame(
                                    w =sample(1:4000, size = n_items, replace = TRUE),
                                    v = runif(n = n_items, 0, 10000))
                                  
                                  # ks_dataset <<-data.frame(
                                  #   w <-sample(1:10, size = 4, replace = TRUE),
                                  #   v <- runif(n = 4, 0, 10))
                                  #ks_dataset <<- data.frame(w = c(2,3,4,5),v=c(1,2,5,6))
                                  
                                },
                                
                                brute_force_knapsack = function(ks_df,ks_size,Paral =FALSE){
                                 
                                  names(ks_df) <-c("W","V")   
                                  all_w_positive <- sum(ks_df$W>0)
                                  all_v_positive <- sum(ks_df$V>0)
                                  total_length <- nrow(ks_df)
                                  stopifnot(is.data.frame(ks_df) & all_v_positive == total_length & all_w_positive == total_length,is.numeric(ks_size),ks_size>0)
                                  
                                  i <- 2
                                  total_value <- 0     
                                  item_included <- NULL
                                  weights<- NULL
                                  values<- NULL
                                  
                                  for (i in 1:nrow(ks_df))
                                  {
                                    if(Paral == FALSE)
                                    {
                                      w_combination <- as.data.frame(combn(ks_df[,1], i))
                                      v_combination <- as.data.frame(combn(ks_df[,2], i))
                                    }
                                    else
                                    {
                                      w_combination <- as.data.frame(RcppAlgos::comboGeneral(ks_df[,1],i,Parallel = TRUE,nThreads = 8))#,constraintFun = "sum",comparisonFun = c("<="),limitConstraints = ks_size))
                                      w_combination <- t(w_combination)
                                      v_combination <- as.data.frame(RcppAlgos::comboGeneral(ks_df[,2],i,Parallel = TRUE,nThreads = 8))#,constraintFun = "sum",comparisonFun = c("<="),limitConstraints = ks_size))
                                      v_combination <- t(v_combination)
                                    }
                                    w_vector <- colSums(w_combination)
                                    v_vector <- colSums(v_combination)
                                    weights_index <- which(w_vector<=ks_size)
                                    val_weight <- NULL

                                    
                                    if(length(weights_index) != 0)
                                      { 
                                        values <- v_vector[weights_index]
                                        total_value <- max(values)
                                        temp <- which((values)==total_value)
                                        val_weight_index <- weights_index[temp]
                                        val_weight <- w_combination[, val_weight_index]
                                        
                                        for (j in 1:i) 
                                          {
                                          item_included[j]<-which(ks_df[,1]==val_weight[j])
                                          }
                                      }
                                  }
                                  
                                  return(list(value=round(total_value),elements=item_included))
                                },
                                
                                knapsack_dynamic = function(ks_df,ks_size){
                                
                                  names(ks_df) <-c("W","V")   
                                  all_w_positive <- sum(ks_df$W>0)
                                  all_v_positive <- sum(ks_df$V>0)
                                  total_length <- nrow(ks_df)
                                  ks_df <- rbind(c(0,0),ks_df)
                                  
                                  stopifnot(is.data.frame(ks_df) & all_v_positive == total_length & all_w_positive == total_length)
                                  
                                  n_items <- total_length+1
                                  ks_size <- ks_size+1
                                  
                                  # Creating Matrix of size W x elements
                                  # temp_df1=c()
                                  # for (i in 1:(ks_size*n_items)) 
                                  #   temp_df1[i] = 1
                                  # dim(temp_df1) = c(n_items,ks_size)
                                  # temp_df <- as.data.frame(temp_df1)
                                  
                                  temp_df <- as.data.frame(matrix(1,nrow = n_items,ncol = ks_size))
                                  
                                  
                                  # calculating knapsack matrix
                                  for (i in 1:(n_items)) {
                                    for (j in 1:ks_size) {
                                      if(i==1 | j ==1)
                                        temp_df[i,j] <- 0
                                      else if(ks_df[i,1] < j)
                                      {
                                        temp_i <- i-1
                                        temp_j <- (j-ks_df[i,1])
                                        temp_df[i,j] <- max((ks_df[i,2]+temp_df[temp_i,temp_j]),temp_df[temp_i,j])
                                      }
                                      else
                                      {
                                        temp_df[i,j] <- temp_df[(i-1),j]
                                      }
                                    }
                                  }
                                  
                                  # collecting the selected items from knapsack matrix
                                  i <- n_items
                                  j <- ks_size
                                  k<-1
                                  item_included <- c()
                                  total_weight <- 0
                                  total_value <- 0
                                 
                                   while (i>1 & j>1) 
                                  {
                                    if(temp_df[i,j] == temp_df[i-1,j])
                                    {
                                      i <- i-1
                                    }
                                    else
                                    {
                                      item_included[k] <- i-1
                                      k<-k+1
                                      total_value <- total_value + ks_df[i,2]
                                      j <- j-ks_df[i,1]
                                      i <- i-1
                                    }
                                  }
                                  result <- list(value = round(total_value),elements = sort(item_included))#, weight = total_weight)
                                  return(result)
                                },
                                
                                greedy_knapsack = function(ks_df,ks_size){
                                
                                  names(ks_df) <-c("W","V")   
                                  all_w_positive <- sum(ks_df$W>0)
                                  all_v_positive <- sum(ks_df$V>0)
                                  total_length <- nrow(ks_df)
                                  stopifnot(is.data.frame(ks_df) & all_v_positive == total_length & all_w_positive == total_length,is.numeric(ks_size),ks_size>0)
                                  
                                  temp_df <- ks_df
                                  temp_vw <- NULL
                                  index_vector <- NULL
                                  store_index <- NULL
                                  temp_x <- NULL
                                  temp_weight <- ks_size

                                  for(i in 1:nrow(ks_df))
                                  {
                                    temp_vw[i] <- ks_df[i,2]/ks_df[i,1]
                                    index_vector[i] <- 0
                                    store_index[i] <- i
                                  }

                                  temp_df <- cbind(temp_df,temp_vw,store_index)
                                  temp_df <- temp_df[order(temp_vw,decreasing = TRUE),]
                                  selected_elements <-NULL
                                  temp_var <- 1
                                  
                                  for(i in 1:length(temp_vw))
                                  {
                                    if(temp_weight >= temp_df[i,1])
                                    {
                                      index_vector[i] <- 1
                                      temp_weight <- temp_weight - temp_df[i,1]
                                      selected_elements[temp_var] <- temp_df[i,4]
                                      temp_var <- temp_var + 1
                                    }
                                  }
                                  temp_var <- 0
                                  temp_df <- cbind(temp_df,index_vector)
                                  
                                  total_value <- sum(ks_df$V[selected_elements])

                                  return(list(value = total_value,elements = selected_elements))
                                  
                                },
                                
                                knapsack_brutefore_profiling = function(ks_df,ks_size,para = FALSE)
                                 {
                                   if(para == FALSE)
                                   bfp <- profvis::profvis(brute_force_knapsack(ks_df,ks_size))
                                  else
                                    bfp <- profvis::profvis(brute_force_knapsack(ks_df,ks_size,Paral = TRUE))
                                  
                                    bfp
                                   },
                                knapsack_dynamic_profiling = function(ks_df,ks_size)
                                {
                                    dpp <- profvis::profvis(knapsack_dynamic(ks_df,ks_size))
                                  dpp
                                },
                                knapsack_greedy_profiling = function(ks_df,ks_size)
                                {
                                   ghp <- profvis::profvis(greedy_knapsack(ks_df,ks_size))
                                 ghp
                                }
                              
                                ))