R/greedy_knapsack.R

In abhijeet16/shazam: Knapsack Problem

#' Knapsack Problem - Greedy Heuristic
#' @param x a data frame containing weight and values
#' @param W maximum weight
#' @title Knapsack Problem
#' @name Knapsack
#' @details knapsack problem based on Greedy Heuristic method
#' @description solution of knapsack problem based on Greedy Heuristic method
#' @return returns a list of maximum value and the elements
#' @export greedy_knapsack
greedy_knapsack <- function(x, W) {

  stopifnot(is.data.frame(x),W >= 0)

  # Calculate value per weight
  x$val_per_weight <- x$v/x$w

  # Add a column index
  x$index <- 1:nrow(x)

  # Order data frame in decreasing order on column value per weight
  x<-x[order(x$val_per_weight, decreasing = TRUE),]

  # Initialization
  i <- 1
  total_weight <- 0
  total_value <- 0
  total_indices <- c()

  # Calculate maximum profit and store indices
  while (total_weight < W) {
    total_weight <- total_weight + x$w[i]
    total_value <- total_value + x$v[i]
    total_indices <- append(total_indices, x$index[i])

    i <- i+1
  }

  # Maximum Profit
  max_value <- total_value - x$v[i-1]

  # Output list
  output_list <- list(value=round(max_value), elements=head(total_indices, -1))

  return(output_list)
}