Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Возможно ли сделать все возможные суммы всех значений ?  [new]
Sergey04
Member

Откуда:
Сообщений: 53
Добрый день !
Подскажите пож-та, можно ли с помощью какой-либо функции или синтаксиса решить следующую задачу:
имеется таблица с полями
n val
1 100
2 120
3 200
4 368
5 1500
...

Мне необходимо из этих значений (val) получить все возможные суммы всех значений. Т.е.
100 + 120
100 + 120 + 200
100 + 120 + 368
100 + 368
120 + 1500
и т.д.

Сгруппировать их и около каждого поставить max(n).
Возможно ли такое ?

Буду очень вам признателен за помощь.
С уважением, Сергей.
17 дек 13, 00:17    [15302187]     Ответить | Цитировать Сообщить модератору
 Re: Возможно ли сделать все возможные суммы всех значений ?  [new]
sdet
Member

Откуда:
Сообщений: 463
Sergey04,
представьте в цифрах конечный результат в виде таблицы
17 дек 13, 00:41    [15302231]     Ответить | Цитировать Сообщить модератору
 Re: Возможно ли сделать все возможные суммы всех значений ?  [new]
Sergey04
Member

Откуда:
Сообщений: 53
sdet,
В принципе, вводных данных в основном < 10
Если их после сгруппировать - не совсем космос должен получиться. Хотя, конечно, могу ошибаться.
17 дек 13, 01:27    [15302310]     Ответить | Цитировать Сообщить модератору
 Re: Возможно ли сделать все возможные суммы всех значений ?  [new]
Ennor Tiegael
Member

Откуда:
Сообщений: 3274
Sergey04
100 + 120 + 368
Попахивает факториальной зависимостью.

И подробнее объясните, что именно надо. Только по 3 элемента группировать? Почему после 100 + 368 не пошло 100 + 368 + 120? Ничего не понятно, короче.
17 дек 13, 05:41    [15302459]     Ответить | Цитировать Сообщить модератору
 Re: Возможно ли сделать все возможные суммы всех значений ?  [new]
AlexandrPlus
Member

Откуда:
Сообщений: 7887
вообще, если не важно - что в сумме, как следуют, ..., то есть только значения

добавим 0 к
таблица t
n val
1 100
2 120
3 200
4 368
5 1500
...
9...9 0

и пусть суммы до k слагаемых
select
distinct t1.val+...+tk.val 
from t t1, ..., t tk 
where 
(t1.val+...+tk.val)<>0


Или уже для любой таблицы для суммы до числа слагаемых, равных количеству строк, процедура (или функция) нужна?
17 дек 13, 08:12    [15302533]     Ответить | Цитировать Сообщить модератору
 Re: Возможно ли сделать все возможные суммы всех значений ?  [new]
AlexandrPlus
Member

Откуда:
Сообщений: 7887
AlexandrPlus
вообще, если не важно - что в сумме, как следуют, ..., то есть только значения

добавим 0 к
таблица t
n val
1 100
2 120
3 200
4 368
5 1500
...
9...9 0

и пусть суммы до k слагаемых
select
distinct t1.val+...+tk.val 
from t t1, ..., t tk 
where 
(t1.val+...+tk.val)<>0



Или уже для любой таблицы для суммы до числа слагаемых, равных количеству строк, процедура (или функция) нужна?


пардон
при таком подходе, как указал, наверно как раз для n=10 будет "комбинаторный взрыв"
(то есть для некоторого условного компьютера для n-1 расчет будет пару минут,
а для n - уже несколько суток)
ЗЫ Такая вот красота.
17 дек 13, 09:00    [15302615]     Ответить | Цитировать Сообщить модератору
 Re: Возможно ли сделать все возможные суммы всех значений ?  [new]
AlexandrPlus
Member

Откуда:
Сообщений: 7887
AlexandrPlus
AlexandrPlus
вообще, если не важно - что в сумме, как следуют, ..., то есть только значения

добавим 0 к
таблица t
n val
1 100
2 120
3 200
4 368
5 1500
...
9...9 0

и пусть суммы до k слагаемых
select
distinct t1.val+...+tk.val 
from t t1, ..., t tk 
where 
(t1.val+...+tk.val)<>0




Или уже для любой таблицы для суммы до числа слагаемых, равных количеству строк, процедура (или функция) нужна?


пардон
при таком подходе, как указал, наверно как раз для n=10 будет "комбинаторный взрыв"
(то есть для некоторого условного компьютера для n-1 расчет будет пару минут,
а для n - уже несколько суток)
ЗЫ Такая вот красота.


да, для такой конструкции (и не для машин, которые называются
сегодня - суперкомпьютеры) - именно 10
17 дек 13, 09:57    [15302873]     Ответить | Цитировать Сообщить модератору
 Re: Возможно ли сделать все возможные суммы всех значений ?  [new]
