In Oliverckb/LAB6: functions for knapsack problem

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

library(lab6pkg)

suppressWarnings(RNGversion("3.5.9"))
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))

The Knapsack Problem

This package contains three different functions for solving the Knapsack Problem:

1. brute_force_knapsack

2. knapsack_dynamic

3. greedy_knapsack

First function: brute_force_knapsack()

The only solution that is guaranteed to give a correct answer in all situations for the knapsack problem is using brute-force search, i.e. going through all possible alternatives and return the maximum value found. This approach is of complexity $O(2^n)$ since all possible combinations $2^n$ needs to be evaluated.

The Algorithm can be executed as shown below. The time taken for $n=16$ objects is shown below.

set.seed(42, kind = "Mersenne-Twister", normal.kind = "Inversion")
n <- 16
knapsack_objects <- data.frame(w=sample(1:4000, size = n, replace = TRUE),v=runif(n = n, 0, 10000))
brute_force_knapsack(knapsack_objects[1:16,],3500)
system.time(brute_force_knapsack(knapsack_objects[1:16,],3500))

RUN TIME with parallel equal to FALSE: 0.69 second RUN TIME with parallel equal to FALSE: 0.19 second

After Parallelizing, the run time shortened significantly.

After profiling, it can be seen that it is taking too much time in serial operation.The time taken for $n=16$ objects. wzxhzdk:4 ## Second function: **Knapsack_dynamic()**

The Algorithm can be executed and the time taken for $n=500$ objects as shown below. As it can be seen that the dynamic algorithm is faster than the brute force because the dynamic algorithm will run in $O(Wn)$. wzxhzdk:5 And the result of profiling comes below: wzxhzdk:6 ## Third function: **greedy_knapsack()**

The Algorithm can be executed and the time taken for $n=10000$ objects as shown below. Greedy algorithm is _not most accurate algorithm_, but is the fastest of all because the computational complexity for this algorithm is $O(nlogn)$ due to its sorting mechanism. wzxhzdk:7 And the result of profiling comes below: wzxhzdk:8

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