#'@title brute force
#'@description brute force implementation
#'@name lib6af
#'@docType package
#'@importFrom utils, combn
#'@export brute_force_knapsack
#acknowledgement John Lacin, Erick Herwin, Simon Jonsson
#library(lineprof)
library(utils)
brute_force_knapsack <- function(x, W, parallel = FALSE) {
stopifnot(W > 0 &
is.data.frame(x) &
is.vector(x$v) &
is.vector(x$w) &
length(x$w) == length(x$v))
n <- length(x[[1]])
v <- x$v
w <- x$w
best <- replicate(n, 0)
if (parallel) {
# Checks each row of M if the weight is allowed
res_vec <- parallel::mclapply(1:(2^n-1), function(x, w, v, W) {
m <- intToBits(x)
if (sum(w[m == 1]) <= W) {
return(m)
}
}, w, v, W, mc.cores = parallel::detectCores())
# Takes all the allowed rows and calculates which one has the best value
lapply(Filter(Negate(is.null), res_vec), function(m) {
if (sum(v[m == 1]) > sum(v[best == 1])) {
best <<- m
}
})
} else {
# Goes through each row of M to find the optimal value
lapply(1:(2^n-1), function(x) {
m <- intToBits(x)
if (sum(v[m == 1]) > sum(v[best == 1]) & sum(w[m == 1]) <= W) {
best <<- m
}
})
}
res <- list(value = sum(v[best == 1]), elements = which(best == 1))
return(res)
}
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.