Sergey04
Member

Откуда:
Сообщений: 53
Ennor Tiegael
Sergey04
100 + 120 + 368
Попахивает факториальной зависимостью.

И подробнее объясните, что именно надо. Только по 3 элемента группировать? Почему после 100 + 368 не пошло 100 + 368 + 120? Ничего не понятно, короче.


Пробую подробнее. Ну вот, например, есть здание. В нем есть офисы разной площади:
120 кв.м.
160 кв.м.
540 кв.м.

Вам, например, нужен офис 700 кв.м. Такого офиса в этом здании нет. Но есть 540 кв.м. и 160 кв.м., что в сумме дает 700. Поэтому мне нужно из этих 3-х цифр создать всевозможные комбинации сумм.

120 кв.м.
160 кв.м.
540 кв.м.
а также
120+160=280 кв.м.
120+540=660 кв.м.
160+540=700 кв.м.

С уважением, Сергей.
17 дек 13, 12:33    [15303922]     Ответить | Цитировать Сообщить модератору
 Re: Возможно ли сделать все возможные суммы всех значений ?  [new]
o-o
Guest
ну и где тут группировка и max(n)?
или надо просто всевозможные суммы получить из всевозможного числа слагаемых?
17 дек 13, 12:53    [15304061]     Ответить | Цитировать Сообщить модератору
 Re: Возможно ли сделать все возможные суммы всех значений ?  [new]
Ennor Tiegael
Member

Откуда:
Сообщений: 3274
Sergey04,

Это называется "задача о рюкзаке". Ищите, и откроется.
17 дек 13, 13:18    [15304303]     Ответить | Цитировать Сообщить модератору
 Re: Возможно ли сделать все возможные суммы всех значений ?  [new]
Sergey04
Member

Откуда:
Сообщений: 53
Да, похоже, что задача о рюкзаке - это действительно то, что нужно.
Буду изучать. Я так понимаю - готового решения нет ?

С уважением, Сергей.
17 дек 13, 17:53    [15306803]     Ответить | Цитировать Сообщить модератору
 Re: Возможно ли сделать все возможные суммы всех значений ?  [new]
sdet
Member

Откуда:
Сообщений: 463
Sergey04
Да, похоже, что задача о рюкзаке - это действительно то, что нужно.
Буду изучать. Я так понимаю - готового решения нет ?

С уважением, Сергей.

Вы сначала определитесь, что вам надо, а потом думайте о готовом решении.
17 дек 13, 18:04    [15306854]     Ответить | Цитировать Сообщить модератору
 Re: Возможно ли сделать все возможные суммы всех значений ?  [new]
AlexandrPlus
Member

Откуда:
Сообщений: 7887
Sergey04
Да, похоже, что задача о рюкзаке - это действительно то, что нужно.
Буду изучать. Я так понимаю - готового решения нет ?

С уважением, Сергей.


в рюкзак нужно максимально больше всунуть, не превысив объем рюкзака
ЗЫ Потом добавляются условия - что должно быть обязательно, что не может быть вместе в одном мешке, ...
НУ КАК В ЖИЗНИ.

а в аренду нужно сдать минимальное количество площадей, но чтобы общая сданная площадь превышала
требуемую
ЗЫ А потом НАВЕРНЯКА добавятся условия, чтобы офисы были ближе, если это проектная работа (или дальше, если это торговля), офисы были одного класса, один офис не большой - для начальников и его команды ("мозгов бизнеса"), а другие покрупнее, где будет располагаться "рабочая сила бизнеса", ...

PS Это в математике называется - двойственные задачи.
17 дек 13, 18:18    [15306912]     Ответить | Цитировать Сообщить модератору
 Re: Возможно ли сделать все возможные суммы всех значений ?  [new]
Добрый Э - Эх
Guest
Sergey04
Я так понимаю - готового решения нет ?
Да так-то задача более чем тривиальная. Любой и сам может "приготовить" её в соответствии со своими вкусовыми пристрастиями.
Как вариант:
--
-- Тестовый набор данных (для примера три числа - 1,2,3):
with
  t as
  (
     select level as num
       from dual
    connect by level <= 3
  )
--
-- Основной запрос:
select ltrim(sys_connect_by_path(num,'+'),'+') as str_summ,
       -- Динамически расчитываем сумму получившейся комбинации чисел:
       extractvalue
         (dbms_xmlgen.getxmltype
           ('select '||ltrim(sys_connect_by_path(num,'+'),'+')||
            ' as summ FROM dual')
           ,'/ROWSET/ROW/SUMM'
         ) summ
  from t
-- Строим дерево всех комбинаций чисел:
connect by prior num < num;
on-line проверка на sqlfiddle.com
18 дек 13, 10:19    [15309144]     Ответить | Цитировать Сообщить модератору
 Re: Возможно ли сделать все возможные суммы всех значений ?  [new]
