加起来等于一个数的组合 - Julia lang

Question

我是 Julia 的新手。有没有办法将列表中的元素加起来达到某个值目标？我已经使用 Python 的 itertools 库完成了此操作，如下例所示，但我发现它对于较大的数据集来说非常慢。

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

这被称为 Knapsack problem，它没有已知的有效解决方案，这意味着唯一已知的解决方案具有时间复杂度，随着数字的数量增加，（NPC）如果你恰好找到这个问题的有效解决方案你将赢得一百万美元，因为P vs. NP问题是千年难题之一

Answer 2

虽然正如 Kermit 所提到的，该问题是 NP-hard 问题，但仍然值得了解如何解决此类问题。虽然其中一些类型具有专门的启发式算法，但您可以做的最简单和最快的事情是使用求解器：

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 可以进一步提高速度。

然而 CBC 似乎相当不错（即使对于较大的应用程序）。看一下 numbers 的这个基准，其中 50_000 个元素需要 17 秒才能用 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

Combinations that add up to a number - Julia lang

arrays

julia

method-combination