Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
785 views
in Technique[技术] by (71.8m points)

Combinations adding up to a target - Julia lang

I am new to Julia, I've asked this question in a simpler form, I need to expand it a bit more. I need to find a combination of numbers in an array that add up to a certain target AND are a part of the same group. Here is my dataset.

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

So for the target = 941.44, I need only one number to be returned as the result, which belongs to group 180. I have the following code which was already provided to me in an earlier question:

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

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)
  1. Adding and comparing float numbers is a bad idea. Convert everything to Int (in your case multiple by 100).
  2. You need to reformulate the problem in such a way that this is still a MILP problem otherwise solving it is very difficult. This problem is about mathematics not Julia so this is no question for StackOverflow. There is a portal https://math.stackexchange.com/ for mathematics questions
  3. You model will look more or less like this:
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)

Good luck! optimization is a big and exciting part of mathematics. Note that there is a useful material on that subject that you should get familiar with https://www.chkwon.net/julia/


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...