Алгоритм для поиска сумм документов для нужной суммы

Форум Программирование Общие вопросы программирования (Dev)

Платформа 1С v8.3

1. BaldKiwi 25.03.21 04:01 Сейчас в теме

Добрый день, написал алгоритм, который должен был искать в массиве документов суммы документов которые лучше всего бы подходили к требуемой сумме, но столкнулся с проблемой, что не совсем корректно всё отрабатывает, может кто дать совет или подсказку? код ниже

Для каждого стр из ВсеДокументы Цикл
        МассивДокументов.Добавить(Новый структура("ТребуемаяСумма, Сумма", 
                                        ТребуемаяСумма, стр.Сумма));
    КонецЦикла;
                                    
    МассивПроверки = Новый Массив(ТребуемаяСумма,ВсеДокументы.Количество());
    
    Для сч = 0 по МассивДокументов[0].ТребуемаяСумма-1 Цикл
        МассивПроверки[сч][0] = 0;
    КонецЦикла;
                                                       
    Для сч = МассивДокументов[0].ТребуемаяСумма по ВсеДокументы.Количество() Цикл                        
        МассивПроверки[сч][0] = МассивДокументов[0].Сумма;
    КонецЦикла;
                                                                          
    Для Счетчик = 1 по МассивДокументов.ВГраница() Цикл
        Для сч = 0 по МассивДокументов[Счетчик].ТребуемаяСумма-1 Цикл
            МассивПроверки[сч][Счетчик] = МассивПроверки[сч][Счетчик-1];
        КонецЦикла;
        Для сч = МассивДокументов[Счетчик].ТребуемаяСумма по ВсеДокументы.Количество() Цикл
            МассивПроверки[сч][Счетчик] = Макс(МассивПроверки[сч][Счетчик-1], МассивПроверки[сч - МассивДокументов[Счетчик].ТребуемаяСумма][Счетчик - 1] + МассивДокументов[Счетчик].Сумма);
        КонецЦикла;
    КонецЦикла;
        
    ОставшаясяСумма = ТребуемаяСумма;
    МассивЛучшихДокументов = Новый Массив;
    
    Для Х = МассивЛучшихДокументов.ВГраница() по 1 Цикл
        Если МассивПроверки[ТребуемаяСумма-1][Х] <> МассивПроверки[ТребуемаяСумма-1][Х-1] Тогда
            МассивЛучшихДокументов.Добавить(МассивДокументов[Х]);
            ОставшаясяСумма = ОставшаясяСумма - МассивДокументов[Х].ТребуемаяСумма;
        КонецЕсли;
    КонецЦикла;
    Если МассивПроверки[ОставшаясяСумма][0] <> 0 Тогда
        МассивЛучшихДокументов.Добавить(МассивДокументов[0]);
    КонецЕсли;

Показать

По теме из базы знаний

Ответы

Подписаться на ответы Инфостарт бот

Свернуть все

2. alxarz 32 25.03.21 05:58 Сейчас в теме

(1)

что не совсем корректно всё отрабатывает

что именно? Задача о рюкзаке, полный перебор не лучший вариант решать такую задачу, а здесь вроде как он приведён, или ошибаюсь?

3. BaldKiwi 25.03.21 06:38 Сейчас в теме

(2)да, перебор происходит всех возможных вариантов и после уже ищется самый лучший вариант, но пролема на моменте

Для Счетчик = 1 по МассивДокументов.ВГраница() Цикл
        Для сч = 0 по МассивДокументов[Счетчик].ТребуемаяСумма-1 Цикл
            МассивПроверки[сч][Счетчик] = МассивПроверки[сч][Счетчик-1];
        КонецЦикла;
        Для сч = МассивДокументов[Счетчик].ТребуемаяСумма по ВсеДокументы.Количество() Цикл
            МассивПроверки[сч][Счетчик] = Макс(МассивПроверки[сч][Счетчик-1], МассивПроверки[сч - МассивДокументов[Счетчик].ТребуемаяСумма][Счетчик - 1] + МассивДокументов[Счетчик].Сумма);
        КонецЦикла;
    КонецЦикла;

а именно, во втором цикле "Для сч = МассивДокументов[Счетчик].ТребуемаяСумма по ВсеДокументы.Количество() Цикл"
Переменная сч = сумме, которую указывает пользователь, а вот количество документов намного меньше может быть, допустим сч = 10000 по 100 и в цикл просто не ныряет код, чтобы найти лучшие варианты

10. shurikvz 25.03.21 20:15 Сейчас в теме

