R/greedy_knapsack.R

Defines functions greedy_knapsack

Documented in greedy_knapsack

#' Greedy Heuristic
#'
#' @param x \code{data.frame} containing objects with weights \code{w} and values \code{v} as columns.
#' @param W max weight of the knapsack 
#'
#' @return a list with at least 50 % of the max value and corresponding elements
#' @importFrom magrittr %>%
#' @export
#'
#' @examples
#' data(knapsack_objects)
#' greedy_knapsack(x = knapsack_objects[1:8,], W = 3500)
#' @references \url{https://en.wikipedia.org/wiki/Knapsack_problem#Greedy_approximation_algorithm}
greedy_knapsack <-
function(x, W){
  stopifnot("x is not a data.frame." = is.data.frame(x))
  stopifnot("data.frame must contain exactly two variables" = ncol(x)==2)
  stopifnot("data.frame must contain the two variables v and w" = all(colnames(x) %in% c("v","w")))
  stopifnot("v and w must be positive values" = all(x[,1:2]>0 ))
  stopifnot("W must be a positive value" = W >= 0)
  # Main
  frac <- x$v/x$w
  df <- data.frame(object = 1:length(frac), frac = frac, v = x$v, w = x$w)
  # Sort in decreasing order
  df_sorted <- df %>% 
    dplyr::arrange(desc(frac))
  S1 <- df_sorted[cumsum(df_sorted$w) <= W,]
  S2 <- df_sorted[cumsum(df_sorted$w) > W,][1,]
  if(sum(S1$v) >= S2$v){
    value <- sum(S1$v)
    elements <- S1$object
  }else{
    if(S2$w <= W){
      value <- round(S2$v)
      elements <- S2$object
    }
  }
  return(list(value = round(value), elements = elements))
}
sofiejorgensen/knapsack documentation built on Oct. 16, 2020, 2:51 a.m.