R/greedy_knapsack.R

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

#'  Greedy approximation algorithm for solving knapsack problem
#' 
#' \code{greedy_knapsack(x, W)} returns  the solution for knapsack problem
#'     using Greedy approximation algorithm.
#' 
#' This function solves the Knapsack probem using Greedy approximation 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.
#'  
#'  
#'  
#' @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
#'  greedy_knapsack(data.frame(w=c(3660,3749,1145,3322),v=c(9899,4384,6999,8890)),W =3500)
#'  
#' @references \url{https://en.wikipedia.org/wiki/Knapsack_problem#Greedy_approximation_algorithm}  
#' @export


greedy_knapsack <- function(x, W){
  
  stopifnot(is.data.frame(x))
  stopifnot(names(x) == c("w", "v"))
  stopifnot(x[] > 0)
  stopifnot(is.numeric(W), length(W) == 1, W > 0)
  
  
  n <- nrow(x)
  
  ValPerW <- x$v / x$w
  
  sortedValPerW <- sort(ValPerW, decreasing = TRUE, index.return = TRUE)
  
  sorted_w <- x$w[sortedValPerW$ix]
  sorted_v <- x$v[sortedValPerW$ix]
  
  total_w <- 0
  total_v <- 0
  elements <-c()
  
  i <- 1
  while(total_w <= W & i <= n){
    
    if((sorted_w[i] + total_w) <= W){
      
      total_w <- sorted_w[i] + total_w
      total_v <- sorted_v[i] + total_v
      elements <-c(elements,i)
      i <- i + 1
    }else{break}
    
  }
  
  return(list(value = round(total_v), elements = sortedValPerW$ix[elements]))
}