时间戳

首页 > 解决方案 > 添加到目标的组合 - Julia lang

julia - 添加到目标的组合 - Julia lang

问题描述

我是 Julia 的新手，我以更简单的形式提出了这个问题，我需要进一步扩展它。我需要在一个数组中找到一个数字组合，这些数字加起来是某个目标并且是同一组的一部分。这是我的数据集。

target=941.44

Group   numbers
11  107.99
11  107.99
11  240.19
11  240.19
11  1943.82
11  4323.45
12  1232.76
12  1232.76
12  2538.72
12  2538.73
13  418.38
13  529.39
13  7949.13
13  10058.47
60  198.29
60  526.92
60  782.16
87  244.58
87  244.58
87  244.58
87  244.6
87  1467.5
132 435.67
132 1001.93
132 1742.66
132 4007.71
132 4753.91
132 19015.64
134 28.17
134 253.56
134 280.3
134 2522.69
141 212.33
141 318.49
141 554.57
141 831.86
141 1592.45
141 4159.3
180 131.64
180 230.77
180 240.44
180 263.27
180 313.81
180 394.91
180 461.54
180 480.87
180 526.55
180 627.63
180 692.3
180 721.31
180 923.07
180 941.44
180 961.74
180 1255.25
180 1316.37
180 2307.67
180 2404.35
180 3138.12
430 7006.42
430 9693.36
430 13183
442 511.1
442 1378.44
442 1533.31
442 4135.32
527 6454.93
527 6454.94
527 12221.4
527 12221.41
535 267.27
535 267.28
535 356.37
535 1171.24
535 1171.24
535 1561.66
535 2289.34
535 2289.34
535 3052.46
1173    83.1
1173    83.1
1173    83.1
1173    83.1
1173    124.65
1173    349.62
1173    349.62
1173    349.62
1173    349.62
1173    373.92
1173    515.52
1173    515.52
1173    515.52
1173    515.52
1173    524.44
1173    773.28
1173    1396.92
1173    1396.92
1173    1396.92
1173    1396.92
1173    1573.32
1173    2095.38
1173    2319.81
1173    6286.13
1358    359.95
1358    493.32
1358    914.56
1358    1439.79
1358    1973.3
1358    2030.31
1358    3658.24
1358    8121.25
1361    109.64
1361    284.72
1361    592.23
1361    2083.18
1361    5409.72
1361    11252.29
1363    121.1
1363    181.65
1363    430.15
1363    645.22
1363    773.95
1363    1160.93
1602    788.71
1602    788.71
1602    913.15
1602    913.15
1602    4853.62
1602    4853.63
1737    1769.42
1737    1769.43
1737    3538.85
1740    551.07
1740    1023.42
1740    1241.28
1740    2305.24
1740    2659.17
1740    4938.45
2203    186.34
2203    186.34
2203    641.69
2203    641.69
2203    1490.75
2203    5133.48
2628    142.09
2628    142.09
2628    504.32
2628    504.32
2628    836.72
2628    836.72
2628    2557.68
2628    9077.76
2628    15060.99
2700    3699.2
2700    3699.2
2700    7398.41
2704    2618.7
2704    2618.7
2704    3012.7
2704    3012.71
2705    729.07
2705    3527.86
2705    6369.84
2705    7571.78
2705    16440.02
3069    414.41
3069    414.41
3069    414.41
3069    1243.23
3069    1657.64
3069    4144.12
3451    373.82
3451    523.35
3451    598.11
3451    1370.16
3451    1918.22
3451    2192.25
3618    791.73
3618    791.73
3618    1583.46
3618    4750.36
3643    4877.81
3643    7876.17
3643    14233.58
3801    41.94
3801    41.94
3801    59.02
3801    59.02
3801    83.88
3801    118.04
3801    167.76
3801    236.08
3801    503.29
3801    708.24
3805    27.55
3805    96.42
3805    151.51
3805    380.86
3805    696.64
3805    1333.01
3805    2094.72
3805    2438.23
3805    3831.51
3808    2337.44
3808    2337.45
3808    2337.45
3808    2337.45
3821    827.01
3821    3308.02
3821    4135.03
4127    73.56
4127    73.56
4127    73.56
4127    193.34
4127    193.34
4127    193.34
4127    420.09
4127    420.09
4127    420.09
4127    477.26
4127    477.26
4127    477.26
4127    1250.59
4127    3286.8
4127    7141.55
4127    8113.33
4370    7444.4
4370    7444.4
4370    9435.66
4370    9435.67
6405    558.17
6405    1012.76
6405    1302.4
6405    1481.25
6405    1860.57
6405    2363.1
6405    3375.85
6405    3456.24
6405    4937.49
6414    1654.41
6414    1654.41
6414    3308.82
6414    26470.58
7703    637.49
7703    913.87
7703    956.23
7703    1370.81
7703    1593.71
7703    2284.68
7703    3187.42
7703    4569.35
8547    1825.78
8547    1825.78
8547    4837.37
8547    4837.37

因此，对于目标 = 941.44，我只需要返回一个数字作为结果，它属于组 180。我有以下代码，在之前的问题中已经提供给我：

using JuMP, Cbc
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

标签： juliacombinationsknapsack-problemjulia-jump

解决方案

  1. 添加和比较浮点数是一个坏主意。将所有内容转换为Int（在您的情况下乘以 100）。
  2. 您需要以这种方式重新表述问题，使这仍然是一个 MILP 问题，否则解决它非常困难。这个问题是关于数学而不是 Julia，所以这对于 StackOverflow 来说是没有问题的。有一个门户https://math.stackexchange.com/用于数学问题
  3. 您的模型或多或少看起来像这样：
groupids = unique(group)
@variable(m, x[1:length(numbers)], Bin)
@variable(m, y[1:length(groupids))
@constraint(m, numbers'*x == target)
@constraint(m, sum(y) == 1)
for i in 1:length(numbers)
    groupid = group[i]
    @constraint(m, y[groupid] >= x[i])
end
optimize!(m)

祝你好运！优化是数学中一个重要且令人兴奋的部分。请注意，您应该熟悉有关该主题的有用材料https://www.chkwon.net/julia/

推荐阅读