R/knapsack_dynamic.R

In rjkhan/RCourse-lab6: Knapsack problem solved by different alogrithms

luid <- "rabsh696 & samza595"
name <- "rabnawaz & saman"
#'Knapsack problem solve with Dynamic problem solving.
#'@author rabnawaz & saman
#'@param x is a data frame hiaving 2 column 'w' and 'v' where w is weight if items and v is the value of item
#'@param W capacity of knapsack i.e total weight that knapsack can contain in it
#' @return return list which have maxValue and and item number of elemnts that knapsack have in it
#'@details dynamic programming algo going through all possible alternatives and return the maximum value found.
#'@references
#'\url{https://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming_in-advance_algorithm}
#'@export


knapsack_dynamic <- function(x, W){
  
  if(!(is.data.frame(x)) || !(is.numeric(W)) || W < 0 )
    stop()
  
  mat <- matrix(0, nrow = (nrow(x) + 1), ncol =  (W + 1)  )
  for(i in 2: (nrow(x) + 1))
  {
    for(j in 1: (W + 1) )
    {
      if( x[i-1,1] >= j )
        mat[i,j] = mat[i-1, j]
      else
        mat[i,j] = max(mat[i - 1 ,j] , mat[i - 1 , j - x[i-1,1]] + x[i-1,2] )
    }

  }
  
  # backtracking part
  fmax <- mat[(nrow(x) + 1),(W + 1)]
  j <- (W + 1)
  k <- (nrow(x) + 1) 
  selected_item <- rep(FALSE,(nrow(x) + 1))
  elemnts <- c()
  while( (nrow(x) + 1) > 1)
  {
    
    if(fmax > mat[k,j])
    {
      vv <- (j - x[k,1])
      if (vv > 0) {
        if( (mat[k,vv] + x[k,2]) == mat[k+1,j])
        {
          selected_item[k] <- TRUE
          j <- vv
        }
      }
      else
        break
    }
    k <- k - 1
  }
  
  ItemList <- which(selected_item)
  return(list( value = round(max(mat)) , elements = ItemList))
}

# set.seed(42)
# n <- 2000
# knapsack_objects <- data.frame( w=sample(1:4000, size = n, replace = TRUE),
# v=runif(n = n, 0, 10000)
# )
# # a <- data.frame(w=c(1,3 ,4 ,5 ), v=c(1,4,5,7) )
# 
# knapsack_dynamic(x = knapsack_objects[1:8,], W = 3500)
# # system.time()
# # proc.time()