Некая вариация задачи о рюкзаке.
Необходимо набрать товара из таблицы на сумму не меньшую заданной с минимальной разницей.
Реквизиты Наименование, Количество, Цена.

Т.е. Цен2*кол + цен5*кол + цен8*кол >= искомая сумма
где кол - необходимое количество, не большее количеству по строке в таб.

Буду благодарен знатокам за помощь с алгоритмом.

ЗЫ: тему Нужен алгоритм набора нужной суммы видел, но к конкретному более-менее оптимальному решению с количеством еще не пришел...

какое
макс  кол-во  номеклатур
макс кол-во

макс время расчета ?

Номенклатур десятки - сотни.
Количеств по строке десятки, сотни иногда тысячи.

Макс время - в пределах двух. сек - будет отлично.
Если больше, то чем меньше, тем лучше, конешн.

Если по итерациям ограничение превысит - соберу жадным. Но сначала хотелось бы чем-нибудь вменяемым поискать.

Комбинаторику знаем? Составь заранее базу всевозможных сочетаний с готовыми суммами и используй поиск по ней по полю "сумма".

(4)+ Если база будет слишком большая то почти одинаковые значения суммы (и их составляющие) можно почистить/выкинуть.
Причем как самые большие наборы так и наоборот самые мелкие оставить, на ваш вкус.

(4) комбинаторику знали, но, к чертям, забыли.
Как и практически всю вышку (слишком много времени прошло с тех пор как была необходимость ее использовать).

Ну и не хотелось бы все варианты перебирать.

(6) Варианты перебираешь заранее а потом только хранишь/используешь.
Надеюсь номенклатура и цены меняются не часто?

(7) Это шутка?
До какого значения кол хранить?
Даже если товаров всего 100, и кол равно либо нулю, либо единице, количество комбинаций 2^100, примерно равно 10^30

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

(8) "Искомая сумма" сильно ограничивает количество комбинаций.

К тому же можно банальным множителем (для кол-ва) легко подогнать меньшую комбинацию под большую сумму.

ЗЫ Прекрасно понимаю что можно применять алгоритм набора суммы из нужного числа купюр/монет. Но перебор комбинаций прикольнее ))

(10) так "Искомая сумма" сильно ограничивает или "всевозможных сочетаний"

Вопрос именно в алгоритме, учитывающем подобные ограничения.

Банальный множитель должен быть не отрицательным, не большим количества по строке.

Да это она и есть, только ограничение справа, а не слева, купюр произвольное множество и для каждой купюры стоит свое ограничение по количеству.

Тем не менее, да, самая близкая. Теперь бы понять как это адаптировать...

Можно для перебора вариантов заюзать GPU (на CUDA или OpenCL).

(11) Можешь задачку подробнее описать и с примерами?
В т.ч. какие граничные условия, вот банально количество это натуральное число?

А еще лучше цель этого "набора из корзины" какая?

(14) цель подобрать реальный товар на необходимую сумму, как можно ближе к заданной.

Да, количества, как правило, натуральные.

Салфетки 200р 5 шт.
Костыли 8900р 10 шт.
Корсеты 5100р 11 шт.
Гематогены 60 5 шт.
Подгузники 4700р 2 шт.

Нужно набрать товара на сумму большую 9450, максимально близкую к данной.

Т.е. 2 подгузника и один гематоген.

(9) Вечная тема: за что заплатил клиент (по номенклатурно)?

(14) цифры из головы.
Цены могут быть не только натуральные.

(16) конечно.
Только теперь законодательно нужно выводить сие в чек.
И, не смотря на то что в типовой сие отсутствует, руководство хочет требование выполнять "от и до".

(18) Ну напечатаете Вы что-то, а при следующем платеже что будете делать: нужно же учесть, что уже напечатано и на какую сумму. Мне кажется, как минимум нужен регистр накопления. Тем более сумма платежа может не совпасть с подобранной.
Может административно заставить оплачивать 1 реализацию ПОЛНОСТЬЮ?

(16) (18) Эээ вы что хотите аванс одной суммой раскидать только на часть позиций в документе?

Нафига???

(19) в случае если сумма гасится по реализации полностью, естественно все товары берутся.
Административно заставить - не реально.
Плюс авансы никуда не деются...

(20) нет. Аванс есть аванс.
Но вот часть оплаты, которая реально ставит отгрузку в кредит - да на часть позиций. :)

(21) Не страдайте идиотизмом, в случае опта у вас идет не оплата конкретных товаров.

