Отобрать на сумму | |
---|---|
Равиль Автор Сообщений: 6549 Откуда: Уфа Дата регистрации: 01.08.2003 |
Всем привет, возможно подобное обсуждалось - задачка такого типа:
------------------ Тяжело согнать курсором муху с монитора ... |
Re: Отобрать на сумму | |
---|---|
PaulWist Сообщений: 14618 Дата регистрации: 01.04.2004 |
Равиль, привет. Рад видеть
Давай рассуждать (информация к размышлению), пойдем к конца 1. Сумма товаров минус заданное кол-во денег должно быть минимальным, тогда Цитата:2. Что это значит: Цитата:Блин девки зовут кофе пить, ну думаю идея понятна, надо найти S(nKoli* nCenai) - m.lnSumma) в аналитическом виде или решить численно. ------------------ Есть многое на свете, друг Горацио... Что и не снилось нашим мудрецам. (В.Шекспир Гамлет) |
Re: Отобрать на сумму | |
---|---|
Равиль Автор Сообщений: 6549 Откуда: Уфа Дата регистрации: 01.08.2003 |
Привет, Паша - интересно, и в моем варианте тоже есть "подход с конца" только после сортировки по ценам (nCena)
------------------ Тяжело согнать курсором муху с монитора ... |
Re: Отобрать на сумму | |
---|---|
AleksM Сообщений: 17881 Дата регистрации: 11.11.2003 |
Цитата:"Нас на бабу променял ..." (С) ------------------ Лучше переесть, чем недоспать. Не спеши, а то успеешь. |
Re: Отобрать на сумму | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Hi Равиль!
В чистом виде задача линейного программирования Этому в ВУЗах даже не-математиков учат - можно почитать и в инете теорию... Там всё достаточно просто, алгоритмы формализованы. ------------------ WBR, Igor |
Re: Отобрать на сумму | |
---|---|
s66 Сообщений: 689 Откуда: Владивосток Дата регистрации: 09.02.2007 |
Тут все просто, перевый курс
Делаем запрос с условием nkol*ncena<=lnSumma можно сразу с полем (nkol*ncena) потом
|
Re: Отобрать на сумму | |
---|---|
Равиль Автор Сообщений: 6549 Откуда: Уфа Дата регистрации: 01.08.2003 |
Спасибо, но этот алгоритм не даст выборку максимально приближенную к требуемой сумме. Хотя бы потому, что из нее сразу исключаются позиции в которых nKol * nCena > m.lnSumma А вдруг как раз в этой позиции мы получили бы равенство (nKol - m.i) * nCena = m.lnSumma ))) Я тоже поначалу подумал, что все просто, но после того, как Игорь Королев посоветовал искать решение в алгоритмах линейного программирования ... немного охладел к теме ))
------------------ Тяжело согнать курсором муху с монитора ... Исправлено 1 раз(а). Последнее : Равиль, 12.12.07 15:46 |
Re: Отобрать на сумму | |
---|---|
AleksM Сообщений: 17881 Дата регистрации: 11.11.2003 |
Может я не в ту степь, НО
------------------ Лучше переесть, чем недоспать. Не спеши, а то успеешь. |
Re: Отобрать на сумму | |
---|---|
AleksM Сообщений: 17881 Дата регистрации: 11.11.2003 |
Равиль, а тебе один товар отобрать надо или корзинку набрать?
------------------ Лучше переесть, чем недоспать. Не спеши, а то успеешь. |
Re: Отобрать на сумму | |
---|---|
Равиль Автор Сообщений: 6549 Откуда: Уфа Дата регистрации: 01.08.2003 |
Саш, привет - тоже самое - почему вы сразу берете для сравнения все количество каждого товара - можно выбирать часть количества (правда челые числа) из каждой позиции.
------------------ Тяжело согнать курсором муху с монитора ... |
Re: Отобрать на сумму | |
---|---|
Равиль Автор Сообщений: 6549 Откуда: Уфа Дата регистрации: 01.08.2003 |
корзинку - ну если хотите лукошко ))
------------------ Тяжело согнать курсором муху с монитора ... |
Re: Отобрать на сумму | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Привет Равиль!
Да, дело это непростое. Основная сложность состоит именно в том что необходимо использовать целочисленные методы ЛП Если бы не это, то решение получалось бы тривиальным (но конечно неоднозначным ;) ). В общем случае когда задана система ограничений вида Xi<=Bi, Xi>=0 и плюс к тому Sum(Xi*Ai) = C, где Xi - отбираемое количесто i-го товара, Bi-максимально доступное количество i-го товара (по логике Bi>=0), Ai - цена i-го товара (тоже примем что Ai>=0) и C - общая сумма денег (опять таки примем что C>=0); решения могут быть следующие: 1) одно решение - это если C=0 - нет денег - ничего нельзя купить, или C>=Sum(Bi*Ai) - денег слишком много - скупаем всё что есть. 2) Бесконечное множество решений в случае 0<C<Sum(Bi*Ai). Решение представляет собой "поверхности" в n-мерном пространстве (n - число видов товаров). Причём поверхности первого порядка (грубо говоря "плоскость"). Проще всего это представить для случая 2 или 3 видов товаров - для n=2 мы имеем прямую заданную уравнением x*A1+y*A2=C (я просто переименовал X1 и X2 в принятые обозначения для 2-мерной геометрии) для n=3 это плоскость x*A1+y*A2+z*A3=C. Причём эта поверхность ограничена (отсечена) соответствующими поверхностями, паралельными координатным плоскостям (или просто осям координат для случая n=2). Любая точка данной поверхности удовлетворяет решению - НО они конечно в большинстве своём не целые числа... Решения конечно имеются для такой задачи - например "метод ветвей и границ". Он довольно подробно расписан в литераторе, и мне кажется что алгоритм вполне подходит для кодирования ------------------ WBR, Igor |
Re: Отобрать на сумму | |
---|---|
Равиль Автор Сообщений: 6549 Откуда: Уфа Дата регистрации: 01.08.2003 |
Игорь, привет - спасибо за ответ. Откуда ноги растут ситуация распространенная - Покупатель забирает у Поставщика товар на сумму m.lnSumma, затем перегоняет некоторую сумму m.lnSumma1 < m.lnSumma, остальное платит налом. Нужно сделать ему соответвующие 2 накладные из исходной. При такой постановке, когда нужно точное соотвествие сумме - задача может и не иметь решения, поэтому я немного изменил условия Сегодня это имеет чисто теоретический интерес, потому что было предложено другое решение. Порюсь в тырнете - может что-нибудь и получится ------------------ Тяжело согнать курсором муху с монитора ... |
© 2000-2024 Fox Club  |