Въпрос за алгоритам и варианти за получавенето на дадена сума.


1

Здравейте приятели!
Трябва да алгоритъм, който да генерира всички възможни валианта да получа сумата на дадено число без повторения. Също имам и няколко ограничения - броя на числата, които мога да използвам, както и големината им.

Премер:

$my_number = 20;
$array_max_size = 6;
$max_number = 5;

Съответно първите няколко члена на масива са:
 

    [0] => Array
        (
            [0] => 5
            [1] => 5
            [2] => 5
            [3] => 3
            [4] => 1
            [5] => 1
        )

[1] => Array ( [0] => 5 [1] => 5 [2] => 5 [3] => 2 [4] => 2 [5] => 1 )
[2] => Array ( [0] => 5 [1] => 5 [2] => 4 [3] => 3 [4] => 2 [5] => 1 )
[3] => Array ( [0] => 5 [1] => 5 [2] => 4 [3] => 2 [4] => 2 [5] => 2 )
и т.н.
П.П. Претърсих нета и такова животно няма. Разбрах че в по общия случай проблема се нарича Partition Problem

 




Отговори



0

Важно е да можеш да си разбиеш задачата на подзадачи. В случая просто ти трябва алгоритъм за генериране на комбинации. След това имаш две условия - първо, сумата на генерираната комбинация да е равна на $my_number, и второ - ако е равна, до сега да не си генерирал такава комбинация. Сега вече имаш да решиш три по-лесни проблема :)


от neutrino (3376 точки)


0
Всъщност проблема е, че като генерирам всички комбинации(които са твърде много), php-то зависва( Allowed memory size of 134217728). Затова трябва паралелно да се извършват тези три подзадачи.

от webmatrix (825 точки)

0
Ето по-добра идея. Първо, започваш да генерираш комбинацията от първия елемент, като въртиш цикъл от най-голямото число ($max_number) към на-малкото. Значи имаш {5}. След това задачата се свежда пак до същата задача - да представиш остатъка ($max_number - 5 = 15), като сума от ($array_max_size - 1 = 5) елемента. Пак започваш от най-голямото. Сега ще имаш {5 + 5}. Сега вече трябва да представиш числото (15 - 5 = 10), като сума от 4 елемента. Пак от най-голямото ще имаш {5 + 5 + 5}. Т.е имаш рекурентна зависимост, която може да използваш. За да избегнеш повторенията, проверяваш дали всеки следващ елемент на комбинацията не е по-голям от предходния. Така си генерираш комбинациите подредени в низходящ ред и няма как да се повтарят :)

от neutrino (3376 точки)


0

Това не са ли просто вариации без повторение? Тук ги има в псевдо код, но при мен се чупи енкодинга: http://www.nakov.com/pranka/additional-materials/1.3-Kombinatorni-konfiguracii.txt .

Може да погледнеш и това https://github.com/Nachev/Telerik/blob/master/Course_C%23Part2/Homework/Arrays/Variations/Variations.cs и най-вече метода CalcVariationsIterattive , където може да проверяш за достигната сума и да я запазваш.

А ако знаеш точно колко ще са елементите всеки път, както в случая 6, правиш толкова на брой вложени цикли и си готов. Само не се занимавай с рекурсия, че трябва да се оптимизира доста за да не е алчна.




1
Пиша ти го така, в полу-псевдо код че е на notepad :)) Не уточняваш дали винаги трябва да използваш 6 числа или не. Решението по-долу използва масив с големина максималната разрешена. Всеки елемент е число от 1 до максималното. При всяко рекурсивно викане се попълва следващия индекс от масива и се проверява дали е достигната или премината търсената сума. Ако е достигната се добавя масива в отговорите - само трябва да провериш да нямаш такъв масив вече (такава комбинация от числа).
 
var maxSize = 6;var maxNumber = 5;var minNumber = 1;var targetSum = 20;
var vector = new int[maxSize];List<int[]> combinations = new List<int[]>();
public static void Generate(int[] vector, int index) {
    var currComboSum = 0;
    for (var i =0; i < index; i++) {
        currComboSum+= vector[i];
        if (currComboSum > targetSum) return;
    }
    if (currComboSum == targetSum) combinations.Add(Array.copy(vector));
    if (index == maxSize) return;
    for (var i = minNumber; i <= maxNumber; i++) {
        vector[index] = i;
        Generate(vector,index+1);
        vector[index] = 0;
    }
}

от dzhenko (3893 точки)


1

Ето едно решение, което използва рекурсивната зависимост, която описах по-горе в коментара си:

Решение (C#): http://pastebin.com/HGYGqPKF

Ето изхода за примерните данни, които си дал:

myNumber = 20; maxElements = 6; maxNumber = 5;

  1. 20 = 5 + 5 + 5 + 5
  2. 20 = 5 + 5 + 5 + 4 + 1
  3. 20 = 5 + 5 + 5 + 3 + 2
  4. 20 = 5 + 5 + 5 + 3 + 1 + 1
  5. 20 = 5 + 5 + 5 + 2 + 2 + 1
  6. 20 = 5 + 5 + 4 + 4 + 2
  7. 20 = 5 + 5 + 4 + 4 + 1 + 1
  8. 20 = 5 + 5 + 4 + 3 + 3
  9. 20 = 5 + 5 + 4 + 3 + 2 + 1
  10. 20 = 5 + 5 + 4 + 2 + 2 + 2
  11. 20 = 5 + 5 + 3 + 3 + 3 + 1
  12. 20 = 5 + 5 + 3 + 3 + 2 + 2
  13. 20 = 5 + 4 + 4 + 4 + 3
  14. 20 = 5 + 4 + 4 + 4 + 2 + 1
  15. 20 = 5 + 4 + 4 + 3 + 3 + 1
  16. 20 = 5 + 4 + 4 + 3 + 2 + 2
  17. 20 = 5 + 4 + 3 + 3 + 3 + 2
  18. 20 = 5 + 3 + 3 + 3 + 3 + 3
  19. 20 = 4 + 4 + 4 + 4 + 4
  20. 20 = 4 + 4 + 4 + 4 + 3 + 1
  21. 20 = 4 + 4 + 4 + 4 + 2 + 2
  22. 20 = 4 + 4 + 4 + 3 + 3 + 2
  23. 20 = 4 + 4 + 3 + 3 + 3 + 3

 


от neutrino (3376 точки)