2

我是朱莉娅的新手。有没有办法将列表中的元素加起来达到某个值目标？我已经使用 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
4

2 回答 2

5

这被称为背包问题，它没有已知的有效解决方案，这意味着唯一已知的解决方案具有时间复杂度，随着数字的数量增加 eksponentiel，（NPC）如果你碰巧找到了这个问题的有效解决方案，你会赢得一百万美元，因为问题 P 与 NP 是千年问题之一

于 2021-01-08T23:51:26.423 回答
3

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

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 似乎相当不错（即使对于更大的应用程序）。看看这个benchamarknumbers有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)
于 2021-01-09T12:48:27.670 回答