lab6-package: Knapsack problem algorithms

In alede379/lab6: Knapsack problem algorithms

Description

The knapsack problem is a discrete optimization problem, in the package there are three different algorithms to approach it: Brute force search, Dynamic programming, Greedy heuristic.

Details

This package contains three different functions for solving the knapsack problem:

1. brute_force_knapsack(x,W) : goes through all possible combinations of item and return the maximum value found;

2. knapsack_dynamic(x,W) : iterates over all possible values of w to find the optimum;

3. greedy_knapsack(x,W) : sorts the items of decreasing order of value per unit of weight and then it proceeds to insert them into the sack until there is not more room in the sack.

All three functions take two elements:

• a dataframe containing the values and the weights of each item (x);

• the knapsack maximum weight (W).

All of them return the maximum value they found and the elements choosen to reach that value.

Author(s)

Barakat Bruno [aut, cre], De Biase Alessia [aut]

Maintainer: Alessia De Biase <[e-mail]>

References

https://en.wikipedia.org/wiki/Knapsack_problem

alede379/lab6 documentation built on May 21, 2019, 2:31 a.m.