In akilahmd/Knapsackpackage: Takes a vector of values and weights and also a maximum limit of weight that a scak can hold

Knapsack Package Introduction

The Knapsack Package implements methods for solving the knapsack problem with the application of functions:

1.brute_force_knapsack

2.knapsack_dynamic

3.greedy_knapsack

How to generate dataset

set.seed(42)
n <- 2000
knapsack_objects <-
  data.frame(
    w=sample(1:4000, size = n, replace = TRUE),
    v=runif(n = n, 0, 10000)
  )

brute_force_knapsack

brute_force_knapsack implements a function where you call knapsack brute force(x, W) that takes a data.frame with two variables v and w and returns the maximum knapsack value and which elements (rows in the data.frame). Argument W is the knapsack size:

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

$value
[1] 16770

$element
[1] 5 8

Question: How long time does it takes to run the algorithm for n = 16 objects?
system.time(brute_force_knapsack(knapsack_objects[1:16,],3500))
   user  system elapsed 
      0       0       0 

knapsack_dynamic

This function should return the same results as the brute force algorithm, but unlike the brute force it should scale much better.

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

$value
[1] 16770

$elements
[1] 5 8

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

system.time(knapsack_dynamic(knapsack_objects[1:500,],3500))
   user  system elapsed 
  18.98    0.08   19.16 

greedy_knapsack

This algorithm will not give an exact result (but it can be shown that it will return at least 50% of the true maximum value), but it will reduce the computational complexity considerably.

greedy_knapsack(knapsack_objects[1:8,],3500)

$value
[1] 15428

$elements
[1] 8 3

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

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

system.time(greedy_knapsack(knapsack_objects[1:1000000,],3500))
   user  system elapsed 
   3.08    0.09    3.16   

akilahmd/Knapsackpackage documentation built on May 12, 2019, 4:42 a.m.