总计为数字的组合-朱莉娅·朗(Julia Lang) [英] Combinations that add up to a number - Julia lang

问题描述

我是朱莉娅(Julia)的新手.有没有一种方法可以将列表中的元素相加并达到某个特定的价值目标?我已经使用Python的itertools库完成了此操作，如下面的示例所示，但是对于较大的数据集，我发现它非常慢.

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  

推荐答案

尽管像Kermit提到的那样，问题是NP难题，但仍然值得知道如何解决此类问题.尽管其中某些类型具有专用的启发式方法，但您可以做的最简单，最快的操作是使用求解器:

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

对于更大的数字集，此代码将比您的数字快几个数量级.通过使用商用求解器(Gurobi，CPLEX，Fico)而不是Cbc，可以进一步提高速度.

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.

但是CBC似乎相当不错(即使对于较大的应用程序).看看这个具有 50_000 元素的 numbers 的基准测试，需要花费17秒的时间来解决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)

现在:

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)

这篇关于总计为数字的组合-朱莉娅·朗(Julia Lang)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！