This project focuses on the optimization of the Knapsack problem using multiple algorithmic techniques.
The Knapsack problem is a classic optimization problem where given a set of items with their weights and values, we aim to select a combination of items that maximizes the total value while respecting a given weight constraint.
This repository contains implementations of various algorithms to tackle the Knapsack problem efficiently. The following techniques have been implemented and are available in this project:
The Branch & Bound technique is a systematic approach that divides the problem into smaller subproblems and uses bounds to prune branches that are not optimal. It guarantees an optimal solution for the Knapsack problem.
The Total Value Greedy approach selects items based on their total value, prioritizing items with higher values. It is a heuristic technique that provides a fast but not necessarily optimal solution.
The Greedy Weight technique selects items based on their weight, choosing items with lower weights first. It is another heuristic approach that provides a quick but suboptimal solution.
The Gray Wolf Optimization Algorithm is a metaheuristic algorithm inspired by the hunting behavior of gray wolves. It mimics the social hierarchy and hunting patterns of wolves to optimize the Knapsack problem.
Tabu Search is a metaheuristic algorithm that explores the search space by moving from one solution to another based on certain criteria. It uses memory structures to prevent revisiting previously explored solutions.
The Greedy Profit technique selects items based on their profit, prioritizing items with higher profits. It is another heuristic approach that provides a quick but suboptimal solution.
The Extended Efficiency technique combines both weight and profit factors to select items. It calculates the efficiency ratio of each item and chooses items with higher efficiency ratios.
The Greedy Efficiency technique selects items based on their efficiency ratio, which is calculated as the ratio of profit to weight. It prioritizes items with higher efficiency ratios.
The Genetic Algorithm is a population-based metaheuristic inspired by the principles of natural selection and genetics. It evolves a population of candidate solutions to find an optimal or near-optimal solution for the Knapsack problem.