R/knapsack_dynamic.R

In harjew/lab6G3: Computer lab 5

#' Knapsack dynamic Problem
#' 
#' knapsack dynamic force.
#' 
#' @param x An object with the class “data frame”, the weight of the data in the first column and price in the second column.
#' @param W A numeric value grater than 0, the maximal capacity of the knapsack.
#' 
#' @return A list of the greatest combined value and the elements.
#' @examples 
#' x<-knapsack_data(8)
#' knapsack_dynamic(x,3500)
#' system.time(knapsack_dynamic(x,3500))
#' @export


knapsack_dynamic<-function(x,W){
  stopifnot(is.data.frame(x),is.numeric(W),W>0)
  n<-length(x[,1])
  x$n<-1:n
  orginal<-x
  x<-x[order(x[,1]),]
  x$x<-logical(n)
  taken<-W+1
  matrix_1<-matrix(0,nrow = taken,ncol = n)
  matrix_2<-matrix(0,nrow = taken,ncol = 1)
  #Forward calculations
    i<-1
    repeat{
    matrix_1[,i]<-matrix_2
    if(W>=x[,1][i]){
      v<-c(numeric(x[,1][i]),matrix_2[1:(W+1-x[,1][i]),1]+x[,2][i])
      matrix_2<-pmax(matrix_2,v)
    }else{
      matrix_2<-matrix_2
    }
    i<-i+1
    if(i>n){
      break
    }
  }
  maximum<-matrix_2[W+1,1]
  # Backwards calculations
  j<-n
  repeat{
    if(matrix_1[taken,j]<maximum){
      x$x[j]<-TRUE
      taken<-taken-x[,1][j]
      maximum<-matrix_1[taken,j]
    }
    j<-j-1
    if(j==0){
      break
    }
  }
  my_list<-list()
  which_<-x$x*x$n
  which_elements<-sort(which_[which(which_!=0)])
  my_list$value<-sum(orginal[,2][which_elements])
  my_list$elements<-which_elements
  my_list
  return(my_list)
}