Роспись суммы несколькими строками (с учетом округлений).

[Steini]

Добрый день, любители пошевелить извилинами!
Я к вам с интересной задачкой, которая возникла на работе, которую я, в принципе, решил, но всего лишь для большинства случаев, и все еще не получил научного оргазма, удовлетворения от элегантного ее решения) Задачка по алгоритмизации и связана с округлениями:

есть сумма С в рублях с точностью до коп., на которую надо поставить продукцию. Есть количество К кг продукции, которое надо поставить. Есть вес В одной штуки продукции.

Надо рассчитать цены за штуку и за килограмм с точностями до коп. Приэтом ЦенаЗаШт $=$ ЦенаЗаКг / Вес. Можно раскидать несколькими строками с разными ценами, лишь бы все сошлось с точностью до копейки.

Например, сумма $=$ 206968,48 (руб.), колво $=$ 13003 (кг), вес одной штуки $=$ 0,65 (кг). Тогда цена за кг вроде бы $= 206968,48 / 13003 = 15,91698 \approx 15,92 $, но $ 15,92 \cdot 13003 = 207007,76$, что в свою очередь категорически $ \ne 206968,48 $! Решается эта проблема росписью двумя строками:
1) 5397,6 (кг) по цене 15,80 (что эквивалентно 8304 штуки по цене 10,27) $ = 85282,08 $
2) 7605,4 (кг) по цене 16,00 (что эквивалентно 11700,615 штук по цене 10,40) $ = 121686,40 $
В итоге $ 206968,48 = 206968,48 $. Круто!

Мой алгоритм росписи двумя строками:
1) сначала создадим табличку ЦенаЗаШт - ЦенаЗаКг, в которую вобьем значения цен, которые при конвертации из штук в кг и обратно дают цены с точностью до 2 знака (до коп.). Отсортируем эту табличку так, чтоб первая цена была наиболее близко к "справедливой".
2)

Цикл по ценам из таблички
    Цикл от i = 1 По К
          Колво1 = i;
          Колво2 = К - i;
          //Далее расчеты цен, проверки, что окргуленные до коп. суммы совпадают

Пользователю нужно вывести все найденные варианты. Я здесь отбросил нюансы и те оптимизации, которые я сделал, чтобы не засорять итак большую "простыню".
Код работает, все хорошо, но не всегда. Тогда приходиться расписывать тремя строчками, и без оптимизации это может занять день на вполне хороших компах (перебор примерно $10^{14}$ вариантов).
Я оптимизировал и это, в основном за счет того, что сузил интервалы поиска решений. Но алгоритм не справился с задачкой, когда отгрузка на 1,5 миллиона - 70 тонн.

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

Может кто-нибудь что-нибудь подскажет? Задачка сложная, но жутко интересная для меня на моей работе)

[Teletranslator]

То есть: задача состоит в том, чтобы подогнать цену за КГ продукции под сумму и количество так, чтобы всё сходилось до копеек?

Тогда нужно уточнить: какие значения может принимать вес этих долей? Это принципальный вопрос.

[Steini]

Не только цену за кг, но и за штуку, и чтобы тождественно выполнялась связь ЦенаЗаШт $=$ ЦенаЗаКг $\cdot$ ВесОднойШтуки, если быть точнее, ЦенаЗаШт $=$ Окр( Окр(ЦенаЗаКг, 2) $\cdot$ ВесОднойШтуки , 2), где Окр(х, 2) означает округление по арфиметическим правилам до двух знаков после запятой. И чтобы ЦенаЗаШт $\cdot$ КолвоШт $\equiv$ ЦенаЗаКг $\cdot$ КолвоКг $\equiv$ Сумма (с точностью до копеек)

В каких пропорциях расписать строки? Здесь вопрос эстетики. Вроде можно произвольной ценой, но, если справедливая цена, скажем, 15,51698 руб., то нас устроит расписать одно количество рублей так по 13-14, другое - рублей так по 15-17 вполне. Или же (крайний, но приемлемый случай) почти всю партию по рублей 15-16, а две штучки по 14 копеек. Но никак не устроит списывать ценам в два раза превышающих "справедливую" цену 15,51698.

