In uzairjan/AdvR6: Knapsack Problem

1 Brute force search

library(lab06)

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))

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

getTime <- function(sample, FUNC){
  time = system.time({for (i in 1:sample) FUNC})/2
  return(time)
}

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

time <- getTime(2, brute_force_knapsack(x = knapsack_objects[1:16,], W = 3500))
 print("Observed times:")
time

Question: What performance gain could you get by parallelizing brute force search?

para_time <- getTime(2, brute_force_knapsack(x = knapsack_objects[1:16,], W = 3500, p=TRUE))
print("Observed times:")
para_time

we can observe that the user time gets smaller with the system time is increased with same sample size

Dynamic programming

examples from dynamic programming

obj <- lab06::knapsack_dynamic()

obj$knapsackDynamic(df = knapsack_objects[1:8,], W = 3500)
obj$knapsackDynamic(df = knapsack_objects[1:12,], W = 3500)
obj$knapsackDynamic(df = knapsack_objects[1:8,], W = 2000)
obj$knapsackDynamic(df = knapsack_objects[1:12,], W = 2000)

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

obj <- lab06::knapsack_dynamic()
d_time <- getTime(2, obj$knapsackDynamic(df = knapsack_objects[1:500,], W = 3500))
d_time

Greedy heuristic

examples:

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

Question: How much time does it take to run the algorithm for n = 1000000 objects?

n <- 1000000
knapsack_objects_1000000 <-
data.frame(
w=sample(1:4000, size = n, replace = TRUE),
v=runif(n = n, 0, 10000)
)

g_time <- getTime(2,greedy_knapsack(x = knapsack_objects_1000000, W = 3500))
print("Time for 1000000 Objects")
g_time

Performance assessment and code optimization

Question: What performance gain could you get by trying to improve your code?

Tried to use While loop in place of using for loop to reduce time taken to create a list or vector compare to for loop. Optimizing our algorithm, we tried eliminate weight that is greater than the knapsack size. Created parallel version of this algorithm and divided problem into iterations and distributed iterations to the cores. Tried to replaced the loops for vectorization to possibly reduce execution time.

For parallelize the brute programming

add parameter p = T

brute_force_knapsack(x = knapsack_objects[1:8,], W = 3500, p = T)
brute_force_knapsack(x = knapsack_objects[1:8,], W = 2000, p = T)

uzairjan/AdvR6 documentation built on Dec. 23, 2021, 2:06 p.m.