ReSQL.ru
     
powered by simpleCommunicator - 2.0.53     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / FoxPro, Visual FoxPro [игнор отключен] [закрыт для гостей] / Как подобрать значения полей таблицы к сумме
15 сообщений из 15, страница 1 из 1
Как подобрать значения полей таблицы к сумме
    #37598802
pirogon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
pirogon
Гость
Всем здравствуйте.

Возникла проблема с алгоритмом. Есть таблица podbor.dbf. Три поля, два числовых и дата. и есть число 109000. Задача - выбрать из данной таблицы записи, сумма полей t_sm которых составит 109000. Как только не извращался, но отсутствие высшего образования и прошедший корпоратив ни разу не способствовали решению проблемы.
...
Рейтинг: 0 / 0
29.12.2011, 12:32
| Ответить | Цитировать | Написать  
Как подобрать значения полей таблицы к сумме
    #37598822
IgorNG
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
IgorNG
Участник
pirogon,

Ну а в цикле суммировать, пока сумма меньше необходимой.
...
Рейтинг: 0 / 0
29.12.2011, 12:42
| Ответить | Цитировать | Написать  
Как подобрать значения полей таблицы к сумме
    #37598843
pirogon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
pirogon
Гость
IgorNG, спасибо за внимание, пробовал, проблема в том, что искомая комбинация не всегда составляется прямо, что ли. В данном случае подобрал комбинацию из 8 полей, с помощью калькулятора и случая... но уверили что такая задача будет чуть не каждую неделю и хотелось бы ее облегчить.
...
Рейтинг: 0 / 0
29.12.2011, 12:50
| Ответить | Цитировать | Написать  
Как подобрать значения полей таблицы к сумме
    #37598978
IgorNG
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
IgorNG
Участник
pirogon,

Так объясни задачу поконкретнет. А то пока понятно, что нужно отобрать из всего количества записей, чтобы была РОВНО определенная сумма. Так чисто гипотетически, можно ведь и не подобрать. Поэтому и написал про цикл - суммировать, пока сумма меньше или равна. Но при цикле будут участвовать одни и те же записи.
...
Рейтинг: 0 / 0
29.12.2011, 13:52
| Ответить | Цитировать | Написать  
Как подобрать значения полей таблицы к сумме
    #37599004
pirogon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
pirogon
Гость
IgorNG, извиняюсь, нужно строгое равенство, не максимально приближенное, а строгое, т.е. это реальные суммы, проходящие по учету, просто перечислять их будут только часть. А получить информацию, какие именно платежи поступили в оплату, не представляется возможным, надеюсь пока. Извиняюсь за туманность формулировок, если что объясню подробней.
...
Рейтинг: 0 / 0
29.12.2011, 14:04
| Ответить | Цитировать | Написать  
Как подобрать значения полей таблицы к сумме
    #37599096
IgorNG
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
IgorNG
Участник
pirogon,

Ну, если это 12 строк, то еще как-то можно, а если строк будет 1000?
Ну, а в принципе алгоритм простой - перебор записей.
Например, берется 1-я запись, к ней прибавляется 2-я. Если больше искомой суммы, то берется 1-я запись, к ней прибавляется третья и т.д. Ну, а теперь представьте какое количество комбинация может быть даже в этих 12 строках.
...
Рейтинг: 0 / 0
29.12.2011, 14:34
| Ответить | Цитировать | Написать  
Как подобрать значения полей таблицы к сумме
    #37599174
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
 
Пример перебора всех вариантов
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
lnSumFind = 109000 && Искомое значение
* Получаем набор значений которые надо скомбинировать
select *, .F. as lUse from podbor into cursor tRes readwrite
sele tRes
sum t_sm to lnSumMax
do while .T.
	* Устанавливаем очередной вариант
	scan
		if lUse
			repl lUse with .F.
		else
			repl lUse with .T.
			exit
		endif
	endscan
	* проверяем
	sum for lUse t_sm to lnSum
	do case
		case lnSum = lnSumFind
			* нашли
			brow for lUse
			exit
		case lnSum = lnSumMax
			MessageBox('Подобрать невозможно')
			exit
	endcase
enddo


При небольшом количестве значений перебора достаточно. Количество перебираемых вариантов = 2 в степени количества записей минус 1. В данном случае 2^12 - 1 = 4095, нездоровая зависимость, если значений будет 30 то это уже миллиард комбинаций :)

Можно немного оптимизировать этот код, можно переписать его на Си или ASMе, тогда быстрее перебирать будет. Но больше 30-35 значений перебирать не получится.

Хоть высшую математику и изучал, но за давностью лет и ненадобностью помню только что вроде есть какие-то хитрые алгоритмы по этому поводу. Конкретнее думаю в форуме по алгоритмам подскажут.

PS Я не смог подобрать 109000 по данным из твоей DBF-ки
...
Рейтинг: 0 / 0
29.12.2011, 15:14
| Ответить | Цитировать | Написать  
Как подобрать значения полей таблицы к сумме
    #37599245
pirogon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
pirogon
Гость
Спасибо, просмотрел задачку по загрузке рюкзака, попробовал, должно получиться. Но задача остается на пару недель. Нет предела для оптимизации:)
...
Рейтинг: 0 / 0
29.12.2011, 15:46
| Ответить | Цитировать | Написать  
Как подобрать значения полей таблицы к сумме
    #37599257