[_Ivana]

Школьная арифметика, говорят, страшная сила. Экономит сутки работы компов. Следите за руками: если одна штука весит $0.65$ кг, то при условии целых копеек в ценах килограмма и штуки, цена килограмма должна быть кратна 20 копейкам, а цена штуки - 13 копейкам. Понятно почему? Расписываю подробно: $sc = 0.65sv, 100sc = 65sv, 20sc = 13sv$. Далее ваша арифметика - средняя цена килограмма $15.91$ - округляя до 20 копеек вверх и вниз получаем, что часть отгрузим по $15.80$, а часть по $16.00$. Аналогично штук у вас $13003/0.65 = 20004.615.....$, средняя цена штуки $10.346....$, округляем до 13 копеек вверх и вниз, получаем что часть продукции отгрузим по $10.27$ а часть по $10.40$. Далее выписываем уравнения для пятого класса: $15.80v_1 + 16.00(V-v_1) = S$, где $V$ - общий вес, $S$ - сумма отгрузки, $v_1$ - часть веса, отгружаемая по $15.80$, откуда однозначно находим $v_1 = 5397.6$, соответственно $v_2 = V-v_1 = 7605.4$ - выходим на ваши волшебные цифры. А если учесть, что $15.80v_1 = 10.27q_1$, то получаем $q_1 = 8304, q_2 = Q-q_1 = 11700.615......$ - и не мучаем сутками компы!...

[Steini]

_Ivana
Во-первых, большое спасибо! Очень полезное сообщение.
А во-вторых , к сожалению, есть нюанс. Этот примерчик простенький, у меня он считается порядка 10 секунд (при росписи двумя строками), перебирая абсолютно все варианты, в конце концов (после всех фильтров "эстетичности") выводя на экран пользователю 14 более-менее приемлемых вариантов.
Сутками же (!) считается тот случай, когда двумя строками расписать невозможно. Тогда включается тот же алгоритм, но для трех строк. И тогда уже время непозволительно огромное, а если я оптимизирую - то не находятся варианты. Тут же стоит отметить, что продукция бывает не только 0,65 кг, но и вполне 0,032 кг.
Вот вариант, который посадил меня в лужу: Сумма $= 1595243,05$ руб., Колво $= 66579,5$ кг, вес одной штуки так же 0,65 кг. Его двумя строками не расписать, тремя - либо долго (тогда весь смысл автоматизации пропадает), либо вообще не находит решений.
Буду весьма признателен, если кто-нибудь меня просто жестоко опустит, рассказав, как это просто все считается

П.С.: Почему предложенный выше алгоритм не подходит для этого примера? Потому что в обеих строках получится нецелое количество штук. Такое, как понимаете, недопустимо. В последней строке может быть 13,667 штуки, тогда на бумаге все будет с точностью до копеек,а в жизни вместо 0,667 штуки поедет целая. Но такого, чтобы у одной целой штуки были две разные цены (0,333 по 23,80 руб. и 0,667 по 24 руб.) - такое недопустимо.

[Alexu007]

(23755 x 15.58) + (78585 x 15.59) = 1595243.05

[_Ivana]

Alexu007, вы мало того, что 90 штук продукции себе в карман положили, так еще и не соблюли условия
Steini, в вашем варианте я бы предложил бухгалтерии ограничиться двумя строчками и выписать:

$61465\cdot15.47 = 39952.25\cdot23.80 = 950863.55$ и

$40965\cdot15.73 = 26627.25\cdot24.20 = 644379.45$

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

[Alexu007]

(61635 x 15.57) + (40795 x 15.58) = 1595243.05

Вот так. Что касается второго условия... оно какое-то странное. Если товар расфасован поштучно по 0.65 кг, какой смысл подсчитывать, сколько стоит 1 кг?

[_Ivana]

Вот получше вариант:

$40975\cdot15.22=623639.50\leftrightarrow26633.75\cdot23.42=623762.425$

$61455\cdot15.81=971603.55\leftrightarrow39945.75\cdot24.32=971480.64$

