In rjkhan/RCourse-lab6: Knapsack problem solved by different alogrithms

we have created a new package on github to implement the 3 different alorithms to solve a knapsack problem

What is Kanpsack Problem ?

The knapsack problem is a discrete optimization problem where we have a knapsack that can take a limited weight Wand we want to fill this knapsack with a number of items i = 1, ..., n, each with a weight wi and a value vi .The goal is to find the knapsack with the largest value of the elements added to the knapsack.This problem is NP-hard, meaning that it is ”at least as hardas the hardest problem in NP” ref: (via)

What is NP?

NP is a (fundamental) class of problems for which there are (currently) no polynomial time algorithms to solve them.It is an open (Millennium Prize) problem, whether it is or is not possible to solve these problemsin polynomial time. For a more detailed background of the knapsack problem see this page (via) problem.

Three Different algorithms to solve a knapsack problem?

• brute force knapsack brute force knapsack(x,W, parallel = FALSE)
• knapsack dynamic knapsack_dynamic(x,W)
• greedy knapsack greedy_knapsack(x,W)

Arugments

• x is data frame which has w as weight column and v as value of each weight item
• W captial W is represent a knapscak capcaity that knapsack can carry
• parallel which is only used in brute force search alogrithm if you want to run on mulitple core than set is as TRUE. The default value is set as FALSE

generate a data

library(knapsack) #load our knapsack library
set.seed(42) #set seed to generate a random sample
n <- 2000    # number of Items
knapsack_objects <- data.frame( w=sample(1:4000, size = n, replace = TRUE),
                                v=runif(n = n, 0, 10000)
)

head(knapsack_objects) #show number of rows of sample data 

brute_force_knapsack(x,W)

brute_force_knapsack(knapsack_objects[1:8,], W = 3500)

brute_force_knapsack(x = knapsack_objects[1:12,], W = 2000)

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

library(knapsack) #load our knapsack library
set.seed(42) #set seed to generate a random sample
n <- 16    # number of Items
knapsack_objects <- data.frame( w=sample(1:4000, size = n, replace = TRUE),
                                v=runif(n = n, 0, 10000))
# time taken to run on n= 16 and W= 2000
system.time(brute_force <- brute_force_knapsack(x = knapsack_objects[1:12,], W = 2000))

knapsack_dynamic(x, W)

knapsack_dynamic(knapsack_objects[1:8,], W = 3500)

knapsack_dynamic(x = knapsack_objects[1:12,], W = 2000)

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

library(knapsack) #load our knapsack library
set.seed(42) #set seed to generate a random sample
n <- 500    # number of Items
knapsack_objects <- data.frame( w=sample(1:4000, size = n, replace = TRUE),
                                v=runif(n = n, 0, 10000))
# time taken to run on n= 16 and W= 2000
system.time(dynamic_result<- knapsack_dynamic(x = knapsack_objects[1:12,], W = 2000))

greedy_knapsack(x, W)

greedy_knapsack(knapsack_objects[1:800,], W = 3500)

greedy_knapsack(x = knapsack_objects[1:12,], W = 2000)

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

library(knapsack) #load our knapsack library
set.seed(42) #set seed to generate a random sample
n <- 1000000    # number of Items
knapsack_objects <- data.frame( w=sample(1:4000, size = n, replace = TRUE),
                                v=runif(n = n, 0, 10000))
# time taken to run on n= 16 and W= 2000
system.time(greedy_result <- greedy_knapsack(x = knapsack_objects[1:12,], W = 2000))

Parallelize brute force search

The brute force algorithm is straight forward to parallelize for computers with multiple cores. we have Implement an argument parallel in brute force knapsack() that is FALSE by default.If set to TRUE, the function should parallelize over the detected cores.

Microbenchmark package to compare how long each variation takes to run

library(microbenchmark)

microbenchmark(
  "brute_force"= brute_force, #n= 16
  "dynamic_knapsack" = dynamic_result, #n= 500
  "greedy" = greedy_result ,#n = 1000000
  times = 1,
  unit = "us"
)

Note!

Its is platform dependent and only work with MacOS/Linux or Windows.

"He who gives up [code] safety for [code] speed deserves neither." (via) or you can create an issue

• any issue email us: [e-mail]

rjkhan/RCourse-lab6 documentation built on May 6, 2019, 2:34 p.m.