In abhi-vellala/732A94lab6: Knapsack Problem Algorithms

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

library(knapsack)

Description

Package with three different functions for solving the so-called knapsack problem, which is considered NP-hard.

It is basically an optimization problem where a knapsack of limited weight has to be filled with a number of items of different value and weight, aiming to have the highest total value at the end. It is an open (Millennium Prize) problem, whether it is or is not possible to solve these problem in polynomial time.

The knapsack package offers the oportunity to study the computational complexity of different algorithms.

Usage

install.packages("devtools")

devtools::install_github("abhi-vellala/732A94lab6")

Functions

brute_force_knapsack(x,W)

Solution to the knapsack problem using brute-force search.
The algorithm goes through all possible alternatives and returns the maximum value found.
Correct answer guaranteed in all situations.

This function was optimized by detecting its bottlenecks with the lineprof function. The inital code was enumerating all possible combinations in binary form using the intToBit() function. After performing optimization tests, it was seen that it was more efficient to use combn() function to generate all possible permutations of items. Hence, combn() function was implemented.

Runtime for 16 items with parallel=FALSE: around 0.7 seconds.
Runtime for 16 items with parallel=TRUE: around 0.07 seconds.

Input:

• x: A dataframe with 2 variables:
  • v: values of the items.
  • w: weights of the items.

• W: An integer that represents the capacity of the knapsack in Kg.

• parallel: Optional argument to parallelize over the available cores. Default value is FALSE.

Output:

A list with 2 variables:

• value: Final weight of the knapsack.

• elements: Items that were added to the knapsack.

dynamic_knapsack(x,W)

Solution to the knapsack problem using Dynamic Programming.
The algorithm solves the knapsack problem exact by iterating over all possible values of weight.

Runtime for 500 items: around 22 seconds.

Input:

• x: A dataframe with 2 variables:
  • v: values of the items.
  • w: weights of the items.
• W: An integer that represents the capacity of the knapsack in Kg.

Output:

A list with 2 variables:

• value: Final weight of the knapsack.

• elements: Items that were added to the knapsack.

greedy_knapsack(x,W)

Solution to the knapsack problem following a greedy approach.
The algorithm solves the knapsack problem exact by iterating over all possible values of weight.
Do not expect an exact result.

Runtime for 1000000 items: around 20 seconds.

Input:

• x: A dataframe with 2 variables:
  • v: values of the items.
  • w: weights of the items.
• W: An integer that represents the capacity of the knapsack in Kg.

Output:

A list with 2 variables:

• value: Final weight of the knapsack.

• elements: Items that were added to the knapsack.

Examples

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

brute_force_knapsack(x = knapsack_objects[1:8,], W = 3500)
brute_force_knapsack(x = knapsack_objects[1:16,], W = 3500, parallel=TRUE)
dynamic_knapsack(x = knapsack_objects[1:500,], W = 2000)
greedy_knapsack(x = knapsack_objects[1:1000000,], W = 2000)

abhi-vellala/732A94lab6 documentation built on Oct. 31, 2019, 1:54 a.m.