R/knapsack_dynamic.R

In nourqweder/AdvRLab6: The knapsack package

#' Knapsack problem solving using dynamic programming algorithm
#'
#' @param x is a dataframe with weights and values
#' @param W is a knapsack limit weight
#' @return maximum value and the elements of knapsack
#' All arguments must satisfy the conditions
#'
#' @examples
#' knapsack_dynamic(x = knapsack_objects[1:8,], W = 3500)
#' knapsack_dynamic(x = knapsack_objects[1:12,], W = 3500)
#' knapsack_dynamic(x = knapsack_objects[1:8,], W = 2000)
#' knapsack_dynamic(x = knapsack_objects[1:12,], W = 2000)
#'
#'
#' @references url/{https://en.wikipedia.org/wiki/Knapsack_problem}
#'
#' @export
#'
knapsack_dynamic <- function(x, W) {

  #conditioning of the function before working
  stopifnot(is.data.frame(x))
  stopifnot(length(x)==2)
  stopifnot(names(x)==c("w", "v"))
  stopifnot((x$w > 0))
  stopifnot( x$v > 0 )
  stopifnot(is.numeric(W))
  stopifnot( (W > 0) )

  #how it is working
  #pseudo code from wikipedia

  n <- nrow(x)
  mrownum <- n+1
  mcolnum <- W+1

  m <- matrix(nrow = mrownum, ncol = mcolnum )
  m[1,] <- 0

  for (i in 1:n) {
    for (j in 1:mcolnum) {
      if (x$w[i] <= j) {
        m[i+1,j] <- max(m[i,j], m[i,j-x$w[i]] + x$v[i])
      } else {
        m[i+1,j] <- m[i, j]
      }
    }
  }

  contain <- c()
  i <- i+1

  while(i > 1 ){
    if( m[i-1,j] < m[i,j] ){
      contain <- append(contain, i-1)
      i <- i - 1
      j <- j - x$w[i]
    }else{
      i <- i - 1
    }
  }
  contain <- contain[order(contain)]
  return(list(value=round(m[nrow(m), ncol(m)]),elements=contain))
}