I'm new to Julia. Is there a way to add up elements from a list that add up to a certain value target? I have done this with Python's itertools library like in the example below but I find it extremely slow for larger datasets.
import itertools
numbers = [1, 2, 3, 7, 7, 9, 10]
result = [seq for i in range(len(numbers), 0, -1) for seq in itertools.combinations(numbers, i) if sum(seq) == 10]
print result
While like mentioned by Kermit the problem is NP-hard, it is still worth knowing how to approach such problems. While some types of them have dedicated heuristics, the easiest and fastest thing you can do is to use a solver:
using JuMP, Cbc
numbers = [1, 2, 3, 7, 7, 9, 10]
target = 35
m = Model(Cbc.Optimizer)
@variable(m, x[1:length(numbers)], Bin)
@constraint(m, numbers'*x == target)
optimize!(m)
res_x = round.(Int,value.(x))
@assert numbers'*res_x == target
For larger sets of numbers this code will be several orders of magnitude faster than yours. The speed can be further increased by using commercial solvers (Gurobi, CPLEX, Fico) instead of Cbc.
However CBC seems to be quite good (even for larger applications). have a look at this benchamark for numbers having 50_000 elements that takes 17s to solve with Cbc:
using JuMP, Cbc, StatsBase, Random
Random.seed!(0)
numbers = rand(1:30_000,50_000)
target = sum(sample(numbers,45_000,replace=false))
m = Model(Cbc.Optimizer)
@variable(m, x[1:length(numbers)], Bin)
@constraint(m, numbers'*x == target)
And now:
julia> @time optimize!(m)
...
Result - Optimal solution found
Objective value: 0.00000000
Enumerated nodes: 605
Total iterations: 615
Time (CPU seconds): 7.57
Time (Wallclock seconds): 7.57
Total time (CPU seconds): 7.60 (Wallclock seconds): 7.60
17.666201 seconds (40.22 M allocations: 2.372 GiB, 5.82% gc time, 0.83% compilation time)