加起来就是一个数字的组合 - 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屋！