Algorithm to find best combination
33 ビュー (過去 30 日間)
古いコメントを表示
I am looking for a algorithm that will help me to choose the combinations with the minimum sum. Let's say I have differents combinations of numbers and for each of them I have a cost. I have to choose the combinations that will cover all the numbers but with the minimum cost. For example
Combinations with numbers 2 to 7
Combination Cost
________________ _______
2 3 4 5 10.9084
2 3 4 6 10.3335
2 3 4 7 8.8927
2 3 5 6 11.3927
2 3 5 7 11.4411
2 3 6 7 11.5541
(...)
I was looking for hours for severals algorith, but no one is doing exactly what I want. Can someone direct my research to the right algorithm?
Thanks.
Yannick
0 件のコメント
採用された回答
Walter Roberson
2018 年 4 月 14 日
For up to about 11 items in the set, then usually the fastest approach is to generate all the combinations and run the calculation in vectorized form over all of them, choosing the one that gives the best result.
Once you get to roughly 12 then the number of possibilities starts becoming large enough that more complex approaches start winning.
Using combinations of integers is a form of integer programming. MATLAB used to have a separate integer-only programming function, but it was replaced by "mixed integer" routines, which are routines which can take a mix of integer constraints and continuous bound constraints. https://www.mathworks.com/help/optim/ug/mixed-integer-linear-programming-algorithms.html
The difficulty with intlinprog() is that it has real way to say that only combinations (or permutations) are to be used, as opposed to simply integers within a range but which might be repeated. But if your function works with ordered inputs, then it is possible to program it by using the A, b, matrices, where for each adjacent pair of values you would configure weights 1 for x(K) and -1 for x(K+1) and have -1 in the corresponding element of b: x(K)-x(K+1) <= -1 is true for integer x only if the values are sorted in increasing order.
0 件のコメント
その他の回答 (0 件)
参考
カテゴリ
Help Center および File Exchange で Performance and Memory についてさらに検索
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!