(6) не надо данную задачу рекурсией делать. Не будет работать в общем случае. Будет вылетать на переполнении стека.

(3) если решать задачу о ранце - эмпирически у меня получается что после 30000 элементов в массиве (т.е. в твоем случае ТребуемаяСумма * ВсеДокументы.Количество() > 30000) - скорость вычисленя уже не удовлетворительная. Ну не предназначена 1с для решения подобного рода задач. Это мучать оператора ждать.
С полным перебором естественно - еще хуже.

Возможно стоит пересмотреть условия. Обязательна ли точная сумма?
Можешь рассмотреть следующие варианты реализации:
1) поиск сочетаний сумм документов с наиболее близкой к заданной. Сначала проходим смотрим нет ли 1-го документа с нужной суммой, потом сочетание из 2 документов берем смотрим, потом 3 документа, ну потом сочетания из 4 можно посчитать. Делается элементарно в цикле. Скорость работы хорошая.
2) либо просто детерменированный спуск по дереву в лучшем направлении. Набираем максимально близкую не превышающую сумму. Работает естественно быстро, но результат хуже чем у 1-го варианта.
Естественно оба варианта не гарантируют глобально-оптимальное решение.

11. SlavaKron 26.03.21 10:17 Сейчас в теме

(10)

эмпирически у меня получается что после 30000 элементов в массиве (т.е. в твоем случае ТребуемаяСумма * ВсеДокументы.Количество() > 30000)

А если нормализовать суммы с контролируемой погрешностью?

12. shurikvz 26.03.21 10:22 Сейчас в теме

(11) это как?
я для ускорения находил НОД, и соответственно уменьшал все суммы на него. Но НОД то не всегда существует.

13. SlavaKron 26.03.21 10:24 Сейчас в теме

(12) Вариантов много, например за единицу можно взять половину минимальной суммы - это не очень хорошая нормализация, но самая быстрая. (Считаем, что НОД просто не существует у рандомных сумм с двумя знаками после запятой)

4. pyrkin_vanya 497 25.03.21 07:01 Сейчас в теме

(1)а что значит подходили бы к требуемой сумме? Это как? Условия поточнее.

5. alxarz 32 25.03.21 07:28 Сейчас в теме

(3)

сч = МассивДокументов[Счетчик].ТребуемаяСумма

ну да, такого точно не должно быть
и

Для сч = 0 по МассивДокументов[Счетчик].ТребуемаяСумма-1 Цикл
МассивПроверки[сч][Счетчик] = МассивПроверки[сч][Счетчик-1];
КонецЦикла;

это если требуется найти 1000000, у нас массив такой будет? Нужно стререть и писать код заново... Не исправлять.

(4)

а что значит подходили бы к требуемой сумме? Это как?

есть 33 платежа на разные суммы, нам нужно подобрать на 5555руб, берем например 3, 11 и 28 - о, как раз 5555руб. получается. :)

7. BaldKiwi 25.03.21 11:34 Сейчас в теме

(5)Да, уже понял, что нужно полностью переписывать код, потому что не в ту сторону смотрел, если требуемую сумму указывали 10000, то массивов было 9999 и т.д.

Насчет суммы - если пользователь указывает сумму 10000, то из всех документов должны были выбраться документы с ближайшей общей суммой к 10000, но не больше, то есть, если получилось 3 "пачки" документов с суммами, 9000, 9600 и 9300, то должны были в массив конечный попасть документы, суммируя которые мы получаем 9600

6. VladimirB 17 25.03.21 08:23 Сейчас в теме

Примерно так Рекурсией (код не проверял. Просто навожу на мысль)

Функция ПолучитьСуммуРекурсивно(_Массив,_Индекс,_Сумма)
   _См=_Массив[_Индекс].Значение;
  Если _См=_Сумма Тогда
    Возврат _См;
  КонецЕсли;
   Для иии=_Индекс+1 по _Массив.РазмерМассива Цикл
      _тСм=_Массив[_Индекс+1].Значение;
      Если _тСм<=_Сумма - _См Тогда
          _См=_См+ПолучитьСуммуРекурсивно(_Массив,иии,_Сумма)
      КонецЕсли;
   КонецЦикла;
возврат _См
КонецФункции

Показать

8. BaldKiwi 25.03.21 11:34 Сейчас в теме

(6)Спасибо за предложенный вариант

9. SlavaKron 25.03.21 17:30 Сейчас в теме

Похоже на задачу одномерной упаковки. Каково в среднем количество документов в массиве?

Оставьте свое сообщение

E-mail: