In Mahmood1s/lab6: Knapsack Problem Algorithms

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

What Package is Calculating

This package has a class which consist of three methods and one constructer. constructer/initialized method is generated a dataset for the class accounding the user requirement. and then user can call any function from knapsack_brute_force, dynamic_programming or greedy_heuristich.

Function initialized

constructer/initialized method is generated a dataset for the class accounding the user requirement.

Function brute_force_knapsack()

This method is solving knapsack problem by using set method. there is an optional parameter parallel (Paral) which is by default FALSE and if you pass the value TRUE to this parameter it calculations the combiinations in parallel manner and performance increases exponentially.

Function knapsack_brutefore_profiling()

this mathod is profilling the code written in brute_force_knapsack mathod.

Function knapsack_dynamic()

This method is solving knapsack problem by using tabular method/ dynamic programming.

Function knapsack_dynamic_profiling()

this mathod is profilling the code written in knapsack_dynamic mathod.

Function greedy_knapsack()

This function is returning a vector of Residuals

Function knapsack_greedy_profiling()

this mathod is profilling the code written in greedy_knapsack mathod.

knapsack_brute_force

This is how function will called and output the results

devtools::load_all()
obj <- knapsack_class$new()
obj$brute_force_knapsack(obj$ks_dataset[1:16,],3500)
system.time(obj$brute_force_knapsack(obj$ks_dataset[1:16,],3500))
obj$knapsack_brutefore_profiling(obj$ks_dataset[1:16,],3500)

knapsack brute force Question

How much time does it takes to run the algorithm for n = 16 objects?

Answer : it will take 2^16 = 65536 iterations

knapsack_brute_force with parellel Approach

This is how function will called and output the results

obj$brute_force_knapsack(obj$ks_dataset[1:16,],3500,Paral = TRUE)
system.time(obj$brute_force_knapsack(obj$ks_dataset[1:16,],3500,Paral = TRUE))
obj$knapsack_brutefore_profiling(obj$ks_dataset[1:16,],3500,para = TRUE)

knapsack_brute_force performance after optimization

What performance gain could you get by trying to improving your code? Answer = we have got around 15 percent better performance after optimizing the code.we have filtered the comibations those have comulative sum greater than W.

knapsack_brute_force performance gain after parallelization

What performance gain could you get by parallelizing brute force search? Answer = we have got around 80 percent better performance after parallizing the code of computing the combinations in parallel

knapsack_dynamic

This is how function will called and output the results

obj$knapsack_dynamic(obj$ks_dataset[1:8,],3500)
system.time(obj$knapsack_dynamic(obj$ks_dataset[1:8,],3500))
obj$knapsack_dynamic_profiling(obj$ks_dataset[1:8,],3500)

knapsack dynamic Question

How much time does it takes to run the algorithm for n = 500 objects? Answer : it will take n X W time, if W =3500 then it will be 500 X 3500 = 1750000 combinations

greedy_knapsack

This is how function will called and output the results

obj$greedy_knapsack(obj$ks_dataset[1:8,],3500)
system.time(obj$greedy_knapsack(obj$ks_dataset[1:8,],3500))
obj$knapsack_greedy_profiling(obj$greedy_knapsack(obj$ks_dataset[1:800,],3500))

greedy knapsack Question

How much time does it takes to run the algorithm for n = 1000000 objects? Answer : it will take 6000000 time which is nlogn times

Mahmood1s/lab6 documentation built on Oct. 30, 2019, 9:09 p.m.