|
Поиск суммы в запросе | ☑ | ||
---|---|---|---|---|
0
cj001
22.05.18
✎
15:42
|
Помогите, пожалуйста, решить задачу: имеется таблица, состоящая из неких строк, со столбцом "Количество". Например:
Количество 37 47 16 5 2 Также имеется сумма: 63. Нужно выбрать запросом строки из таблицы, дающие эту сумму. Или хотя бы не запросом. Подскажите какие-нибудь пути решения. Количество строк в таблице меняется. Искомая сумма заведомо известна. |
|||
1
Timon1405
22.05.18
✎
15:43
|
||||
2
3achem
22.05.18
✎
15:43
|
||||
3
cj001
22.05.18
✎
15:57
|
Ранец - это перебор. Понятно. А как FIFO поможет решить задачу?
|
|||
4
3achem
22.05.18
✎
16:00
|
(3) Какой вопрос, такой ответ, вот как это интерпретировать "Нужно выбрать запросом строки из таблицы, дающие эту сумму"?
|
|||
5
bolobol
22.05.18
✎
16:00
|
Задача только на перебор, но, бывает, что суть задачи много проще, чем её описывают.
|
|||
6
exwill
22.05.18
✎
16:00
|
(3) Никак.
|
|||
7
bolobol
22.05.18
✎
16:01
|
(4) Ровно дословно понять, без интерпретаций, никак?
|
|||
8
Tateossian
22.05.18
✎
16:09
|
(0) Это же задача о равенстве классов P и NP. Кто ее решит - получит премию института Клея и $1000000.
https://ru.wikipedia.org/wiki/Равенство_классов_P_и_NP |
|||
9
_Дайвер_
22.05.18
✎
16:32
|
Ему 16 и 47 надо сложить и получить 63, выбрать эти строки, походу задачка у него такая
|
|||
10
_Дайвер_
22.05.18
✎
17:01
|
(8) Он решил лям баксов заработать на нас, хитрый жук!
|
|||
11
polosov
22.05.18
✎
17:02
|
Запрос = Новый Запрос;
Запрос.Текст = "ВЫБРАТЬ | 0 КАК Зн"; ТЗ = Запрос.Выполнить().Выгрузить(); ТЗ.Очистить(); НоваяСтрока = ТЗ.Добавить(); НоваяСтрока.Зн = 37; НоваяСтрока = ТЗ.Добавить(); НоваяСтрока.Зн = 47; НоваяСтрока = ТЗ.Добавить(); НоваяСтрока.Зн = 16; НоваяСтрока = ТЗ.Добавить(); НоваяСтрока.Зн = 5; НоваяСтрока = ТЗ.Добавить(); НоваяСтрока.Зн = 2; Запрос = Новый Запрос; Запрос.Текст = "ВЫБРАТЬ | Таб.Зн КАК Зн |ПОМЕСТИТЬ ВТ1 |ИЗ | &Таб КАК Таб |; | |//////////////////////////////////////////////////////////////////////////////// |ВЫБРАТЬ | ВТ1.Зн КАК ИсхЗн, | ВТ1.Зн КАК Зн1, | ВТ11.Зн КАК Зн2 |ПОМЕСТИТЬ ВТ2 |ИЗ | ВТ1 КАК ВТ1, | ВТ1 КАК ВТ11 |; | |//////////////////////////////////////////////////////////////////////////////// |ВЫБРАТЬ | ВТ2.ИсхЗн КАК ИсхЗн, | ВТ2.Зн1 + ВТ2.Зн2 КАК Зн3 |ПОМЕСТИТЬ ВТ3 |ИЗ | ВТ2 КАК ВТ2 |ГДЕ | ВТ2.Зн1 + ВТ2.Зн2 = 63 |; | |//////////////////////////////////////////////////////////////////////////////// |ВЫБРАТЬ | ВТ3.ИсхЗн КАК ИсхЗн |ИЗ | ВТ3 КАК ВТ3 |ГДЕ | ВТ3.Зн3 = 63"; Запрос.УстановитьПараметр("Таб", ТЗ); РезультатЗапроса = Запрос.Выполнить().Выгрузить(); |
|||
12
spiller26
22.05.18
✎
17:04
|
(0) Запросом ни как?
А так 2 одинаковые таблицы, и пошел по строкам в цикле. типа Для Каждого Стр1 Из Таб1 Цикл Сумм = Стр1.Сумма; Для Каждого Стр2 Из Таб2 Цикл Сумм = Сумм + Стр2.Сумма; Если Сумм = 63 Тогда Сообщить = ""; КонецЕсли; КонецЦикла; КонецЦикла; но если таких вариантов будет несколько, то ж.па |
|||
13
polosov
22.05.18
✎
17:04
|
Тьфу, в ВТ3 секцию ГДЕ можно убрать
|
|||
14
spiller26
22.05.18
✎
17:06
|
(11) Это решение одноразовое. а если не две строки дают такой результат?
|
|||
15
polosov
22.05.18
✎
17:07
|
(14) А ты попробуй
|
|||
16
_Дайвер_
22.05.18
✎
17:07
|
(14) Если не две строки, и еще кол-во строк может быть больше 100 например) Задолбаешься писать запрос
|
|||
17
spiller26
22.05.18
✎
17:10
|
(16) я уже писал, что запросом ни как.
|
|||
18
polosov
22.05.18
✎
17:10
|
(14) Вообще как-то так
Запрос = Новый Запрос; Запрос.Текст = "ВЫБРАТЬ | Таб.Зн КАК Зн |ПОМЕСТИТЬ ВТ1 |ИЗ | &Таб КАК Таб |; | |//////////////////////////////////////////////////////////////////////////////// |ВЫБРАТЬ | ВТ1.Зн КАК ИсхЗн, | ВТ1.Зн КАК Зн1, | ВТ11.Зн КАК Зн2 |ПОМЕСТИТЬ ВТ2 |ИЗ | ВТ1 КАК ВТ1, | ВТ1 КАК ВТ11 |; | |//////////////////////////////////////////////////////////////////////////////// |ВЫБРАТЬ | ВТ2.ИсхЗн КАК ИсхЗн, | ВТ2.Зн1 + ВТ2.Зн2 КАК Зн3, | ВТ2.Зн1 КАК Зн1, | ВТ2.Зн2 КАК Зн2 |ПОМЕСТИТЬ ВТ3 |ИЗ | ВТ2 КАК ВТ2 |; | |//////////////////////////////////////////////////////////////////////////////// |ВЫБРАТЬ | ВТ3.Зн1 КАК Зн1, | ВТ3.Зн2 КАК Зн2 |ИЗ | ВТ3 КАК ВТ3 |ГДЕ | ВТ3.Зн3 = 63"; Ну там только одинаковые комбинации исключить осталось |
|||
19
_Дайвер_
22.05.18
✎
17:14
|
Полным перебором только если
Для каждого ТекЧисло Из ТабЧасть Цикл и поехал |
|||
20
spiller26
22.05.18
✎
17:16
|
(18) Вот тебе посложнее, немного добавим входящих данных
37 47 16 5 2 40 23 ------------------------- 63 = 47+16 63 = 16+5+2+40 63 = 40+23 |
|||
21
RomanYS
22.05.18
✎
17:17
|
(19) я бы поехал по другому:
Для инд = 1 По Pow(2, ТЗ.Количество()) Цикл ... |
|||
22
spiller26
22.05.18
✎
17:26
|
мне кажется, что это из ряда нахождения хэш, вычислить все варианты при котором будет равняться некое число.
|
|||
23
spiller26
22.05.18
✎
17:38
|
||||
24
spiller26
22.05.18
✎
17:39
|
||||
25
_Дайвер_
22.05.18
✎
17:40
|
(21) В степень то зачем?Ты понимаешь что при наличии 3-х значений у тебя будет цикл из 27? Когда вариантов получить нужное значение всего 7?
Например есть у нас ТЗ с колонкой кол-во,в ней 3 значения (1,2,3), нужно получить например значение "3", чтобы перебрать все значения просто складываем все возможные варианты: 1 1+2 1+3 2 2+3 3 1+2+3 Итого есть 2 варианта: "1+2" и "3", 7 переборов, 2 результата |
|||
26
spiller26
22.05.18
✎
17:43
|
(24) Вот написано на Cи https://habr.com/post/203362/ можно перелопатить на 1с язык
|
|||
27
ERWINS
22.05.18
✎
17:47
|
"выбрать запросом "
|
|||
28
ERWINS
22.05.18
✎
17:48
|
не знаю как делать в запросе N^N строк
|
|||
29
ERWINS
22.05.18
✎
17:48
|
понял!!!!
надо делать через разложение в простые |
|||
30
RomanYS
22.05.18
✎
18:03
|
(25) 2^3=8, это и есть твои 7 плюс нулевой.
|
|||
31
RomanYS
22.05.18
✎
18:05
|
Ещё проще рекурсией, но больше рисков, что загнется по памяти
|
|||
32
exwill
22.05.18
✎
18:10
|
(28) ВЫБРАТЬ ... ИЗ Таб,Таб
|
|||
33
Franchiser
гуру
22.05.18
✎
18:13
|
(26) этот код работает только для 20 чисел, при 50 он уже неработоспособен
|
|||
34
RomanYS
22.05.18
✎
18:17
|
(31) (20)
перем Мас, ИскомаяСумма, Количество; Процедура Обход(ТекНабор = "", СуммаВх = 0, индНач = 0) Для инд = индНач По Количество Цикл Сумма = СуммаВх + мас[инд]; Если Сумма = ИскомаяСумма Тогда Сообщить(ТекНабор+"+"+мас[инд]); ИначеЕсли Сумма < ИскомаяСумма Тогда Обход(ТекНабор+"+"+мас[инд], Сумма, инд+1); КонецЕсли; КонецЦикла; КонецПроцедуры Мас = Новый Массив; Мас.Добавить(37); Мас.Добавить(47); Мас.Добавить(16); Мас.Добавить(5); Мас.Добавить(2); Мас.Добавить(40); Мас.Добавить(23); Количество = Мас.Количество(); ИскомаяСумма = 63; Обход(); |
|||
35
Franchiser
гуру
22.05.18
✎
18:43
|
ТЗ1 = ПолучитьТаблицу0и1РазмерностиN(Н); //Таблица из 3 колонок вида Ai | Bj | (0 или 1)
ТЗ2 = ПолучитьТаблицуДляМассиваЗначений(); //Таблица из 2 колонок вида i | Xi Запрос = Новый Запрос; Запрос.Текст = "ВЫБРАТЬ | Тз1.А, | Тз1.В, | Тз1.Х |ПОМЕСТИТЬ Тз1 |ИЗ | &Тз1 КАК Тз1 |; | |//////////////////////////////////////////////////////////////////////////////// |ВЫБРАТЬ | Тз2.Н, | Тз2.ХН |ПОМЕСТИТЬ Тз2 |ИЗ | &Тз2 КАК Тз2 |; | |//////////////////////////////////////////////////////////////////////////////// |ВЫБРАТЬ | Тз1.А, | Тз1.В, | Тз1.Х * Тз2.ХН КАК Х |ПОМЕСТИТЬ НеСгруппированно |ИЗ | Тз1 КАК Тз1 | ВНУТРЕННЕЕ СОЕДИНЕНИЕ Тз2 КАК Тз2 | ПО Тз1.В = Тз2.Н |; | |//////////////////////////////////////////////////////////////////////////////// |ВЫБРАТЬ | НеСгрупированно.А, | СУММА(НеСгрупированно.Х) КАК Х |ПОМЕСТИТЬ Сгруппировано |ИЗ | НеСгруппированно КАК НеСгрупированно | |СГРУППИРОВАТЬ ПО | НеСгрупированно.А |; | |//////////////////////////////////////////////////////////////////////////////// |ВЫБРАТЬ ПЕРВЫЕ 1 | Сгруппировано.А |ИЗ | Сгруппировано КАК Сгруппировано |ГДЕ | Сгруппировано.Х | |УПОРЯДОЧИТЬ ПО | Сгруппировано.Х УБЫВ"; Запрос.УстановитьПараметр("ТЗ1",ТЗ1 ); Запрос.УстановитьПараметр("ТЗ2",ТЗ2 ); Запрос.УстановитьПараметр("Р",НекоеПороговоеЗначение); Результат = Запрос.Выполнить(); Выборка = Результат.Выбрать(); Если Выборка.Следующий() тогда ОптимальнаяСтрокаИз0и1 = ПолучитьСтроку0и1ИзТаблицыПоНомеру(Выборка.А); КонецЕсли; |
|||
36
ERWINS
22.05.18
✎
20:13
|
(32) это N^2, а задача требует перебора 2^N
|
|||
37
Михаил Козлов
22.05.18
✎
21:07
|
(8) Все-таки ранец слишком специфическая NP-полная задача. Реальные задачи о ранце вполне решаемы.
Вот вполне реализуемый подход: пусть Аi - i-тое число. Составим (производящую) функцию: F(x) = (1+x^A1)*((1+x^A2)*...*(1+x^An). Если раскрыть скобки, то коэффицент при x^b даст число решений уравнения СУММА(Ai*zi)=b в zi=0 или 1. Трудоемкость раскрытия скобок примерно СУММА(Ai) (это совсем не полином по длине записи задачи). Раскрывать их можно так, чтобы получать и одно из решений. Т.к. такая задача на мисте возникает регулярно, как всегда, вопрос: "А нужно ли именно это?". |
|||
38
cj001
23.05.18
✎
08:42
|
Спасибо за помощь.
|
Форум | Правила | Описание | Объявления | Секции | Поиск | Книга знаний | Вики-миста |