RNGversion(min(as.character(getRversion()), "3.5.3"))
set.seed(42, kind = "Mersenne-Twister", normal.kind = "Inversion")
n <- 16
knapsack_objects <-
data.frame(
w = sample(1:4000, size = n, replace = TRUE), v = runif(n = n, 0, 10000))
brute_force_knapsack <- function(cx, W) {
#' The brute-force approach to solving the knapsack problem
#'
#' @export brute_force_knapsack
#'
#' @param cx A data.frame containing items with weights and values
#' @param W The weight limit of the knapsack.
#'
#' @return The total value of the fitted items, fitted items, and the time to run the algorithm.
#' @source \url{https://en.wikipedia.org/wiki/Knapsack_problem}
if(!is.data.frame(cx) || (length(cx) != 2)){(stop("Not a data frame or incorrect number of parameters!"))}
if(min(cx$v) < 0) {stop("Vector 'v' is not all positive!")}
if(min(cx$w) < 0) {stop("Vector 'w' is not all positive!")}
if(W < 0) {stop("The weight should be positive!")}
startTime <- Sys.time()
vectorMaxCombinations <- vector()
vectorMaxValues <- vector()
Wlimit <- W
#print(length(cx))
combinationItems <- c(1:length(cx$w))
for(s in 2:length(cx$v)) {
rowCounter <- 1
sampleSize <- s
listOfCombinations <- utils::combn(combinationItems, sampleSize)
lista <- t(listOfCombinations)
langd <- length(lista)/sampleSize
vector_Result_Values <- vector()
vector_Result_Weights <- vector()
vector_Result_Items <- vector()
for(m in 1:langd) {
items <- lista[m, ]
len <- length(items)
sumValue <- 0
sumWeight <- 0
#It is observed that the lines below consume a lot of time. For loop was changed into the R-built sum function.
# for(k in 1:len) {
# sumValue <- sumValue + cx$v[items[k]]
# sumWeight <- sumWeight + cx$w[items[k]]
# }
sumValue <- sum(cx$v[items])
sumWeight <- sum(cx$w[items])
if(sumWeight > Wlimit) next
vector_Result_Values[rowCounter] <- sumValue
vector_Result_Weights[rowCounter] <- sumWeight
vector_Result_Items[rowCounter] <- stringr::str_c(c(items), collapse = ", ")
rowCounter <- rowCounter + 1
}
vektorLangd <- length(vector_Result_Items)
if(vektorLangd == 0) next
maxNr <- which.max(vector_Result_Values)
vectorMaxCombinations[s-1] <- vector_Result_Items[maxNr]
vectorMaxValues[s-1] <- vector_Result_Values[maxNr]
}
maxValue <- max(vectorMaxValues)
maxValueRow <- which.max(vectorMaxValues)
kombination <- vectorMaxCombinations[maxValueRow]
maxValue
kombination <- as.numeric(unlist((strsplit(kombination, ","))))
stopTime <- Sys.time()
timeDiff <- stopTime - startTime
timeDiff
resultat <- list("value" = round(maxValue, digits = 3), "elements" = kombination, "time_elapsed" = round(timeDiff, digits = 4))
return(resultat)
}
#brute_force_knapsack(cx = knapsack_objects[1:8, ], W = 3500)
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.