А оплата товара по конкретному договору или документу поставки... Так и следует писать.

(22) Один фиг, 1-й аванс, 2-й аванс или 100-й аванс...

В любом случае: эт все неважно.

Имеется вот такая странная задача и есть алгоритмическая проблема в ее реализации.

Товар: Оплата по договору XXX
Количество: 1
Цена: 10000 р
Сумма: 10000 р.


Все!

(25)
1. это реально противоречит новому закону.
2. не важно на сколько данная задача дурацкая, она есть и её необходимо решить в том виде, в котором она поставлена...

(24) Если задача из ТЧ документа (в 100 позиций макс), где разная номенклатура с разной ценой и разным кол-вом.

Требуется выбрать часть позиций (товар, кол-во, цена) на заданную сумму - то это классический https://ru.wikipedia.org/wiki/Задачаоранце

Конкретно если нужно самое точное решение то https://ru.wikipedia.org/wiki/Методветвейи_границ

Если наиболее быстрое решение то можно попробовать "генетический алгоритм".

(27)+ Пока ничего лучше чем "параллельные генетические алгоритмы" еще не придумали, почитать можно http://www.intuit.ru/studies/courses/14227/1284/lecture/24174?page=1
https://interactive-plus.ru/ru/article/11099/discussion_platform

(27)я первом посте написал "Некая вариация задачи о рюкзаке"
И линки на обсуждение дал.

Проблема в ограничении суммы "справа", а не "слева" и в прикручивании туда количества.

(29) Какая разница с какой стороны сумму ограничивать?

А еще вместо добавления в рюкзак можно же из него выкладывать, пока не останется то что надо.

(30) вот эту разницу я пока и не могу осмыслить.
Можно, если не сложно, пример на базе (15)?

(29) Если думаешь что существует простой (для понимания) готовый алгоритм который легко взял и приспособил... то глубоко ошибаешься!

Даже банальный полный перебор не так то просто написать без ошибок. Это блин не проведение документа по регистрам и даже не вычисление себестоимости.

Если не подумать насчет скорости алгоритма, да банальное представление-хранение в памяти данных над которыми работаем, то ничего не получится на требуемых тебе объемах.

Для начала выкинь коды/ссылки номенклатуры и замени её целыми числами по порядку. Далее все в массив и уже дальше думаем.

(31) Если не срочно то могу сделать и выложить почти готовое решение на ИС.
Счас слегка занят, прикручиваю кассу к древней измененной конфе

(33) ну, до 30 буду этим заниматься...
Буду благодарен, за пример.

Касса какая?
У меня тоже конфа древняя. М.б. смогу чем-то поделиться.

(34) атол 22ПТК модернизированная и альфа-авто 4.1.01.28 сильно перепиленная

(35) понятно.
Не, с Альфа-авто дел никогда не имел.

(36) Я тоже не имел, но глубоко пофиг какая конфа если их уже более сотни разных видел/имел дело.

Тут проблема что они заразы не только 54-ФЗ в новой версии 4.1.01.29 добавили но и еще кучу мелких багов поисправляли, а много из них у этих товарищей тоже исправлены но совсем другими способами.
А уж своего понапилено просто пипец ну и как вишенка на торте это система защиты от Рарус :)

(37) вообще на ИС есть "Комплект для печати Чеков ККМ для Атол и Штрих без подключения в 1С драйверов торгового оборудования"

К любой не типовой можно без серьезных заморочек прикрутить.

(38) круто

(12), (13), (14) - а можно не изобретать велосипед, а просто посмотреть нормальные методы решения рюкзака.

Это либо какой-то прикол, либо новое движение "дай чуваку ощутить себя полным идиотом".

Все знают что это "стандартная" задача рюкзака, все знают что есть масса методов решения. Начиная от ДП и "Ветвей и границ" и заканчивая построением сеток по Лагарису-Одлузко, поисков кратчайших по Лейнстра-Лейнстра-Ловаса и нахождению оптимальных по Каннага Финке Поста. Но все почему-то хранят тайну каким образом привести описанную задачу к любому из указанных методов. Как лучше разобрать количество, как найти оптимальные решения при ограничении "справа" - все для всех очевидно.
Да я тоже знаю о существовании этих методов, но как конкретно применить хоть один из них к задаче и не ждать мегалета?
Для меня это не очевидно. Потому и прошу знающих людей прояснить ситуацию.

(41) Генетический бери, ГСЧ за тебя всё сделает

