SHARE
TWEET

Untitled

a guest May 23rd, 2018 165 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include 'bstd.ch'
  2. #include 'xlangext.ch'
  3.  
  4. static _aNominal  // Запоминаемый массив номиналов
  5. static _mDoneSums // HashMap достигнутых сумм {сумма -> номер наименьшего номинала}
  6. static _errorSumNonNegative   := 'Набираемая сумма не может быть отрицательной'
  7. static _errorNomimalPositive  := 'Номиналы должны быть положительными'
  8.  
  9. /**   knapsack()   -> Жадный алгоритм набора суммы из доступных номиналов
  10.  *    @param   nSum     <-  Сумма, которую надо набрать (неотрицательная)
  11.  *    @param   aNominal <-  Массив номиналов (положительных)
  12.  *
  13.  *    @return  aResult   -> Массив упорядоченных по возрастанию используемых номиналов (nil - нет решения)
  14.  *
  15.  * NB: Использует наибольшие номиналы в первую очередь (т.е. как можно больше 'больших' номиналов),
  16.  *     но итоговый набор не обязательно(!!!) минимален по количеству
  17.  * EX: knapsack(300, {50, 150, 200}) => {50, 50, 200} (а не {150, 150})
  18.  *     Больше примеров в тестах в конце файла
  19.  *    
  20.  *     Итоговая асимптотика (очень большая оценка сверху): O(n^( ceil(Sum/m) ) ),
  21.  *     где n - количество номиналов, m - наименьший номинал, sum - искомая сумма
  22.  * (!) Есть ограничение на работу из-за стандартного стека (см. тест _speed)
  23.  */
  24. function knapsack(nSum, aNominal)
  25.    // Проверим на валидные значения
  26.    assert(!negative(nSum), _errorSumNonNegative)
  27.    AEval(aNominal, {|x| _assertPositiveNominal(x)})
  28.    // Запомним массив, чтобы не передавать ссылку на него постоянно
  29.    _aNominal := AClone(aNominal)
  30.    // Нет смысла сортировать массив каждый вызов
  31.    // Отсортируем от старших к младшим
  32.    ASort(_aNominal,,, {|aX, aY| aX > aY})
  33.    // Создадим пустой HashMap или очистим существующий
  34.    if _mDoneSums == nil
  35.       _mDoneSums := HashMap():new()
  36.    else
  37.       _mDoneSums:clear()
  38.    endif
  39.    // Запустим расчёт
  40. return _knapsack(nSum, 1)
  41.  
  42. /**
  43.  *  nSum - сумма, которую осталось набрать
  44.  *  nBeg - номер наибольшего номинала, который можно использовать
  45.  */
  46. static function _knapsack(nSum, nBeg)
  47. // Integer
  48.    local i, nCur
  49. // Array
  50.    local aRes
  51.  
  52.    // Если сумма отрицательная - нет ответа
  53.    if negative(nSum)
  54.       return nil
  55.    endif
  56.    // Если набрали сумму - выходим
  57.    if isZero(nSum)
  58.       return {}
  59.    endif
  60.    // Если уже набирали эту сумму с таким же или больше наименьшим номиналом
  61.    if (_mDoneSums:containsKey(nSum) .and. _mDoneSums:get(nSum) <= nBeg)
  62.       return nil
  63.    endif
  64.    // Запомним, что уже набирали эту сумму с данным наименьшим номиналом
  65.    _mDoneSums:put(nSum, nBeg)
  66.    // Перебираем с наибольших номиналов
  67.    for i := nBeg to len(_aNominal)
  68.       nCur := _aNominal[i]
  69.       if (aRes := _knapsack(nSum - nCur, i)) != nil
  70.          // Если решение найдено - добавим текущий в конец и выведем ответ
  71.          AAdd(aRes, nCur)
  72.          return aRes
  73.       endif
  74.    next i
  75. return nil
  76.  
  77. /** Функция для assert, т.к. в блок кода нельзя вставить данную макрокоманду */
  78. static procedure _assertPositiveNominal(x); assert(positive(x), _errorNomimalPositive); return
  79.  
  80. #ifdef _TEST_
  81.  
  82. // Проверка проброса ошибок в исключительных ситуациях
  83. procedure _Test_knapsack_error()
  84.    // Проверим, что не работает для отрицательной суммы и неправильных номиналов
  85.    AssertError({|| knapsack(-100, {1, 200})}, , _errorSumNonNegative )
  86.    AssertError({|| knapsack(1, {-1, 1, 50})}, , _errorNomimalPositive)
  87.    AssertError({|| knapsack(1, {20, 0, 50})}, , _errorNomimalPositive)
  88. return
  89.  
  90. // Основная проверка
  91. procedure _Test_knapsack_main()
  92.    local aNominal := {}
  93.  
  94.    aNominal := {200, 500, 1000}
  95.    AssertEquals({200, 200, 200}, knapsack(600, aNominal))
  96.    AssertEquals({500},           knapsack(500, aNominal))
  97.    AssertEquals(nil,             knapsack(300, aNominal))
  98.    AssertEquals(nil,             knapsack(100, aNominal))
  99.    // Проверим, что изменение входного массива извне не повлияет на результат
  100.    aadd(aNominal, 100)
  101.    AssertEquals(nil,            _knapsack(300, 1       ))
  102.    AssertEquals({100, 200},      knapsack(300, aNominal))
  103.  
  104.    aNominal := {100, 5, 1000, 500, 1, 5000, 2, 50, 10}
  105.    AssertEquals({100},           knapsack(100, aNominal))
  106.    AssertEquals({2, 2, 10, 100}, knapsack(114, aNominal))
  107.    AssertEquals({5, 10, 100},    knapsack(115, aNominal))
  108.    AssertEquals({1, 2},          knapsack(3  , aNominal))
  109.    AssertEquals({1, 2, 5, 10, 50, 100, 500, 1000, 5000}, knapsack(6668, aNominal))
  110.  
  111.    // Проверим, что не меняем исходный массив номиналов
  112.    AssertEquals({100, 5, 1000, 500, 1, 5000, 2, 50, 10}, aNominal)
  113.  
  114.    // Пример из описания функции
  115.    AssertEquals({50, 50, 200},   knapsack(300, {50, 150, 200}))
  116. return
  117.  
  118. // Проверка функции с дробными значениями
  119. procedure _Test_knapsack_float()
  120.    local aNominal := {}
  121.  
  122.    aNominal :=  {0.1, 0.5, 1.0}
  123.    AssertEquals({1, 1, 1, 1, 1}, knapsack(5,   aNominal))
  124.    AssertEquals({0.1, 0.5,   1}, knapsack(1.6, aNominal))
  125.    AssertEquals({0.1, 0.1, 0.5}, knapsack(0.7, aNominal))
  126. return
  127.  
  128. // Проверка скорости работы
  129. procedure _Test_knapsack_speed()
  130.    local aNominal := {}
  131.  
  132.    aNominal := {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}   // 10 наименьших чётных номиналов
  133.    AssertEquals(nil, knapsack(50001, aNominal) )      // 5 * 10^4 + 1 - нечётное, перебор всех вариантов
  134.    
  135. // Отрабатывает за ~6 секунд (время растёт псевдолинейно из-за больших отсечений по набранным суммам),
  136. // на бОльших тестах первым выходит из строя стек (StackOverflow) - из-за большой вложенности рекурсии
  137. // при данном тесте  вложенность ~25к; по документации ограничение стека - 50 000 байт;
  138. // эмпирически ограничение стека на вложенность данной функцией < 30к
  139. return
  140.  
  141. // Проверка dimasik-а
  142. procedure _Test_knapsack_1()
  143.    local aNominal := {100, 330, 510, 1020}
  144.    AssertEquals(aaFill(14, 100), knapsack(1400, aNominal))
  145. return
  146.  
  147. #endif // _TEST_
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top