for flooders
:: Главная :: Решения :: Статьи :: Сайт М. Дроздова :: Файловый архив :: Книга по VFP 9 :: Русский Help Online :: OFF-LINE Форум
   Л и с о в о д ы   в с е х   с т р а н,  о б ъ е д и н я й т е с ь !!!  

Список Форумов  :: Игры Разума
   :: Помощь сайту :: 

Отобрать на сумму
Равиль
Автор

Сообщений: 6242
Откуда: Уфа
Дата: 01.11.07 08:24:24ОтветитьЦитировать
Всем привет, возможно подобное обсуждалось - задачка такого типа:

*!* Дано: Таблица товаров - Наименование, кол-во, цена :  
    
  Close Tables  
    
  Create Cursor Test (cName c(20), nKol N(4), nCena N(10,2))  
    
  Insert Into Test ;  
  	(cName, nKol, nCena);  
  	VALUES ;  
  	("Яблоки", 10, 55)  
    
  Insert Into Test ;  
  	(cName, nKol, nCena);  
  	VALUES ;  
  	("Виноград", 10, 75)  
    
  Insert Into Test ;  
  	(cName, nKol, nCena);  
  	VALUES ;  
  	("Груши", 10, 65)  
    
 *!* и так далее ...  
    
  Local m.lnSumma  
  m.lnSumma = 999 && рублей  
    
 *!* Задание: Вырезать из этой таблицы товар в другую таблицу на сумму <= m.lnSumma  
 *!* при условии максимального приближения к этой сумме ))
Необязательно, чтобы в выборку попали все товары ))


------------------
Тяжело согнать курсором муху с монитора ...
Ratings: 0 negative/0 positive

Re: Отобрать на сумму
PaulWist

Сообщений: 13047
Дата: 01.11.07 08:57:36ОтветитьЦитировать
Равиль, привет. Рад видеть

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

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

Цитата:
S(nKoli* nCenai) - m.lnSumma => min
2. Что это значит:

Цитата:
d(S(nKoli* nCenai) - m.lnSumma)/d(nCena) = 0
Блин девки зовут кофе пить, ну думаю идея понятна, надо найти
S(nKoli* nCenai) - m.lnSumma) в аналитическом виде или решить численно.


------------------
Есть многое на свете, друг Горацио...
Что и не снилось нашим мудрецам.
(В.Шекспир Гамлет)
Ratings: 0 negative/0 positive

Re: Отобрать на сумму
Равиль
Автор

Сообщений: 6242
Откуда: Уфа
Дата: 01.11.07 09:08:32ОтветитьЦитировать
Привет, Паша - интересно, и в моем варианте тоже есть "подход с конца" только после сортировки по ценам (nCena)


------------------
Тяжело согнать курсором муху с монитора ...
Ratings: 0 negative/0 positive

Re: Отобрать на сумму
AleksM
[Админ]

Сообщений: 17704
Дата: 01.11.07 09:53:58ОтветитьЦитировать
Цитата:
Блин девки зовут кофе пить,
"Нас на бабу променял ..." (С)


------------------
Лучше переесть, чем недоспать.
Не спеши, а то успеешь.
Ratings: 0 negative/0 positive

Re: Отобрать на сумму
Igor Korolyov

Сообщений: 32376
Дата: 04.11.07 19:05:04ОтветитьЦитировать
Hi Равиль!

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


------------------
WBR, Igor
Ratings: 0 negative/0 positive

Re: Отобрать на сумму
s66

Сообщений: 689
Откуда: Владивосток
Дата: 12.12.07 11:12:15ОтветитьЦитировать
Тут все просто, перевый курс
Делаем запрос с условием 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  && если необходимо
Ну а дальше понятно
Ratings: 0 negative/0 positive

Re: Отобрать на сумму
Равиль
Автор

Сообщений: 6242
Откуда: Уфа
Дата: 12.12.07 14:42:24ОтветитьЦитировать
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 )))

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

