knapsack_dynamic: A dynamic programming solution to 0/1 Knapsack problem

In thozh912/Lab6: Performace code for knapsack problem

Description

This function solves the 0/1 Knapsack problem using dynamic programming

Usage

knapsack_dynamic(x, W)

Arguments

x	A data.frame with two columns named in order "w" and "v" Every row in x is an object with weight w and value v.
W	A numeric scalar which is the limit of the weight the knapsack can carry.

Details

The Knapsack problem is a combinatorial optimization problem where one tries to fill a limited weight knapsack with objects of as high a total value as possible. Every object has a positive weight and value associated with itself.

Value

list A list with names $value, telling the maximum value of the knapsack and $elements which indicates which row objects in data.frame x was put in the knapsack.

References

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

Examples

knapsack_dynamic(data.frame(w=c(20,30,40,50),v=c(2,2,1,2)),W =20)

thozh912/Lab6 documentation built on May 31, 2019, 11:18 a.m.