R/brute_force_knapsack.R

In shihs/LiUAdRLab6: The knapsack package

#' Solve knapsack problem by brute-force search. This approach is of complexity O(2^n).
#'
#' @param x data.frame, first column x:weight of object, second column v:value of object
#' @param W numeric, weight limit of knapsack
#'
#' @return list, value: total value of objects, elements: the rows of objects
#'
#' @examples
#' data(knapsack_objects)
#' knapsack_brute_force(x = knapsack_objects[1:8,], W = 3500)
#'
#' @export
brute_force_knapsack <- function(x, W) {
  #--------------------------------------------------------------------------------
  # Stop checking
  #--------------------------------------------------------------------------------
  if (!is.data.frame(x) || !is.numeric(W)) {
    stop("wrong input")
  }

  if (all(names(x) != c("w", "v"))) {
    stop("the name of columns have to be 'w' and 'v'")
  }

  if (!is.numeric(x$w) || !is.numeric(x$v)) {
    stop("the value of data.frame columns have to be positive number")
  }

  if (!all(x$w > 0) || !all(x$v > 0)) {
    stop("the value of data.frame columns have to be positive number")
  }

  #--------------------------------------------------------------------------------
  # Initialize return values
  #--------------------------------------------------------------------------------
  # rowname for retrun elements
  rownames(x) <- 1:nrow(x)
  max_value <- 0
  elements <- c()

  # delete the rows which weight are already over weight limit W
  i <- which(x$w > W)
  if (length(i) > 0) {
    x <- x[-i, ]
  }
  # x <- x[order(x$w), ]
  #--------------------------------------------------------------------------------
  # Brute force search - Time complexity:O(2^n)
  #--------------------------------------------------------------------------------
  # there're 2^nrow(x) -1 (minus {}) subsets
  lapply(1:(2^nrow(x)-1), function(i) {
    sub_set <- x[intToBits(i) > 0, ]
    if (sum(sub_set$w) <= W) {
      sum_value <- sum(sub_set$v)
      max_value <<- max(max_value, sum_value)
      # choose maxmum value subset
      if (max_value == sum_value) {
        elements <<- rownames(x)[intToBits(i) > 0]
      }
    }
  })

  return (list(value = round(max_value, 0), elements = as.numeric(elements)))
}