Applying Three Diferrent Methods for Solve 0-1 Knapsack Problem

About the Repository

This repository was created for the subject of Computer Theory. The propose of this subject is to improve your skills to solve the 0-1 knapsack problem of different ways. The techniques used were Dynamic Programing and two metaheuristics (which are GRASP and TABU search).

0-1 Knapsack Problem Description

Example of 0-1 knapsack problem.

The image above, show one of example the 0-1 Knapsack Problem, where which boxes should be chosen to maximize the amount of money while still keeping the overall weight under or equal to 15 kg. For know more about the concepts of this problem, please just click in this link.

Assignments Description:

Assignment 1: Dynamic Programing

The proposal of this assignment is use dynamic programing to findo the optimal solution of different instance of the 0-1 knapsack problem. The code of implementation can be show [clicked here][dynamic_programing.py].

Assignment 2: GRASP Metaheuristic

The goal of this second assignment is using GRASP metaheuristic for solve the 0-1 Knapsack problem. Therefore, as GRASP isn't optimal solution and of metaheuristic, then the results of each instance are close to the optimal. But in some instance, the result are the same of the optimal solution.

Assignment 3: TABU Metaheuristic

Tabu metaheuristic is some of search methods using to optimazing the the GRASP metaheuristc. For more details about the concepts, please readme the paper Fred W. Glover (1986). Anyway, the result of this technique for 0-1 Knapsack problem was very satisfactory.

Getting Started

Prerequisites

  For get all of the algorithms you need to understand the "0-1 Knapsack problem" and what's metaheuristic.

Usage

I other to run all of the methods, you need activate the venv (virtual environment) type in your terminal the following code:

  source venv/bin/activate

The next step is run dynamic_programing, GRASP, and TABU implementations. For run the dynamic programing just type the follow command in your terminal:

  python dynamic_programing.py

Already to run the GRASP implementation, just type the follow command in your terminal:

  python grasp.py

And finally the last technique is the TABU search, and for run the script just type the follow command in your termina:

  python tabu.py

Some Results

Bellow, follow some graphic results between mataheuristics (GRASP, TABU) and dynamic programming.

GRASP vs Dynamic Programing

Correlation between dynamic programing and GRASP metaheuristic using as score with metric.

TABU vs Dynamic Programing

Correlation between dynamic programing and TABU metaheuristic using as score with metric.

AcKnowledgment

Thanks for the teacher PhD Eduardo Theodoro Bogue for all the tips about the concepts of the methods.

Sincerely Neemias B. Silva.