In KarthiKeyanD4/lab6r: Knapsack Functions

knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>"
)

library(lab6r)

<p> This package is for knapsack problem i.e the total combination of object within the given weight.

<p> The three algorithms for the solution are
1. Brute Force Algorithm
2. Dynamic Algorithm
3. Greedy Algorithm

<p> Knapsack_object is a object which is a dataframe of 2000 rows and 2 columns. The column data contains the weight and value of objects.

```r
RNGkind(sample.kind = "Rounding")
set.seed(42)
n = 10000
knapsack_objects <- data.frame(w=sample(1:4000, size = n, replace = TRUE),v=runif(n = n, 0, 10000))

Algorithm Implementation

Brute Force Algorithm

The Algorithm can be executed as shown below. The time taken for 16 objects are shown below.

brute_force_knapsack(x = knapsack_objects[1:16,], W = 3500)
microbenchmark::microbenchmark(brute_force_knapsack(x = knapsack_objects[1:16,], W = 3500))

Dynamic Force Algorithm

The Algorithm can be executed as shown below. The time taken for 500 objects Using Rcpp.

dynamic_knapsack(x = knapsack_objects[1:500,], W = 3500, fast=FALSE)
microbenchmark::microbenchmark(dynamic_knapsack(x = knapsack_objects[1:500,],W = 3500, fast=FALSE))

Greedy Algorithm

The Algorithm can be executed as shown below. The time taken for 10000 objects Using Rcpp.

greedy_knapsack(x = knapsack_objects[1:10000,], W = 3500, fast=FALSE)
microbenchmark::microbenchmark(greedy_knapsack(x = knapsack_objects[1:10000,],W = 3500,fast=FALSE))