Knapsack with Priority Queue

Background

The objective of this project was to write a user-defined R function that solves the celebrated “Knapsack Problem” for a general number of items using a priority queue.

This project was for one of my undergraduate courses.

Method

Inputs:

  1. a vector, COST, which represents the costs of the items you want to include in the knapsack

  2. a vector, BENEFIT, which represents the benefits of the items you want to include in the knapsack

  3. a value, CAP, which represents the capacity of the knapsack

Outputs:

  1. a vector, Best.Vector, which is the binary vector that contains a 1 in the jth position if the jth item is packed and a 0 in the jth position if it is not packed

  2. a value, Best.Benefit, which represents the pro fit of Best.Vector

  3. a value, Best.Cost, which represents the cost of Best.Vector

Flowchart

 
Knapsack with Priority Queue Flowchart.png