*!* Внесем элемент случайности ))  
    
  Rand(-1)  
    
  Close Tables  
    
  Create Cursor Test (Id i, cName C(20), nKol N(4), nCena N(10,2))  
    
  Local m.i, m.k  
  m.k = Int(20 + 20 * Rand())  
    
  For m.i = 1 To m.k  
  	Insert Into Test ;  
  		(Id, cName, nKol, nCena);  
  		Values ;  
  		(m.i, "Товар "+Trans(m.i), 10 + 100 * Rand(), 10 + 100 * Rand())  
  Next  
    
  Local m.lnSumma  
  m.lnSumma = 1000 + Round(1000 * Rand(), 2) && Сумма для отбора  
    
  Go Top  
  Browse Last Title "Исходные данные - Отобрать на сумму "+Transform(m.lnSumma)
*!* а дальше ?


------------------
Тяжело согнать курсором муху с монитора ...




Исправлено: Равиль, 12.12.07 14:46
Ratings: 0 negative/0 positive

Re: Отобрать на сумму
AleksM
[Админ]

Сообщений: 17704
Дата: 12.12.07 14:53:24ОтветитьЦитировать
Может я не в ту степь, НО
  
  select Id, nCol*nCena as Total, lnSumma-nCol*nCena as Diff ;  
     from Test ;  
     where lnSumma>=nCol*nCena ;  
     into cTmp  
  select Id ;  
     from cTmp ;  
     where Diff in (select min(Diff) as Diff from cTmp) ;  
     into cTmp1
Ну дальше наверное понятно


------------------
Лучше переесть, чем недоспать.
Не спеши, а то успеешь.
Ratings: 0 negative/0 positive

Re: Отобрать на сумму
AleksM
[Админ]

Сообщений: 17704
Дата: 12.12.07 14:58:40ОтветитьЦитировать
Равиль, а тебе один товар отобрать надо или корзинку набрать?


------------------
Лучше переесть, чем недоспать.
Не спеши, а то успеешь.
Ratings: 0 negative/0 positive

Re: Отобрать на сумму
Равиль
Автор

Сообщений: 6242
Откуда: Уфа
Дата: 12.12.07 15:01:20ОтветитьЦитировать
Саш, привет - тоже самое - почему вы сразу берете для сравнения все количество каждого товара - можно выбирать часть количества (правда челые числа) из каждой позиции.


------------------
Тяжело согнать курсором муху с монитора ...
Ratings: 0 negative/0 positive

Re: Отобрать на сумму
Равиль
Автор

Сообщений: 6242
Откуда: Уфа
Дата: 12.12.07 15:02:02ОтветитьЦитировать
корзинку - ну если хотите лукошко ))


------------------
Тяжело согнать курсором муху с монитора ...
Ratings: 0 negative/0 positive

Re: Отобрать на сумму
Igor Korolyov

Сообщений: 32376
Дата: 16.12.07 16:58:35ОтветитьЦитировать
Привет Равиль!

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

Re: Отобрать на сумму
Равиль
Автор

Сообщений: 6242
Откуда: Уфа
Дата: 17.12.07 08:31:05ОтветитьЦитировать
Igor Korolyov
... Решения конечно имеются для такой задачи - например "метод ветвей и границ". Он довольно подробно расписан в литераторе, и мне кажется что алгоритм вполне подходит для кодирования
Игорь, привет - спасибо за ответ. Откуда ноги растут ситуация распространенная - Покупатель забирает у Поставщика товар на сумму m.lnSumma, затем перегоняет некоторую сумму m.lnSumma1 < m.lnSumma, остальное платит налом. Нужно сделать ему соответвующие 2 накладные из исходной. При такой постановке, когда нужно точное соотвествие сумме - задача может и не иметь решения, поэтому я немного изменил условия
Сегодня это имеет чисто теоретический интерес, потому что было предложено другое решение.
Порюсь в тырнете - может что-нибудь и получится


------------------
Тяжело согнать курсором муху с монитора ...
Ratings: 0 negative/0 positive



Извините, только зарегистрированные пользователи могут писать в этом форуме.

On-line: 92 Mitjay Alsim sphinx dimuhametov  and Guests: 88


© 2000-2019 Fox Club 
Яндекс.Метрика