Имя: Пароль:
1C
1С v8
Поиск суммы в запросе
, ,
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
Спасибо за помощь.
Компьютер — устройство, разработанное для ускорения и автоматизации человеческих ошибок.