#' @title
#' greedy_knapsack
#' @description greedy_knapsack function to solve the knapsack problem
#' @name
#' greedy_knapsack
#'
#' @param x , is the input weight
#' @param W , is the input value
#'
#'
#' @return list , returns a list that contain the maximum value and the list of elements chosen
#' @export
greedy_knapsack <- function(x,W)
{
#Check input
if(is.data.frame(x)==FALSE)
stop("x must be a data frame")
if(is.numeric(W)==FALSE)
stop("W should be a number")
if (W <=0)
stop("W should bigger than 0")
#+++++++++++++++++++++
#value per weight
vpw <- x[,2]/x[,1]
x$vpw <- vpw
#order
x <- x[order(x$vpw, decreasing = TRUE),]
weight <- W
sum <- 0
i <-1
elements <- c()
nrow <- nrow(x)
#sum value until reach the weight
for (i in 1:nrow)
{
if (x$w[i] < weight)
{
if (weight > 0)
{
weight <- weight - x$w[i]
sum <- sum + x$v[i]
elements <- c(elements, as.numeric(row.names(x)[i]))
}
} else break()
}
output <- list(value = round(sum, 0), elements = elements)
return(output)
}
#greedy_knapsack(x = knapsack_objects[1:800,], W = 3500)
#greedy_knapsack(x = knapsack_objects[1:1200,], W = 2000)
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.