pirogon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
pirogon
Гость
Дмитрий Т, отдельное Спасибо за разъяснение, обязательно попробую, но боюсь что уже не сегодня...
...
Рейтинг: 0 / 0
29.12.2011, 15:49
| Ответить | Цитировать | Написать  
Как подобрать значения полей таблицы к сумме
    #37599266
IgorNG
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
IgorNG
Участник
Dima T+
 
Пример перебора всех вариантов
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
lnSumFind = 109000 && Искомое значение
* Получаем набор значений которые надо скомбинировать
select *, .F. as lUse from podbor into cursor tRes readwrite
sele tRes
sum t_sm to lnSumMax
do while .T.
	* Устанавливаем очередной вариант
	scan
		if lUse
			repl lUse with .F.
		else
			repl lUse with .T.
			exit
		endif
	endscan
	* проверяем
	sum for lUse t_sm to lnSum
	do case
		case lnSum = lnSumFind
			* нашли
			brow for lUse
			exit
		case lnSum = lnSumMax
			MessageBox('Подобрать невозможно')
			exit
	endcase
enddo


При небольшом количестве значений перебора достаточно. Количество перебираемых вариантов = 2 в степени количества записей минус 1. В данном случае 2^12 - 1 = 4095, нездоровая зависимость, если значений будет 30 то это уже миллиард комбинаций :)

Можно немного оптимизировать этот код, можно переписать его на Си или ASMе, тогда быстрее перебирать будет. Но больше 30-35 значений перебирать не получится.

Хоть высшую математику и изучал, но за давностью лет и ненадобностью помню только что вроде есть какие-то хитрые алгоритмы по этому поводу. Конкретнее думаю в форуме по алгоритмам подскажут.

PS Я не смог подобрать 109000 по данным из твоей DBF-ки

А не подобрал, потому что у тебя ы цикле SCAN помечается только одна запись, а при повторном скане метка с этой записи снимается и ставится на другую запись, но одну. А чтобы получить искомую сумму может быть сложено неизвестное количество записей.
...
Рейтинг: 0 / 0
29.12.2011, 15:55
| Ответить | Цитировать | Написать  
Как подобрать значения полей таблицы к сумме
    #37599281
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
IgorNGА не подобрал, потому что у тебя....
Ты сначала сам подбери, тут озвучь, а потом косяки в моем коде ищи.

Я не подобрал потому что невозможно 109000 подобрать, потому что pirogon после вчерашнего корпоратива на калькуляторе подбирал
...
Рейтинг: 0 / 0
29.12.2011, 16:05
| Ответить | Цитировать | Написать  
Как подобрать значения полей таблицы к сумме
    #37599306
IgorNG
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
IgorNG
Участник
Dima T,

Ты не обижайся. Я блох не искал. Мне просто показалось, что код слишком прост для этой задачи и посмотрел его внимательно ради собственного интереса.
...
Рейтинг: 0 / 0
29.12.2011, 16:32
| Ответить | Цитировать | Написать  
Как подобрать значения полей таблицы к сумме
    #37599316
reware
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
reware
Участник
pirogonВсем здравствуйте.
Возникла проблема с алгоритмом. Есть таблица podbor.dbf. Три поля, два числовых и дата. и есть число 109000. Задача - выбрать из данной таблицы записи, сумма полей t_sm которых составит 109000. Как только не извращался, но отсутствие высшего образования и прошедший корпоратив ни разу не способствовали решению проблемы.
Чистая задача из области комбинаторики. Т.е. надо в данном случае найти записи, сумма полей которых равна Х. Читайте про комбинаторику, это не есть задача чисто программирования.
...
Рейтинг: 0 / 0
29.12.2011, 16:37
| Ответить | Цитировать | Написать  
Как подобрать значения полей таблицы к сумме
    #37599970
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
IgorNGDima T,

Ты не обижайся. Я блох не искал. Мне просто показалось, что код слишком прост для этой задачи и посмотрел его внимательно ради собственного интереса.
Проехали. Код простой потому что было два года изучения двоичной логики по 4-5 пар в неделю :)
...
Рейтинг: 0 / 0
30.12.2011, 10:04
| Ответить | Цитировать | Написать  
Как подобрать значения полей таблицы к сумме
    #37608951
pirogon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
pirogon
Гость
Спасибо всем кто приложился к данной проблеме. Вопреки праздникам. Сейчас попробую все коды, по результатам отпишу. Еще раз спасибо.
...
Рейтинг: 0 / 0
11.01.2012, 12:06
| Ответить | Цитировать | Написать  
15 сообщений из 15, страница 1 из 1
Форумы / FoxPro, Visual FoxPro [игнор отключен] [закрыт для гостей] / Как подобрать значения полей таблицы к сумме
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=41&msg=37608951&tid=1583897]:
 0ms
get settings:
 10ms
get forum list:
 14ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 41ms
get topic data:
 11ms
get forum data:
 3ms
get page messages:
 58ms
get tp. blocked users:
 2ms
others: 255ms
total:  402ms
созд. / загр.: 402ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]