R/dynamic_knap_sac.R

In fbarulli/lib6af: Connecting R to an API

#'@title dynamic implementation
#'@description dynamic implementation
#'@name lib6af
#'@docType package 
#'#'@title brute force 
#'@description brute force implementation
#'@name lib6af
#'@docType package 
#'@importFrom utils, combn
#'
#'@export knapsack_dynamic
#acknowledgement John Lacin, Eric Herwin, Simon Jonsson
#library(lineprof)
#library(utils) 

# set.seed(42)
#acknowledgment : Simon Jonsson
#intput

#library(lineprof)

# set.seed(42)
# n <- 2000
# knapsack_objects <-
#   data.frame(w = sample(1:4000, size = n, replace = TRUE),
#              v = runif(n = n, 0, 10000))


#function
knapsack_dynamic <- function(x, W) {
  stopifnot(W > 0 &
              is.data.frame(x) &
              is.vector(x$v) &
              is.vector(x$w) &
              length(x$w) == length(x$v))

  dynamic_knap_sack_n <- length(x[[1]])
  d_k_s_matrix <-
    matrix(replicate(W * dynamic_knap_sack_n, 0),
           nrow = dynamic_knap_sack_n,
           ncol = W)
  v <- x$v
  w <- x$w

  for (j in 1:W) {
    d_k_s_matrix[1, j] <- 0
  }

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

obs<-c()
weight<-W
i<-dynamic_knap_sack_n
while(i>1){
  if(d_k_s_matrix[i,weight]> d_k_s_matrix[i-1,weight]){
    obs<-c(obs,i)
    weight<- weight-w[i]
    i<-i-1
  } else {
    i<-i-1
  }
}
return(list(value=d_k_s_matrix[dynamic_knap_sack_n,W], elements=rev(obs)))
}


# lineprof(knapsack_dynamic(x = knapsack_objects[1:12,], W=3500))