Набор суммы минимальным числом слагаемых , динамическое программирование

Akina
Спасибо... можно на примере не совсем понял что значит не с нуля?
допустим у меня массив номиналов {10,5,2,1} и сумма 47...
1) массив отсортировать? если да то по убыванию или возрастанию?
2) насколько я понимаю мне нужен не жадный алгоритм?

Сообщение отредактировано: test4me - 01.07.21, 14:39

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

1. не факт, что подобный размен вообще возможен. Сумма = 17, номиналы {4, 10} - решения нет. Не знаю, надо ли перед основными вычислениями убедиться, что решение в принципе есть (то есть найти первое, пусть неоптимальное разложение) или нужно вычислять, и, если, никакое решение не найдено, значит, разложение невозможно...Тут какая-то делимость может быть замешана. Проблема в том, что проверять придется вообще всевозможные делимости, в том числе всевозможные суммы номиналов.

2. какие номиналы брать, когда их кол-во одинаково, но их состав различен. Пример: S = 25, номиналы {11, 12, 13, 14} --> S1 = 11 + 14, S2 = 12 + 13, S1 = S2...

3. мат.модель. Обозначим номиналы так: {a, b, c, ...}. N(x) - количество монет номинала x
a * N(a) + b * N(b) + c * N© + ... S - попахивает чем-то диофантовым вроде, т к все решать надо в целых числах
надо добавить ограничения на количество монет каждого номинала
N(a) = [0 ... S/a]
N(b) = [0 ... S/b]
...

4. надо ли сортировать? а вот хз) по идее можно, по возрастанию. Сведется что-то к задаче о рюкзаке, только тебе нужен размен под ноль и никаких дельт образовываться не должно.

Я не знаю, как это решить, но такое чувство, что здесь какой-то рекурсивный перебор будет. Akina, как я понял, предложил тебе вариант подбором/перебором, возможно, это самый оптимальный подход здесь.
Пример: {1, 2, 3, 5, 10, 17, 25}, S = 200
N(1) = 200, N(2) = 100, N(3) = 66, N(5) = 40, N(10) = 20, N(17) = 11, N(25) = 8
Сколько всего здесь переборов? Вроде получается 200 * 100 * 66 * 40 * 20 * 11 * 8 (это еще нулевые значения не взяты в расчет) = 92 928 000 000 (почти 100 миллиардов вариантов перебора) ). А если S = 2 500 или 27 539? - очевидно, что в какой-то момент полным перебором за разумное время результат будет невозможно получить.

-----------------------------------------
если количество монет каждого номинала строго из множества {0; 1}, тогда все значительно упрощается, но все равно, какие-то тонкости здесь есть...

FasterHarder
Спасибо за развернутый ответ!
задача такая есть товары в количестве А но незнаем какие это товары, которые проданы за день скажем на какую то условную сумму денег.
Есть известная сумма Х по которой надо списать то количество товара которое надо найти в зависимости какой товар по цене подойдет или хотя бы приблизится к этой сумме.

Скажем есть условно 20 товаров:
А1 10 шт по цене 2
А2 6 шт по цене 3
А3 18 шт по цене 5
А4 3 шт по цене 7
А5 35 шт по цене 9
....
А20 14 шт по цене 15

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

Сообщение отредактировано: test4me - 01.07.21, 19:21

Цитата test4me @ 01.07.21, 14:12

допустим у меня массив номиналов {10,5,2,1} и сумма 47

Сразу откладываем по 1 монете. Это сумма 18. Остаётся 47-18=29. Пытаемся набрать её произвольным образом. Получается (например, 2*10+1*5+2*2+0*1). Прибавляем те самые отложенные монеты, и получаем решение (одно из возможных): 3*10+2*5+3*2+1*1=47.

Akina
Спасибо попробую сделать!

Цитата test4me @ 01.07.21, 19:16

FasterHarder
Спасибо за развернутый ответ!
задача такая есть товары в количестве А но незнаем какие это товары, которые проданы за день скажем на какую то условную сумму денег.
Есть известная сумма Х по которой надо списать то количество товара которое надо найти в зависимости какой товар по цене подойдет или хотя бы приблизится к этой сумме.

Скажем есть условно 20 товаров:
А1 10 шт по цене 2
А2 6 шт по цене 3
А3 18 шт по цене 5
А4 3 шт по цене 7
А5 35 шт по цене 9
....
А20 14 шт по цене 15

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

