R/knapsack_dynamic.R

In abhijeet16/shazam: Knapsack Problem

#' Knapsack Problem - Dynamic Programming
#' @param x a data frame containing weight and values
#' @param W maximum weight
#' @title Knapsack Problem
#' @name Knapsack
#' @details knapsack problem based on Dynamic Programming
#' @description solution of knapsack problem based on Dynamic Programming
#' @return returns a list of maximum value and the elements
#' @export knapsack_dynamic
knapsack_dynamic <- function(x, W){

  stopifnot(is.data.frame(x),W >= 0)
  stopifnot(is.numeric(W))

  #Reorder the weights and remove the weights that are more than the maximum weight
  x <- x[rev(order(x[,1])),]
  x <- x[x[,'w']<=W,]

  # store all indices
  element_chars <- rownames(x)

  # store all weights
  weight <-(x[,1])

  # store all profits
  profit <-(x[,2])

  # calculate total no of rows assign FALSE to no of rows
  total_rows <- nrow(x)
  x <- logical(total_rows)

  # Create Matrices
  mat1 <- matrix(0, nrow=W+1, ncol=total_rows)
  mat2 <- matrix(0, nrow=W+1, ncol=1)


  for (i in 1:total_rows) {
    mat1[, i] <- mat2
    values <- c(numeric(weight[i]), mat2[1:(W + 1 - weight[i]), 1] + profit[i])

    # Store maximum of two vectors element by element
    mat2 <- pmax(mat2, values)
  }
  max_value <- mat2[W + 1, 1]

  temp <- max_value
  j <- W + 1

  # Reverse Order
  for (k in total_rows:1) {
    if (mat1[j, k] < temp) {
      x[k] <- TRUE
      j <- j - weight[k]
      temp <- mat1[j, k]
    }
  }

  # Get Indices
  get_index <- which(x)

  # Get elements
  elements <- as.numeric(element_chars[x])

  # Get Maximum profit
  max_profit <- round(sum(profit[get_index]))

  result <- list(value = max_profit, elements = elements)
  return(result)
}