In menon1234/Lab06: This package gives the different ways to solve the knapsack problem

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

library(Lab06)
library(microbenchmark)
library(parallel)
n = 2000
knapsack_objects <- data.frame(
   w=sample(1:4000, size = n, replace = TRUE),
   v=runif(n = n, 0, 10000))

Description

This Package gives several solutions to solving the knapsack problem.The knapsack problem or rucksack 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. Some of which are Greedy approach, Dynamic approach and the brute force algorithm.

---

Brute Force algorithm (with parallelize)

Brute Force Algorithms refers to a programming style that does not include any shortcuts to improve performance, but instead relies on sheer computing power to try all possibilities until the solution to a problem is found.Here we have implemented this algorithm to solve the knapsack problem.

Example

#Lab06::brute_force_knapsack(x = knapsack_objects[1:8,], W = 2000)

---

Dynamic algorithm

Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming.

Example

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

---

Greedy algorithm

A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage with the intent of finding a global optimum.

Example

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

---

Profiling on each algorithm

Brute force

 #microbenchmark (Lab06::brute_force_knapsack(x = knapsack_objects[1:5,], W = 3500), times = 1)

Greedy algorithm

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

Dynamic Programming

microbenchmark (Lab06::knapsack_dynamic(x = knapsack_objects[1:800,], W = 3500), times = 1)

menon1234/Lab06 documentation built on Nov. 4, 2019, 6:25 p.m.