5  SubSet Sum

5.1 Introduction

Given a set of integers \(S\) and an integer \(M\), we want to find the biggest subset sum of \(S\) such that the sum of its elements does not exceed \(M\).

The associated decision problem is to find a subset sum that is strictly equal to \(M\), the existence of such a set is known to be NP-Hard.

Perhaps, there exist two heuristics for the above problem: LLL and a dynamic programming approach.

Remark : the general SubSet Sum problem allows \(S\) to be a MultiSet.

5.2 Code

Let \(S\) be a python set of integers and \(M\) the target value.

S = set(<values>)
M = <target_value>

To find a solution to the subset sum problem, create a subset and solve it.

problem = SubSet(S, M)
dynamic_solution = problem.solve_dynamic_prog()
LLL_solution = problem.solve_LLL()

• Dynamic
  • solve_dynamic_prog returns a couple (target, chosen elemements), as if there is no solution to the problem, it will give the closest to the target.
    
• LLL
  • solve_LLL returns a vector corresponding to the chosen elements

Alternative constructors :

• Concatenantion :
  • SubSet(S + M)
• Random example :
  • SubSet.generate_random_low_density_subset_problem(number_of_elements, density)
  • If you dont specify parameters, the number of elements will be a random number between 0 and 20, and the density will be 0.5

5.2.1 Examples

5.2.1.1 LLL algorithm

To perform a single, precise test:

set = SubSet([23603, 6105, 5851, 19660, 8398, 8545, 14712], 37760)
X = set.solve_LLL()
assert np.dot(X, [23603, 6105, 5851, 19660, 8398, 8545, 14712]) == 37760

X = [0, 1, 0, 0, 1, 1, 1]

To parameterize set length and density, and study the algorithm’s performance:

solved_count = 0
unsolved_count = 0
total_density = 0
n = 4

for i in range(1000):
    subset_problem = SubSet.generate_random_low_density_subset_problem(n,density=0.2)
    X = subset_problem.solve_LLL()
    density = subset_problem.density()
    
    if X is not None:
        solved_count += 1
        total_density += density
    else:
        unsolved_count += 1

avg_density = total_density / solved_count if solved_count > 0 else 0

Benchmark Table: n = 4
Number of problems solved: 555
Number of problems unsolved: 445
Average density: 0.19783403475538835

The test above can be modified in the tests/subset_sum.py file.

5.2.1.2 Dynamic programming

problem = SubSet([23603, 6105, 5851, 19660, 8398, 8545, 14712], 37760)

dynamic_solution = problem.solve_dynamic_prog()

Dynamic solution : (37760, [6105, 8398, 8545, 14712])