(42) я понял. Таки движение.

Оплата по накладной, содержащей товары, или по договору, или как-то еще? Идентифицировать документ отгрузки возможно? Или вы весь справочник берете, или все обороты по товарам?

(44) беру кредитные реализации из движений покупателей.
Товар подбираю из них.
Но тут проблемы нет. Проблема в адаптации алгоритма.

Не лучший пример адаптации (самый очевидный):

РюкзакПо(СуммаВсехЭлементов - ИскомаяСумма);
По полученному массиву:
Для К = 1 По КолСтрВМассиве Цикл
Таб.Кол = Таб.Кол - Таб.ВыбКол
КонецЦикла;

Количество перебираем как здесь: Нужен алгоритм набора нужной суммы

(43) А ты чего хочешь? Код за тебя написать? В генетическом алгоритме всё предельно понятно, генерируешь случайные наборы в определённом количество например 2000 наборов, и выбираешь из них лучший. Что непонятного то?

(45) Если есть возможность идентифицировать накладную оплаты, то можно вычислить: долю оплаты документа. Например, если это первая частичная оплата, тогда берем с первой позиции в документе на нужную сумму, корректирую пропорционально количество, пусть даже будет дробное количество - это не запрещено законом. Если это последующая частичная оплата, тогда сначала исключаем с первой позиции все товары на сумму предыдущих оплат, а затем из остатка товаров точно также собираем для текущей оплаты.
По мне так логичнее. Иначе рискуете один и тот же товар в чек выводить, в тоже время другой вообще никогда не вывести.

+(48) Ну и погрешности расчета суммы учитывайте

(48) Один и тот же товар - ничего страшного.
Отследить что клиент дважды за один и тот же товар заплатил даже сам клиент не всегда сможет - если такая необходимость у него вообще возникнет (что в нашем случае - вряд ли). Гарантированно подбирать различный товар можно только с заведением отдельного регистра. Да и то на момент до и после восстановления последовательности он будет разным.

А вот 3,2 костыля в чеке могут вызвать вопросы.

(50) В разобранном состоянии =))

Вот тут http://catalog.mista.ru/public/460935/ в задаче 23 описана готовая функция.

В процессе ее обсуждения с Олегом Родионовым (ovrfox) родился более эффективный вариант (там из комментариев можно прямо готовые обработки скачать). Хотя там для 8-ки, ничего особенно восьмерочного в коде нет, можно переписать на 77, либо просто идею алгоритма взять.

Хотя там заявляется метод ветвей и границ, на самом деле это просто "рациональный" перебор. Превратить куски материала в номенклатуру несложно - это буквально одно и тоже. Как расширить условие на больше прямо сейчас не скажу - нужно еще подумать.

(40) С удовольствием бы посмотрел нормальные методы решения рюкзака аналогично быстрой сортировке https://software.intel.com/ru-ru/articles/gpu-quicksort-in-opencl-20-using-nested-parallelism-and-work-group-scan-functions

(52) Если Вы имеете в виду 23. Оптимизация подбора кусков заданного суммарного метража методом ветвей и границ, то ветвями и границами там и не пахнет: не развиваются явно неперспективные ветки, когда добавление нового куска бессмысленно.
В ветвях и границах подразумевается использовать "релаксированную" задачу (обычно снятие условие целочисленности) для получения оценки значения функционала и отсечения ветви, если оценка хуже рекорда.
Можете напустить эту процедуру на задачу, в которой число кусков = 2N+1, длина каждого = 2, а требуемая сумма = 2N+1 и посмотреть, как долго она будет работать.

(53)+ Хмм оказывается кое что есть https://homepages.laas.fr/elbaz/4676b763.pdf

Гуглится "knapsack problem gpu"

(52) Спасибо!

Кстати, проверил на реальных данных вариант из (46) и, т.к. реализация, как правило, редко гасится, вполне себе рабочий (те самые ветки и границы, по-моему). Сейчас добавлю жадину и буду сравнивать на предмет меньшей дельты (в предыдущем стоит итерационное ограничение).

Далее можно более быстрые рюкзаки засунуть по схеме (46)

* редко гасится на малую сумму - как правило почти полностью.

(55) Если они не сильно наврали в табличке тестов то офигенное ускорение на видеокарте получается.

Использовали Tesla C2050 / C2070 GPU с 448 ядрами CUDA.
http://www.nvidia.ru/object/product_tesla_C2050_C2070_ru.html