У вас тут два критерия.
Во-первых, включить все разновидности товаров в набор суммы. Во-вторых, максимально приблизиться к требуемой сумме.
Может оказаться так, что сумма точно набирается, но без одного товара. А с этим товаром она точно не набирается. Или сумма точно набирается только одним видом товара.
Так что вы определитесь, что вам важнее: минимизация отклонения или включение всех видов товаров.
Если второе, то сразу берите по одной штуке каждого товара. Затем просто решается задача о наборе суммы.

Решение этой задачи зависит от величины набираемой суммы. Если она большая, то ДП вам не поможет.
Для сверхбольшой размерности у меня есть очень хороший алгоритм (дипломница писала для нашей бухгалтерии, для планирования госзакупок), но программного кода нет, т.к. писала не я. Сразу должна сказать, что алгоритм довольно сложный. В смысле не так просто программируется, как это всё.
Если ДП вам не подойдёт, могу дать описание. Есть и статья, "Информационные технологии", 2019 год, №4 ("Гибридный" алгоритм планирования государственных закупок товарно-материальных ценностей). Там есть пример работы на модельном примере, но подробное описание попросили убрать.

swf
Спасибо за ответ! Да вы правы тут 2 варианта .... в моем случае важно списать больше разного товара максимально приближаясь к этой сумме,при необходимости в дальнейшем можно будет сделать корректировку добавлением проводок списания в ручном режиме для достижения точного соответствия сумме. Насчет суммы нужно списать за 3 года... но в любом случае списывать нужно каждый день, учитывая закупку, возврат товара. Придумал еще разделить товары на группы типа каждодневные товары (хлеб, сыр, масло, колбаса, молоко, алкоголь....и.т.д.), и товары которые продаются в разный сезон в процентном соотнешении с каждодневными вместе в зависимости от времени суток, сезона и времени года... ну как бы модель того что могло бы продаваться в разное время года.

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

Спасибо, всем кто написал и помог ценным советом!

Сообщение отредактировано: test4me - 03.07.21, 08:04

Хорошо, я прикреплю текстовый файл с полным описанием алгоритма (надеюсь, найду на компьютере, вечером после футбола поищу муж через комп футбол смотрит). И тестовый пример работы алгоритма на небольшом наборе данных покажу, чтоб на пальцах объяснить идею. У нас для каждого подразделения набирались большие суммы (несколько миллионов рублей) и количество слагаемых было очень большим (например, один только список канцтоваров для кафедры, каждый канцтовар - отдельный лот), а сумма набиралась очень точно, с отклонением в несколько рублей. То есть этим алгоритмом вы можете сразу набрать всю сумму за три года. А потом эту сумму другим алгоритмом можно задним числом раскидать по дням. Это если задним числом делать.

А если вы каждый день должны списывать небольшую сумму, то можно ДП обойтись. Если стоимости округлить до рубля, то какая будет сумма, столько будет столбцов в табличке. Правда, я ДП реальные задачи не решала, не знаю, какой там максимум количества столбцов. Может, кто-нибудь подскажет.

swf
Спасибо большое как раз то что нужно... да и проводки задним числом нужно провести за 3 года....суммы тоже не маленькие за день..(да придется тем более их умножать на 100 делать целыми) буду ждать ваше сообщение!

Вот ссылка на полный алгоритм
https://disk.yandex.ru/i/bDJwOJj6IHxUoQ

Объяснения после футбола

swf
Спасибо получил...разбираюсь.... тоже после футбола зайду))))

Начнём с конца. Гибридный алгоритм состоит из двух алгоритмов: точного и эвристического. Вначале эвристический набирает сумму, меньшую заданной. Когда остаётся не больше 20 слагаемых, то сумму добирает точный переборный алгоритм с возвратом, для 20 слагаемых он работает мгновенно, за счёт перебора набирает очень точно. Этот точный алгоритм описан и есть мои исходники к нему в этой теме:
http://forum.sources.ru/index.php?showtopi...EC%EC%FB&st=15#
Мой ник там Swetlana, посмотрите мои сообщения.

Что касается вашей реальной задачи. Цены на продукты питания всё время растут. За три прошедших года сразу нельзя сумму набрать, потому что цена на каждый вид продукции (лот) с течением времени менялась. Тут нужно подумать. И нужно знать, как она (цена) менялась. 3 года, пусть это будет n=3*365 дней. Для каждого лота нужно завести строку (массив) длины n и проставить цену. И так по каждому лоту. У вас есть такие данные?

