R/knapsack_dynamic.R

In shihs/LiUAdRLab6: The knapsack package

#' Solve knapsack problem by Dynamic programming. This approach is of complexity O(Wn).
#'
#' @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)
#' dynamic_knapsack(x = knapsack_objects[1:8,], W = 3500)
#'
#'
#' @export
dynamic_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)

  # 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), ]

  # # smaller weight in x
  # min_w <- x$w[1]
  # # matrix for saving max sum value
  # sum_matrix <- matrix(rep(0, nrow(x)*(W-min_w+1)), nrow = nrow(x))
  # # vector from smaller weight to limit weight
  # nm <- min_w:W
  # names(sum_matrix) <- nm
  # # the value of first row always
  # sum_matrix[1, ] <- x$v[1]
  #
  # for (i in 2:nrow(x)) {
  #
  #   weight_now <- x[i, "w"]
  #   n <- which(nm < weight_now)
  #   sum_matrix[i, n] <- sum_matrix[i-1, n]
  #
  #   sum_matrix[i, which(nm == weight_now)] <- x[i, "v"]
  #
  #   # for (j in (n[length(n)]+1):W) {
  #   for (j in (n[length(n)]+2):(W - min_w + 1)) {
  #     sum_matrix[i, j] <- max(sum_matrix[i-1, j], sum_matrix[i-1, (j+min_w-1)-weight_now] + x[i, "v"])
  #
  #   }
  # }

  sum_matrix <- matrix(rep(0, (nrow(x)+1)*(W+1)), nrow = nrow(x)+1)

  for (i in 2:(nrow(x)+1)) {
    for (j in 1:(W+1)) {
      if (x[i-1, "w"] > j) {
        sum_matrix[i, j] <- sum_matrix[i-1, j]
      } else {
        sum_matrix[i, j] <- max(sum_matrix[i-1, j], sum_matrix[i-1, j-x[i-1, "w"]] + x[i-1, "v"])
      }
    }
  }


  i <- nrow(sum_matrix)
  j <- ncol(sum_matrix)
  value <- sum_matrix[i, j]

  elements <- c()

  while (i > 1 && j > 1) {

    if (sum_matrix[i, j] == sum_matrix[i-1, j]) {
      i <- i - 1
    } else {
      # print (paste0("i = ", i, " j = ", j))
      elements <- c(elements, rownames(x)[i-1])
      j <- (j - 1) - x[i-1, "w"]
      i <- i - 1
    }
  }

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

}