Добрый Э - Эх
Guest
Добрый Э - Эх,

Упс, сорри. Попутал ветки форума. Почему-то показалось, что оракловую ветвь читаю.
Под ms sql решение будет чуть сложнее. Там как минимум придется использовать два рекурсивных СТЕ.
Счас набросаю пример и запощу...
18 дек 13, 10:22    [15309160]     Ответить | Цитировать Сообщить модератору
 Re: Возможно ли сделать все возможные суммы всех значений ?  [new]
Добрый Э - Эх
Guest
Что-то такое "родилось":
with
--
-- Тестовые данные (для примера три числа - 1,2,3):
  t (num) as 
    (
      select * from(values(1),(2),(3)) i(n)
    ),
--
-- Основная часть запроса:
--
-- Строим дерево всех комбинаций чисел:
  tree1 (num, path) as
    (
      select num, 
             cast(num as varchar(500)) as path from t
       union all
      select t1.num,
             cast(cast(t1.num  as varchar(500))+'+'+t0.path as varchar(500))
        from t t1
        join tree1 t0
          on t1.num > t0.num
    ),
--
-- "Пилим" дерево на ветки:
  tree2 (num, path) as
    (
      select num, path
        from tree1
      union all
      select t0.num, t1.path
        from tree1 t1
        join tree2 t0
          on substring(t1.path,nullif(charindex('+', t1.path),0)+1,500) = t0.path
    ),
--
-- Рассчитываем суммы всех возможных комбинаций чисел:
  main (str_sum, summ, cnt) as 
    (
      select path as str_sum,  -- комбинация суммируемых чисел
             sum(num) as summ, -- значение суммы чисел комбинации
             count(1) as cnt   -- кол-во элементов в сумме
        from tree2
       group by path
    )
--
-- Запрашиваем результат наших манипуляций:
select * 
  from main
 order by summ, len(str_sum);
on-line проверка на sqlfiddle.com
18 дек 13, 10:54    [15309400]     Ответить | Цитировать Сообщить модератору
 Re: Возможно ли сделать все возможные суммы всех значений ?  [new]
Добрый Э - Эх
Guest
Добрый Э - Эх,

что-то сейчас подумалось, что второй СТЕ таки не нужен. Суммы можно сразу просчитывать, при первом построении дерева.
19 дек 13, 05:39    [15314889]     Ответить | Цитировать Сообщить модератору
 Re: Возможно ли сделать все возможные суммы всех значений ?  [new]
Добрый Э - Эх
Guest
Добрый Э - Эх
что-то сейчас подумалось, что второй СТЕ таки не нужен. Суммы можно сразу просчитывать, при первом построении дерева.

Ну и как пример реализации:
with
--
-- Тестовые данные (для примера три числа - 1,2,3):
  t (num) as 
    (
      select * from(values(1),(2),(3)) i(n)
    ),
--
-- Основная часть запроса:
--
-- Строим дерево всех комбинаций чисел и рассчитываем их суммы:
  tree1 (num, sum_str, summ, cnt) as
    (
      select num, 
             cast(num as varchar(500)) as sum_str,
             num as summ,
             1 as cnt
        from t
       union all
      select t1.num,
             cast(cast(t1.num  as varchar(500))+'+'+t0.sum_str as varchar(500)),
             t1.num + t0.num,
             t0.cnt + 1
        from t t1
        join tree1 t0
          on t1.num > t0.num
    )
--
-- Запрашиваем результат наших манипуляций:
select * from tree1
on-line проверка на sqlfiddle.com
19 дек 13, 05:56    [15314896]     Ответить | Цитировать Сообщить модератору
 Re: Возможно ли сделать все возможные суммы всех значений ?  [new]
Mind
Member

Откуда: Лучший город на Земле
Сообщений: 2322
Добрый Э - Эх,

Супер! И достаточно быстро. Только одна ошибочка в сумме. Должно быть вот так:

with
--
-- Тестовые данные (для примера три числа - 1,2,3):
  t (num) as 
    (
      select * from(values(1),(2),(3)) i(n)
    ),
--
-- Основная часть запроса:
--
-- Строим дерево всех комбинаций чисел и рассчитываем их суммы:
  tree1 (num, sum_str, summ, cnt) as
    (
      select num, 
             cast(num as varchar(500)) as sum_str,
             num as summ,
             1 as cnt
        from t
       union all
      select t1.num,
             cast(cast(t1.num  as varchar(500))+'+'+t0.sum_str as varchar(500)),
             t1.num + t0.summ, --<<< summ
             t0.cnt + 1
        from t t1
        join tree1 t0
          on t1.num > t0.num
    )
--
-- Запрашиваем результат наших манипуляций:
select * from tree1
20 дек 13, 01:36    [15320888]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить