R/brute_force_knapsack.R

In abhi-vellala/732A94lab6: Knapsack Problem Algorithms

#'@title Brute Force Knapsack Algorithm
#'@description Solution to the knapsack problem using brute-force search.\cr
#'The algorithm goes through all possible alternatives and returns the maximum value found.\cr
#'Correct answer guaranteed in all situations.
#'@references \href{https://en.wikipedia.org/wiki/Knapsack_problem}{Wikipedia}
#'@param x Dataframe with variables v and w.
#'@param W Integer. Size of the knapsack.
#'@aliases bfk
#'@return Returns a list with the total final value and the items added to the knapsack.

brute_force_knapsack <- function(x, W, parallel=FALSE){
	if(!is.data.frame(x) | !("w" %in% colnames(x)) | !("v" %in% colnames(x))){
		stop("The first argument must be a dataframe with at least two variables: v and w")
	}
	if(!is.numeric(W)){
		stop("The weight limit (second argument) has to be a numeric object")
	}
	if(W<0){
		stop("The weight limit (second argument) cannot be a negative integer!")
	}
	
	if(parallel==FALSE){
		items <- c()
		weights <- c()
		values <- c()
		for(i in 1:nrow(x)){
			items <- c(items,combn(rownames(x), i, paste, collapse = "+"))
			values <- c(values,combn(x$v, i, sum))
			weights <- c(weights,combn(x$w, i,sum))
		}
	}
	else{
		cores <- parallel::detectCores()
		cl <- makeCluster(cores, type="PSOCK")
		clusterExport(cl, c("x"), envir = environment())
		clusterEvalQ(cl, { library(parallel) })
		items <- parLapplyLB(cl, 1:nrow(x), fun=function(y) { combn(rownames(x), y, paste, collapse="+") })
		weights <- parLapplyLB(cl, 1:nrow(x), fun=function(y) { combn(x$w, y, sum) })
		values <- parLapplyLB(cl, 1:nrow(x), fun=function(y) { combn(x$v, y, sum) })
		stopCluster(cl)
	}
	
	weight_idxs <- which(weights < W) # indexes of weight combinations that don't exceed the limit
	valid_values <- values[weight_idxs] # discard all values associated to combinations that are too heavy
	value_idxs <- which(values == max(valid_values)) # select only those valid combinations that have maximum values
	chosen_items <- unlist(strsplit(items[value_idxs],"+",fixed=TRUE)) #  as.numeric(unlist(  ))
	
	output_list <- list("value"=0,"elements"=c())
	output_list$value <- round(max(valid_values))
	output_list$elements <- as.numeric(chosen_items)
	return( output_list )
	
}

# Setup:
# set.seed(42)
# n <- 2000
# knapsack_objects <- data.frame(w=sample(1:4000, size = n, replace = TRUE), v=runif(n = n, 0, 10000))

# How much time does it takes to run the algorithm for n = 16 objects? 0.6390648 seconds
# start_time <- Sys.time()
# brute_force_knapsack(x = knapsack_objects[1:16,], W = 3500, parallel=TRUE) # 22160 , 3 8 14
# end_time <- Sys.time()
# cat("Runtime for 16 objects: ",end_time-start_time,"\n")

# Execution examples:
#brute_force_knapsack(x = knapsack_objects[1:8,], W = 3500) # 16770 , 5 8
#brute_force_knapsack(x = knapsack_objects[1:12,], W = 3500) # 16770 , 5 8
#brute_force_knapsack(x = knapsack_objects[1:8,], W = 2000) # 15428 , 3 8
#brute_force_knapsack(x = knapsack_objects[1:12,], W = 2000) # 15428 , 3 8