R/greedy.R

In fbarulli/lib6af: Connecting R to an API

#'@title greedy implementation
#'@description greedy implementation
#'@name lib6af
#'@docType package 
#'@importFrom utils, combn

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



greedy_knapsack<-function(x,W){
  stopifnot(W > 0 &
              is.data.frame(x) &
              is.vector(x$v) &
              is.vector(x$w) &
              length(x$w) == length(x$v))
  v<-x$v
  w<-x$w
  n<-length(v)
  winner<- replicate(n,0)

  ordered<-order(v/w, decreasing = TRUE)
  for(i in ordered){
    amount<- (W-w[i]-sum(w[winner>0]))/ w[i]
    if (amount>0){
      winner[i]<-amount
    }else{
      break
    }
  }
  knapsack<-list(value=sum(v[winner>0]), elements = which(winner>0))
  return(knapsack)
}

# lineprof(greedy_knapsack(x = knapsack_objects[1:1200, ], W = 2000))