In abhijeet16/shazam: Knapsack Problem

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

library(shazam)
library(parallel)

The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

How to work with package Shazam

In the package Shazam, several methods are used to find the solution of knapsack problem.

Following are the methods

• brute_force_knapsack(x, W, parallel=FALSE)
  
• knapsack_dynamic(x, W)
  
• greedy_knapsack(x, W)
  Parameters:
  x - It is a data frame with two columns weight and value.
  W - It is the maximum weight that can be taken to calculate maximum profit.
  parallel - Default value - FALSE, If set to TRUE, it parallelizes over the detected cores.

Method 1 - brute_force_knapsack(x, W, parallel=FALSE)

brute_force_knapsack() is a way to find the solution of knapsack problem. In the brute force algorithm all the subsets of the items are found and the value of each subset is calculated. The subset of items with the maximum value and a weight less than equal to the maximum allowed weight gives the answer.
The time taken to calculate all the subsets is O($2^{n}$).

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

Method 2 - knapsack_dynamic(x, W)

knapsack_dynamic() is a way to find the solution of knapsack problem. The basic idea of Knapsack dynamic programming is to use a table to store the solutions of solved subproblems. In case of subproblem again, the solution is taken in the table without having to solve it again. Therefore, the algorithms designed by dynamic programming are very effective.
The time taken to calculate all the subsets is O(nW).

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

Method 3 - greedy_knapsack(x, W)

greedy_knapsack() is another way to find the solution of knapsack problem. The basic idea of the greedy approach is to calculate the ratio value/weight for each item and sort the item on basis of this ratio. Then take the item with the highest ratio and add them until we can't add the next item as a whole and at the end add the next item as much as we can.
The time taken to calculate all the subsets is O(nlogn).

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

Timing for all the algorithms

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

time_taken <- system.time(brute_force_knapsack(x = knapsack_objects[1:16,], W = 2000))
print("User time:")
time_taken[[1]]

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

time_taken <- system.time(knapsack_dynamic(x = knapsack_objects[1:500,], W = 3500))
print("User time:")
time_taken[[1]]

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

time_taken <- system.time(greedy_knapsack(x = knapsack_objects[1:100000,], W = 3500))
print("User time:")
time_taken[[1]]

Profiling

What performance gain could you get by trying to improving your code?
With profiling we observed that there were couple of bottlenecks. Earlier library(combinat) was used to create the combinations. Now,

comb = which(as.logical(intToBits(i)))

is used to create combinations.
We see significant performance gain after improving the code.

Parallelizing Brute Force

What performance gain could you get by parallelizing brute force search?
Parallelizing Brute Force Algorithm

time_taken <- system.time(brute_force_knapsack(x = knapsack_objects[1:16,], W = 2000, parallel = TRUE))
print("User time:")
time_taken[[1]]

There is a notable improvement in time taken when the Brute Force algorithm is Parallelized.

abhijeet16/shazam documentation built on Dec. 18, 2021, 9:30 p.m.