R/greedy_knapsack.R

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

luid <- "rabsh696 & samza595"
name <- "rabnawaz & saman"
#'Knapsack problem solve with greedy algorithm.
#'@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
#' @return return list which have maxValue and and item number of elemnts that knapsack have in it
#'@details dynamic programming algo going through all possible alternatives and return the maximum value found.
#'@references
#'\url{https://en.wikipedia.org/wiki/Knapsack_problem#Greedy_approximation_algorithm}
#'@export


greedy_knapsack <- function(x, W)
{
  
  if(!(is.data.frame(x)) || !(is.numeric(W)) || W < 0 )
    stop()
  
  x$density <- round(x$v / x$w, digits = 3) #calculte density
  x <- x[order(x$density , decreasing = TRUE),] #sort the data on base of density values
  
  #declear empty vector
  Item_list <- c()
  #declear variable
  sum_of_weight <- 0
  total_value <- 0
  k <- 1
  
  repeat
  {
    if( sum_of_weight + x[k,1] < W  )
    {
      total_value <- total_value + x[k,2]
      sum_of_weight <- sum_of_weight + x[k,1]
      Item_list[k] <- as.numeric(rownames(x[k,]))
      k <- k + 1
    }
    else
      break
  }
  
  return(list(value=round(total_value), elements=Item_list))
  #return a list of value and items
}