R/brute_force_algorithm.R

In abhijeet16/shazam: Knapsack Problem

#================================
#Package_name: Shazam
#Date: 11-10-2021
#Author: Abhijeet Anand and Dinuke Jayaweera
#This package is used to solve the Knapsack Problem
#================================

#' Knapsack Problem - Brute Force Method
#' @param x a data frame containing weight and values
#' @param W maximum weight
#' @param parallel TRUE if brute force method is parallelized
#' @title Knapsack Problem
#' @name Knapsack
#' @details knapsack problem based on Brute Force method
#' @description solution of knapsack problem based on Brute Force method
#' @return returns a list of maximum value and the elements
#' @export brute_force_knapsack
brute_force_knapsack <- function(x, W, parallel=FALSE)
{

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

  if (parallel==TRUE) {
    get_combination_weight <- function(k) {
      comb = which(as.logical(intToBits(k)))

      if (sum(x$w[comb])<=W) {
        return(sum(x$v[comb]))

      } else { return(0) }
    }

    # Create Cluster object
    cluster_obj <- parallel::makeCluster(parallel::detectCores())

    # Get total_combination_weight and stop cluster
    total_combination_weight <- parallel::parSapply(cluster_obj, 0:(2^(length(x$v))-1), get_combination_weight)
    parallel::stopCluster(cluster_obj)

    # Calculate max value and max_value_element
    max_value <- max(total_combination_weight)
    max_value_element <- which(as.logical(intToBits(which(total_combination_weight == max_value)[1] - 1)))
  }
  else {
    # Create vector of total rows of DF
    vec_total_rows <- c(1: nrow(x))

    my_elements<-list()
    for (i in 1:(2^(length(x$v)))) {
      comb = which(as.logical(intToBits(i)))
      my_elements[[i]]<-comb
    }

    # Initialize vectors
    v_sum_weights <- c()
    v_sum_values <- c()

    # Generate Vector of weights and values
    for (i in 1:length(my_elements)) {
      sum_weight <- 0
      sum_values <- 0

      for(j in 1:length(my_elements[[i]])) {
        sum_weight <- x$w[my_elements[[i]][[j]]] + sum_weight
        sum_values <- x$v[my_elements[[i]][[j]]] + sum_values
      }
      v_sum_weights <- append(v_sum_weights, sum_weight)
      v_sum_values <- append(v_sum_values, sum_values)
    }

    # get index of weights less than maximum weight
    get_index_weights <- which(v_sum_weights<W)

    # Calculate maximum value
    max_value <- 0
    for (k in 1:length(get_index_weights)) {
      if(v_sum_values[get_index_weights[k]] >= max_value) {
        max_value <- v_sum_values[get_index_weights[k]]
      }
    }

    # Get index of maximum value and generate maximum value
    max_value_index <- which(v_sum_values==max_value)
    max_value_element <- my_elements[[max_value_index]]

  }

  # Output List
  output_list <- list(value=round(max_value), elements=max_value_element)

  return(output_list)
}