R/knapsack.R

In Safvenberger/Lab6RT: Methods for solving the knapsack problem

#' Brute force knapsack problem algorithm
#'
#' @param x A data frame with two variables, v and w, only containing positive values.
#' @param W Knapsack size. 
#' @param fast Logical; whether to run the algorithm via C++ code or R code. Default is FALSE, i.e., R code.
#' @return A list containing the value of the knapsack and it's corresponding elements.
#' @export
#'
#' @examples 
#' set.seed(42)
#' n <- 2000
#' knapsack_objects <- data.frame(
#'    w = sample(1:4000, size = n, replace = TRUE),
#'    v = runif(n = n, 0, 10000)
#'    )
#' brute_force_knapsack(x = knapsack_objects[1:8,], W = 3500)
brute_force_knapsack <- function(x, W, fast = FALSE){
  
    if(!is.data.frame(x) | !all(c("w", "v") %in% names(x))){
      stop("Input x is not a data frame with columns v and w, stopping.")
    }
    if(any(x$w < 0) || any(x$v <0)){
      stop("Negative values in knapsack, stopping.")
    }
    if(W <= 0){
      stop("Knapsack capacity is 0 or negative, stopping.")
    }
    
    n <- nrow(x)
  
    if(fast){
      knapsack_items <- bruteForce(x$v, x$w, W, n)
      indices <- which(knapsack_items == 1)
      return(list(value = round(sum(x[indices, "v"])), 
                  elements = indices))
    } else { 
      index <- replicate(n,0)
      knapsack_value <- 0
      for (i in 1:(2^n)) {  
        j <- n
        temp_weight <- 0
        temp_value <- 0
        while(index[j] !=0 && j > 0){
          index[j] <- 0
          j <- j-1
        }
        index[j] <- 1
        for (k in 1:n) {
          if(index[k] == 1){
            temp_weight <- temp_weight + x$w[k]
            temp_value <- temp_value + x$v[k]
          }
        }
        if((temp_value > knapsack_value) & (temp_weight <= W)){
          knapsack_value <- temp_value
          knapsack_weight <- temp_weight
          knapsack_items <- index
        }
      }
      return(list(value = round(knapsack_value), 
                  elements = which(knapsack_items == 1)))
    }
}


#' A dynamic knapsack problem algorithm
#'
#' @param x A data frame with two variables, v and w, only containing positive values.
#' @param W Knapsack size.
#'
#' @return A list containing the value of the knapsack and it's corresponding elements.
#' @export
#' 
#' @examples 
#' set.seed(42)
#' n <- 2000
#' knapsack_objects <- data.frame(
#'    w = sample(1:4000, size = n, replace = TRUE),
#'    v = runif(n = n, 0, 10000)
#'    )
#' knapsack_dynamic(x = knapsack_objects[1:8,], W = 3500)
knapsack_dynamic <- function(x, W){
  
  if(!is.data.frame(x) | !all(c("w", "v") %in% names(x))){
    stop("Input x is not a data frame with columns v and w, stopping.")
  }
  if(any(x$w < 0) || any(x$v <0)){
    stop("Negative values in knapsack, stopping.")
  }
  if(W <= 0){
    stop("Knapsack capacity is 0 or negative, stopping.")
  }
  
  n <- nrow(x)
  m <- matrix(nrow = n, ncol = W)
  knapsack_items <- vector()
  for(i in 1:n){
    for(j in 1:W){
      if(i == 1 | j == 1){
        m[i, j] <- 0
      }
      else if(x$w[i] > j){
        m[i, j] <- m[i - 1, j]
      } 
      else {
        m[i, j] <- max(m[i - 1, j], m[i - 1, j - x$w[i]] + x$v[i])
      }
    }
  }
  knapsack_value <- m[n, W]
  weight <- W
  for(i in n:1){
    if(knapsack_value <= 0){
      break
    } 
    if(knapsack_value == m[i - 1, weight]){
      next
    } 
    else{
      knapsack_items <- c(knapsack_items, x$w[i])
      knapsack_value <- knapsack_value - x$v[i] 
      weight <- weight - x$w[i] 
    }
  } 
  return(list(value = round(m[n, W]), elements = which(x$w %in% knapsack_items)))
}


#' A greedy approach to the knapsack problem without replacement
#'
#' @param x A data frame with two variables, v and w, only containing positive values.
#' @param W Knapsack size.
#' 
#'
#' @return A list containing the value of the knapsack and it's corresponding elements.
#' @export
#'
#' @examples 
#' set.seed(42)
#' n <- 2000
#' knapsack_objects <- data.frame(
#'    w = sample(1:4000, size = n, replace = TRUE),
#'    v = runif(n = n, 0, 10000)
#'    )
#' greedy_knapsack(x = knapsack_objects[1:800,], W = 3500)
greedy_knapsack <- function(x, W){
  
  if(!is.data.frame(x) | !all(c("w", "v") %in% names(x))){
    stop("Input x is not a data frame with columns v and w, stopping.")
  }
  if(any(x$w < 0) || any(x$v <0)){
    stop("Negative values in knapsack, stopping.")
  }
  if(W <= 0){
    stop("Knapsack capacity is 0 or negative, stopping.")
  }
  
  x$ratio <- x$v / x$w
  x <- x[order(-x$ratio),]

  current_value <- 0
  knapsack_value <- 0
  temp_weight <- 0
  knapsack_items <- c()
  for (i in 1:nrow(x)) {
    temp_weight <- temp_weight + x$w[i]
    
    if(W >= temp_weight){
      current_value <- current_value + x$v[i]
    } 
    
    if(current_value > knapsack_value){
      knapsack_value <- current_value
      knapsack_items <- c(knapsack_items, as.integer(rownames(x)[i]))
    }
  }
  return(list(value = round(knapsack_value), elements = knapsack_items))
}