greedy_knapsack: Greedy approximation algorithm for solving knapsack problem

In mpirmoradiyan/knapsack: Three approaches to deal with knapsack problem

Description

greedy_knapsack(x, W) returns the solution for knapsack problem using Greedy approximation algorithm.

Usage

greedy_knapsack(x, W)

Arguments

x	A data.frame with two variables ("w" , "v"). Every observation (row) in this data frame is an item with a weight (w) and a value (v).
W	A numeric scalar which is the maximum capacity of the knapsack.

Details

This function solves the Knapsack probem using Greedy approximation approach. The knapsack problem is a discrete optimization problem where we have a knapsack that can take a limited weight W and we want to fill this knapsack with a number of items i = 1, 2 ,...,n; each with a weight(w) and a value(v). The goal is to find the knapsack with the largest value of the elements added to the knapsack.

Value

A list with names $value, indicating maximum value of the items picked into the the knapsack , and $elements which states which items (rows) in data.frame were selected out to put into the knapsack.

References

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

Examples

 greedy_knapsack(data.frame(w=c(3660,3749,1145,3322),v=c(9899,4384,6999,8890)),W =3500)
 

mpirmoradiyan/knapsack documentation built on Nov. 4, 2019, 7:31 p.m.