Combinations that add up to a number - Julia lang

Question

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  

Answer 1

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)

Answer 2

this is known as the Knapsack problem, which has no known effective solution, meaning that the only known solutions has a time complexity which grows eksponentiel with the number of numbers, (NPC) If you happen to find an effective solution to this problem you will win one million dollar, as the problem P vs. NP is one of the millenium problems