In zahrajalilpour292/knapsack_package: knapsack_package

knitr::opts_chunk$set(error = TRUE)

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

Loading the packages used in this report

library(knapsack)
library(microbenchmark)

knapsack problem

This package contains different implementations of Knapsack problem.

knapsack is a optimization problem, here we have used the discreate variant of this problem.

There are three different function in which we have implemented same problem using different algorithms techniques.

**1. brute_force_knapsack** **2. knapsack_dynamic** **3. greedy_knapsack** We have generated a random data for this problem. Above functions have same parameters expect for the brute_force_knapsack function. ### Argumnets __x__ represnt the dataframe with values v and weights w for items. __W__ represent the maximum weight that a particular bag can have in it. __parallel__ is for the code to be run on multiple cores of processsor for fast execution. wzxhzdk:2 ## Brute Force 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. for time running, by microbenchmark library we will see the mean time as below. The mean run time is 334ms. wzxhzdk:3 ## Dynamic Programming

The second algorithm we use for knapsack problem is dynamic.The running time of the dynamic programming solution is $O(Wn)$. It is a way to improve the running time. As we see the running time is decreased compared to Brute Force function. The mean of run time is 44 ms. wzxhzdk:4 ## Greedy Knapsack

A last approach is to use the a heuristic or approximation for the problem. This algorithm will not give an exact result (but it can be shown that it will return at least 50% of the true maximum value), but it will reduce the computational complexity considerably (actually to $O(n log n)$ due to the sorting. wzxhzdk:5 ## Brute Force Parallel What we have done here is just added the extra parameter in the brute force algorithm function, parallel which is by default is FALSE. If we put the value TRUE then the function will run on the mutliple core of the system with Windows,linux and MacOs operating system. wzxhzdk:6

zahrajalilpour292/knapsack_package documentation built on Nov. 10, 2020, 1:28 a.m.