Сумма по количеству совпадает полностью с заданной суммой, по весу отличается на полторы копейки. Цены за штуку и килограмм полностью соответствую друг другу при пересчете по коэффициенту и последующему округлению до целых копеек.

[Alexu007]

Чё то я не понял, что здесь не так?

[_Ivana]

Alexu007 то, что у вас сумма за килограммы не равна их количеству умноженному на их цену. Вдобавок, еще по какой-то причине итоговая сумма по количеству у вас нецелая при целых суммах обеих строк :)
Хотя автор темы приложил все усилия, чтобы никто не понял - что ему в конечном итоге все-таки надо. Это одна из причин, по которой так немного желающих разбираться в его теме.
Steini, у меня для вас есть 2 имховых заблуждения, одно плохое, другое возможно получше :)

[Alexu007]

Ну да, я понял уже. У меня округляется окончательный результат, а нужно округлять промежуточные результаты. Я переделал, с моими цифрами отличается. Ваши цифры на вход подставил - совпадает как у вас.

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

[_Ivana]

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

Кстати, если верить автору темы в

Steini в сообщении #896172 писал(а):

Или же (крайний, но приемлемый случай) почти всю партию по рублей 15-16, а две штучки по 14 копеек

то имхо всегда возможен быстрый беспереборный вариант в три строки типа такого:

1 строка: 20380 шт по 15.47 = 315278.6, или 13247 кг по 23.8 = 315278.6, отклонение сумм шт/кг 0
2 строка: 82049 шт по 15.6 = 1279964.4, или 53331.85 кг по 24 = 1279964.4, отклонение сумм шт/кг 0
3 строка: 1 шт по 0.05 = 0.05, или 0.65 кг по 0.08 = 0.052, отклонение сумм шт/кг 0.002
Итого   : 102430 шт на сумму 1595243.05, или 66579.5 кг на сумму 1595243.052, отклонение сумм шт/кг 0.002

(в теге кода а не ТЕХе, потому что проще копипастить текст)

[Steini]

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

-- 18.08.2014, 21:20 --

Alexu007
Как я писал выше, все должно идеально совпадать до копеечки, иначе, Вы, мой друг, сраный коррупционер, простите)
_Ivana
К сожалению, как я написал выше, просто убрать нельзя, можно лишь с последней строке рассчитать все на 0,333 штуки, а в жизни послать целую, на бумаге же все должно быть идеально.
По поводу "имхо всегда возможен быстрый беспереборный вариант в три строки типа ..."
пока что не очевидно, что всегда, надо подумать)

Идея алгоритма росписи тремя строками с ценами вокруг "справедливой" следующий. Сначала собрать табличку с тройками цен, далее, как написал _Ivana в своем полном сарказма посте про простую арифметику, и проверять, везде ли кол-ва штук целое. Но здесь сразу минусы - решение может не найтись, потому как по условиям последняя строчка может давать не тождественное равенство, а и хотя бы просто округленно верное. И не будут выводиться пользователю несколько вариантов.

-- 18.08.2014, 21:35 --

По поводу всегда можно беспереборный вариант со списанием копеек по последней штуки. Да я и так делал, а вот как программно определить, сколько же списать по последней штучке? А если вариант, где итоговое число кг целое, а штук - нецелое? т.е. списывать штучку или 0,667 штуки, а может 2,667 штуки? В моем алгоритме перебором такие ситуации обнаруживаются. Как? По остатку. Вот мы расписали Вашим алгоритмом две строки, а на последнюю строку на последнюю штучку получается остаток 400 руб за кг, такое неприемлемо, как я писал выше. В общем переборы, переборы, переборы - наше все. Пока что единственный рабочий вариант - построить табличку цен (оптимальных), потом подбором по количествам проверять всю кучу условий. В случае росписи трех строк это непозволительно долго. Поэтому хочется сузить интервалы подборов количеств. По-умному, конечно.

[Alexu007]

Считайте штуки в рублях, а килограммы и и цены килограмма пишите с десятью знаками после запятой. Тогда и сумма сойдётся до копейки. Извините, но ваши 0, 667 штуки - маразм.