knapsack_dynamic: Dynamic programming 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 should return the same results as the brute force algorithm, but unlike the brute force it should scale much better since the algorithm will run in O<Wn>.

Usage

knapsack_dynamic(x,W)

Arguments

x	is a data frame with two columns w(weight) and v(value)
W	is maximum weight(capacity) of knapsack

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<-knapsack_dynamic(knapsack_objects[1:12,],3500)
  

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