brute_force_knapsack: Brute force Solution for Knapsack Problem

In Oliverckb/LAB6: functions for knapsack problem

Description

The knapsack problem is a combinatorial optimization problem. A dataframe is given having two parameters, weight and value. Each value has its own weight and we have to pack items with maximum value and within weight capacity. This function will run in O<2^n>.

Usage

brute_force_knapsack(x,W,parallel)

Arguments

x	is a data frame with two columns w(weight) and v(value)
W	is maximum weight(capacity) of knapsack
parallel	is to tell R whether or not to use parallel computation

Value

list List of object containing value giving maximum value of Knapsack out of dataframe and elements giving weight of selected elements from data frame x

See Also

https://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_knapsack_problem

Examples

  RNGversion(min(as.character(getRversion()),"3.6.1"))
  set.seed(42,kind="Mersenne-Twister",normal.kind = "Inversion")
  n <- 2000
  knapsack_objects <-data.frame(w=sample(1:4000, size = n, replace = TRUE),
                             v=runif(n = n, 0, 10000))
  l<-brute_force_knapsack(knapsack_objects[1:16,] , 3500,FALSE)
  

Oliverckb/LAB6 documentation built on Oct. 17, 2020, 5:53 a.m.