(54) Ну, методом ветвей и границ там все-таки "пахнет", но это действительно не настоящий метод ветвей и границ, вы правы, в названии я ошибся.

(54) Взял 501 кусок по 2 метра, задал 1001 метр, получил "пустой" ответ через 801 миллисекунду: http://pixs.ru/showimage/SkrinSHotR_7664998_26690560.png

(60) Согдасно (54) требуемая сумма = 2*250+1, т.е. 501, а не 1001.

(61) Ответ через 440 мсек. )) http://pixs.ru/showimage/SkrinSHot1_4706534_26691995.png

Это я к тому, что то, что метод не является МВГ (который тоже перебор и в случае неудачной функции отсечения будет близок к полному, то есть не только временем будет отличаться, но и памятью (недостаток МВГ)) не означает, что он практически плохой. Как раз практически он хороший.

Идея там в том, что сначала жадным алгоритмом подойти как можно ближе, а затем искать малыми изменениями полученного решения - убирая - добавляя по одной номенклатуре. Работает очень быстро.

Ценную мысль, что оценку для МВГ можно получить, решив ЗЛП, я взял на заметку.

я бы взял старый добрый симлекс .
но он может плохо работать на целочисленных коэффициентах.
те нужна адаптация (банально - округление)


выложите тестовые данные на 1000 примеров
тогда можно будет выбрать самый быстрый.

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

Полный перебор с отсечением как только превышаем требуемую сумму, начиная с наиболее тяжелых предметов (Дорогих товаров)
Можно еще добавить отсечения.

+ (64) Если тексумма + весминимальногопредмета >= Целевая сумма, тогда добавляем минимальный предмет из оставшихся, и прерываем ветвь.

+ (65) Если ТекСумма + максимальныйпредметизоставшихся >= ЛучшийДостигнутыйРезультат результат,
То перебирать начинаем не с большего предмета, а с наиболее тяжелого предмета с весом меньшим чем ЛучшийДостигнутыйРезультат - ТекСумма,
например методом половинного деления.



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

(62) Общий метод решения ЗЛП (например, симплекс) для рюкзака не стоит использовать, т.к. в случае рюкзака релаксированная задача ЛП (одно ограничение, не считая 0<=Xi<=1) допускает аналитическое (тривиальное) решение.
НО! Для случая подбора кусков (целевая функция совпадает с ограничением) релаксированная задача в качестве решения будет ВСЕГДА давать значение ограничения, т.е. ничего отсечь не позволит.
(64) "Симплекс, метод ветвей и границ, методы динамического программирования  и т.д." - это совершенно разные методы.
Если симплекс предназначен исключительно для ЗЛП, то ветви без границ и дин. прог. собственно не методы (алгоритмы), а схемы, которые могут применяться для задач различных классов.

(67)  я писал что это одинаковые методы?

(68) Извините, видимо я Вас в (62) неверно понял.

(69) в (62) ведь не я :)
Хотя обсуждается вроде мой старый код, который на практике очень быстро сходится.

есть метод 1Сный ))) (исходя из пожеланий бухгалтеров и финансистов)
использовать метод пузырька соосный , сиречь - при запросе создаются группы (при прямом быстрее но не суть) которые согласно алгоритма, УЖЕ - сами используют метод пузырька - пример граф (Маньяка чот не видно давно)

(67) ...т.е. ничего отсечь не позволит...
это понятно, но у меня мелькнула мысль, что оценкой будет значение, вычисленное на основе округленных значений переменных из решения ЗЛП. Дальше пока не думал, поэтому настаивать не буду...

В (63) возможно, имеется ввиду метод Гомори.

вложенность проверяется , на сравнение выхода по наименьшему результату из подмножества

я в названиях не силен (кому они нафинг нужны) , но система работает за тот последний который первый в матрицу не сложился , типа тз, так понятнее ?

тада уж Гаусса

кстати в 8-ке , в 7-ке тоже такого нет, только математически, и то 1-у копейку от акциза - все равно потеряешь, проценты это не часть от числа, это производная

(71) Это как бы и есть построение дерева - смысл метода ветвей и границ.
А затем перемещение по веткам этого дерева с отсечением тех которые явно лишние ибо перебор.

(77)+ Иерархические группы/элементы = дерево

(78) с отсеканием , не просто дерево, а по вхождению

(77) дерево , читает всё дерево , а тут зарубки , зарубки виртуальная таблица , и до внутрь, дерево наооборот