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 |
Edited by Paillard Yann