Skip to content

Submission Yann Paillard

Paillard Yann requested to merge ypaillard/hpc4subsetsum:main into main

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

Merge request reports

Loading