R/knapsack_brute.R

In harjew/lab6G3: Computer lab 5

#' Knapsack brute Problem
#' 
#' knapsack brute force, the function goes through all the possible answers.
#'
#' @param x An object with the class “data frame”, the weight of the data in the first column and price in the second column.
#' @param W Maximal capacity of the knapsack.
#' @param parallel Parallelize programming using mclapply and foreach, default is FALSE.
#' @import parallel
#' @import foreach
#' 
#' 
#' @return A list of the greatest combined value and the elements.
#' @examples 
#' x<-knapsack_data(8)
#' brute_force_knapsack(x,3500)
#' system.time(brute_force_knapsack(x,3500))
#' @export



brute_force_knapsack<-function(x,W,parallel=FALSE){
  stopifnot(is.data.frame(x))
  stopifnot(is.numeric(W),W>0)
  if(sum(x$w)<=W){
    return(list(value=sum(x$v),elements=1:length(x[,1])))
  }
  else if(min(x$w)>W){
    return(list(value=0,elements=0))
  }
  else{
  orginal<-x
  x<-x[order(-x[,1]),]
  x<-x[x[,1]<=W,]
  n<-length(x[,1])
  maximum<-0
  k<-2
  best_items<-vector()
  if(parallel==FALSE){
  repeat{
    weig<-data.frame(utils::combn(x[,1],k))
    val<-data.frame(utils::combn(x[,2],k))

    value_now<-colSums(val)
    weights_now<-colSums(weig)
    
    
    weights_l<-which(weights_now<=W)
    if(length(weights_l)>0){
      values<-value_now[weights_l]
      maximum<-max(values)
      Temporarily<-which((values)==maximum)
      maximum_values<-weights_l[Temporarily]
      maximum_whights<-weig[,maximum_values]
      l<-1
      repeat{
        best_items[l]<-which(x[,1]==maximum_whights[l])
        l<-l+1
        if(l>k){
          break
        }
      }
    }
    k<-k+1
    if(k>n){
      break
    }
  }
  }
  else if(parallel==TRUE){
    foreach::foreach(k=2:n, .combine=rbind)%do%{
      weig<-data.frame(utils::combn(x[,1],k))
      val<-data.frame(utils::combn(x[,2],k))
      
    
      weights_now<-unlist(parallel::mclapply(weig,sum))
      value_now<-unlist(parallel::mclapply(val,sum))
      
      weights_l<-which(weights_now<=W)
      if(length(weights_l)>0){
        values<-value_now[weights_l]
        maximum<-max(values)
        Temporarily<-which((values)==maximum)
        maximum_values<-weights_l[Temporarily]
        maximum_whights<-weig[,maximum_values]
        l<-1
        repeat{
          best_items[l]<-which(x[,1]==maximum_whights[l])
          l<-l+1
          if(l>k){
            break
          }
        }
    }
    }
  }
  my_list<-list()
  my_list$value<-maximum
  my_list$elements<-which(orginal$w%in%maximum_whights)
  return(my_list)
  }
}