What is it?
NP-Hard problems or problems that have no algorithm to efficiently find an optimal solution.
The Knapsack Problem
Here the goal is to fit as many items in a knapsack as possible and optimize the value of the total items in the knapsack. For instance if the knapsack holds 20kg and there are items $10@10kg, $20@20kg which combination of items will give us the optimized value constrained by the size of the knapsack?
Take items according to a single metric and in order. For example take items according to weight until the knapsack is full, take items according to value until full or take items by a new metric, value per kg, until full.
Greedy Algorithms is fast and gives a baseline, or a solution to try and beat when exploring other methods.
- Decision Variables
- Variable Constraints
- Objective Function