Сообщение отредактировано: swf - 03.07.21, 20:35

swf
Прочел несколько раз пытаюсь осмыслить все в алгоритме... очень интересно... спасибо Светлана по ссылке нашел тему... насчет продуктов да особенно за 2 года выросло очень в разы.... но у меня есть данные закупок уже все с реальными ценами за 3 года и возвраты все которые были, также есть терминальные выплаты + чековые данные только не отдельно чеки а за весь день одной суммой. Вот есть закупки товара + возвраты + сумма с терминалов + чековые суммы за каждый день и это та сумма на которую надо списать... Пока все вроде бы понятно спасибо очень наглядно и подробно все подсказываете... займусь пока все прочитаю по ссылке!

Добавлено 03.07.21, 21:28
swf
Значит как я понял из выше сказанного нужно для начала:
списать сразу за 3 года не получится изза того что операция списания будет зависит от даты закупки и возврата каждого товара и на тотже день надо посчитать чеки + терминал (((
1) на каждый день пересчитать последовательно за все 3 года каждый продукт (ЗАКУПКА-ВОЗВРАТ) получим реальное оставшееся количество и сумму на каждый день на все 3 года...
2) на каждый день пересчитать последоватльно также СУММА ТЕРМИНАЛА + СУММА ЧЕКА
и потом надо уже испоьзовать алгоритм получить на сумму (СУММА ТЕРМИНАЛА + СУММА ЧЕКА) слагаемые сумм как можно большего числа на тот день товаров.... как наберется это сумма узнаем количество уже тех товаров которые спишем и так повторим за оставшиеся дни в течении 3 лет... кажется так... если нет поправьте...

Сообщение отредактировано: test4me - 03.07.21, 21:28

Алгоритм какой-нибудь придумаем)) Надо вначале с реальной задачей разобраться. Я пока не поняла, какие данные у вас есть.
Чековая сумма за день - это суммарная стоимость проданного за день?
Возвраты - это понятно, кто-то вначале купил (возможно, в другой день), а сегодня вернул.
То есть из проданного за 3 года нужно вычесть возвраты за 3 года. Пока вроде понятно.
А что такое сумма терминала?
Данные закупок с реальными ценами - это какие данные? Пример какой-то приведите, чтобы я поняла.

swf
доброго времени суток!
Да все правильно Чековая сумма - сумма за день... так назваемый (Z)... сами чеки за продажу каждого товара и его количества и суммой были утеряны поэтому есть только чековая сумма за каждый день после закрытия дня.
Возвраты в нашем случае - возвраты закупок которые были по какой-либо причине возвращены нами не покупателями!
Терминальная сумма это выписка из банка то что было заплачено по терминалу кредитками безналичным расчетом.
Данными с реальными ценами я называю как раз закупки которые были сделаны и их данные как раз есть все с количеством и ценой что когда закупали какой товар в течении этих 3 лет - поэтому называю реальными))))
По факту скажем на начало 2018 года есть товары: известны остаток, себестоимость и цена.
Берем первый день - есть приход по некоторым товарам тоесть закупка товара а также возможен и возврат по какой либо причине который был еще закуплен нами в 2017 году в конце года. Ну и 3-й компонент это наша реализация,
которую нам надо уже по алгоритму самим решать какой товар реализовать в каком количестве с какой себестоимостью и ценой.
То есть 1-е действие ОСТАТОК КОЛИЧЕСТВО + НОВОЕ КОЛИЧЕСТВО и ОСТАТОК СУММА + НОВАЯ СУММА (Новая закупка, это только в тех товарах у которых на данное число была закупка) МИНУС отсюда если был возврат по этому товару
(ВОЗВРАТ КОЛИЧЕСТВО) и (ВОЗВРАТ СУММА) = (ФАКТ КОЛИЧЕСТВО) и (ФАКТ СУММА) вот это как раз одно слагаемое из таких же товаров, а слагаемых этих должно быть столько сколько товара на этот день где количество товара>0. Что касается суммы к которой нужно подобрать слагаемые это опять же (ЧЕКОВАЯ СУММА - НДС (18%)) + (ТЕРМИНАЛЬНАЯ СУММА - НДС (18%)) на этот же день по этому товару. И так в цикле наверно 3*365 * N(товара)!

Сообщение отредактировано: test4me - 04.07.21, 19:18