Submission Yann Paillard

Merge Request: Subset Sum Problem - High-Performance Computing

Overview

This merge request introduces the implementation of the Subset Sum Problem using various Dynamic Programming approaches in a High-Performance Computing context. The implemented methods include solving the problem with and without threads, and using sparse matrices for optimization.

Implementation Details

The program handles the Subset Sum Problem, where it takes a set of integers, a target sum, and the maximum value in the set. It then identifies a subset of numbers that sum up to the target. Additional features include density calculation of the set and performance timing under different conditions.

Methods Implemented

Method	Description	study
solve	Basic dynamic programming approach without threads	✅
solve with thread	Utilizes threading for parallel computation	✅
solve with sparse matrix	Employs a sparse matrix for efficient computation	✅
solve with sparse matrix and thread	Combines sparse matrices with threading for optimal performance	✅