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
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 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
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
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
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.