Всем привет, возможно подобное обсуждалось - задачка такого типа:

Необязательно, чтобы в выборку попали все товары ))

Равиль, привет. Рад видеть

Давай рассуждать (информация к размышлению), пойдем к конца

1. Сумма товаров минус заданное кол-во денег должно быть минимальным, тогда

Цитата:

S(nKol_i* nCena_i) - m.lnSumma => min

2. Что это значит:

Цитата:

d(S(nKol_i* nCena_i) - m.lnSumma)/d(nCena) = 0

Блин девки зовут кофе пить, ну думаю идея понятна, надо найти
S(nKol_i* nCena_i) - m.lnSumma) в аналитическом виде или решить численно.

Привет, Паша - интересно, и в моем варианте тоже есть "подход с конца" только после сортировки по ценам (nCena)

Цитата:

Блин девки зовут кофе пить,

"Нас на бабу променял ..." (С)

Hi Равиль!

В чистом виде задача линейного программирования Этому в ВУЗах даже не-математиков учат - можно почитать и в инете теорию... Там всё достаточно просто, алгоритмы формализованы.

Тут все просто, перевый курс
Делаем запрос с условием nkol*ncena<=lnSumma можно сразу с полем (nkol*ncena)
потом
Ну а дальше понятно

s66
Тут все просто, перевый курс
Делаем запрос с условием nkol*ncena<=lnSumma можно сразу с полем (nkol*ncena)
потом

SELECT Cursor
CALCULATE MAX(nkol*ncena) TO lnSum
LOCATE FOR nkol*ncena=lnsum
SELECT Test
LOCATE FOR ALLTRIM(Test.Name)==ALLTRIM(Cursor.Name)
*добавляем запись в другую таблицу
*CONTINUE  && если необходимо

Ну а дальше понятно

Спасибо, но этот алгоритм не даст выборку максимально приближенную к требуемой сумме.
Хотя бы потому, что из нее сразу исключаются позиции в которых nKol * nCena > m.lnSumma
А вдруг как раз в этой позиции мы получили бы равенство (nKol - m.i) * nCena = m.lnSumma )))

Я тоже поначалу подумал, что все просто, но после того, как Игорь Королев посоветовал искать решение в алгоритмах линейного программирования ... немного охладел к теме ))

*!* а дальше ?





Исправлено 1 раз(а). Последнее : Равиль, 12.12.07 15:46

Может я не в ту степь, НО
Ну дальше наверное понятно

Равиль, а тебе один товар отобрать надо или корзинку набрать?

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

корзинку - ну если хотите лукошко ))

Привет Равиль!

Да, дело это непростое. Основная сложность состоит именно в том что необходимо использовать целочисленные методы ЛП
Если бы не это, то решение получалось бы тривиальным (но конечно неоднозначным ;) ).
В общем случае когда задана система ограничений вида 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). Любая точка данной поверхности удовлетворяет решению - НО они конечно в большинстве своём не целые числа...

Решения конечно имеются для такой задачи - например "метод ветвей и границ". Он довольно подробно расписан в литераторе, и мне кажется что алгоритм вполне подходит для кодирования

Igor Korolyov
... Решения конечно имеются для такой задачи - например "метод ветвей и границ". Он довольно подробно расписан в литераторе, и мне кажется что алгоритм вполне подходит для кодирования

Игорь, привет - спасибо за ответ. Откуда ноги растут ситуация распространенная - Покупатель забирает у Поставщика товар на сумму m.lnSumma, затем перегоняет некоторую сумму m.lnSumma1 < m.lnSumma, остальное платит налом. Нужно сделать ему соответвующие 2 накладные из исходной. При такой постановке, когда нужно точное соотвествие сумме - задача может и не иметь решения, поэтому я немного изменил условия
Сегодня это имеет чисто теоретический интерес, потому что было предложено другое решение.
Порюсь в тырнете - может что-нибудь и получится