R/greedyAlgorithem.R

In nourqweder/AdvRLab6: The knapsack package

#' This Package is solving knapsack problem using Greedy heuristic algorithm.
#' Expected Input: It will take data frame and weight limit and implement Greedy
#' Expected Output: It will show list of weights and values total
#' @title Greedy Agorithm Implementation
#' @param x A data frame
#' @param W A weight limit
#' @references \href{https://en.wikipedia.org/wiki/Knapsack_problem#Greedy_approximation_algorithm}
#' @export
greedy_knapsack<-function(x,W){
                           stopifnot(is.data.frame(x) && names(x)==c("w","v") && length(x)>1)
                           maxw<-W
                           x<-transform(x,dens=round(v/w,4))
                           x<-x[order(x$dens,decreasing = TRUE),]
                           x<-transform(x,tw=0)
                           x<-transform(x,tv=0)
                             totalw<- 0
                             totalv<-0
                             for(j in 1:nrow(x)){
                                if(totalw + x[j,]$w>maxw)
                                  break()
                               if(x[j,"tw"]<=maxw){
                                 totalw = totalw + x[j,]$w
                                 totalv = totalv + x[j,]$v
                                 x[j,]$tw<-totalw
                                 x[j,]$tv<-totalv
                            }
                             }

                          elements <- as.numeric(rownames(x[x$tw>0,]))
                          flist <- list("value"=round(max(x$tv)),"elements"=elements)
                           return(flist)
                         }