0

Есть таблица вида

введите сюда описание изображения

Необходимо сгруппировать строки так, что бы в каждой группе сумма cnt была максильно близка к 100, но не больше.

На выходе должна получится таблица вида. Строки разбиты по группа, и сумма cnt в каждой группе не больше 100. Можно использовать pl/sql, вспомогательные таблицы. Пока ни чего лучше перебора всех строк в цикле while не придумал(

введите сюда описание изображения

15
  • Пожалуйста, исправьте вопрос, чтобы он отражал конкретную проблему с достаточным количеством деталей для возможности дать адекватный ответ. Commented 21 мая в 12:13
  • 2
    Что понимается под группировкой? Добавьте в вопрос ожидаемый результат
    – SwaD
    Commented 21 мая в 12:35
  • Даже интересно, возможно ли такое чисто на SQL сделать. Подпишусь на комментарии )
    – CrazyElf
    Commented 21 мая в 13:30
  • Изменил описание. Не обязательно на чистом SQL. Функционал новый, ограничений особых нет Commented 21 мая в 13:36
  • сколько ожидается чисел на входе? а то на 9 числах ваш алгоритм может успевать за разумное время, а на 99 числах зависнет очень надолго
    – ESkri
    Commented 21 мая в 13:44

1 ответ 1

0

Выбрать данные с группировкой по группам в сумму 100 можно, допустим, вот таким образом:

DECLARE
  TYPE r_type IS RECORD(ID NUMBER, cnt NUMBER);
  TYPE t_type IS TABLE OF r_type;
  list_num t_type; -- Создаем коллекцию
  -- Всякие счетчики
  i NUMBER := 1;
  i_in NUMBER := 1;
  groupid NUMBER := 1; -- Номер начальной группы
  delta NUMBER := 0;

  -- Пишет строку в финальную таблицу и удаляет элемент из коллекции
  PROCEDURE upd_res_table(iid NUMBER, groupid NUMBER)
    IS
    BEGIN
      INSERT INTO swad_table_res (tid, cnt, grp)
      VALUES (list_num(iid).id, list_num(iid).cnt, groupid);
      list_num.delete(iid);
    END;
BEGIN
  list_num := t_type(); -- Инициализировали коллекцию

  FOR cur IN (SELECT * FROM swad_table ORDER BY cnt DESC) -- Сортируем по количеству вниз
    LOOP -- Тут наполняем ее
      list_num.extend;
      list_num(i).id := cur.tid;
      list_num(i).cnt := cur.cnt;
      i := i + 1;
    END LOOP;

  -- тут мы на 1м элементе коллекции i_in = 1

  WHILE TRUE
    LOOP
      delta := 100 - list_num(i_in).cnt; -- Считаем, сколько осталось
     

      upd_res_table(i_in, groupid); -- Пишем данные в таблицу
      i_in := list_num.NEXT(i_in); -- Берем следющий номер коллекции
      IF (i_in IS NULL) THEN -- Если i_in null выходим из цикла
        EXIT;
      END IF;

      WHILE TRUE
        LOOP
          IF (delta - list_num(i_in).cnt >= 0) THEN -- Если можно положить в группу, гладем
            delta := delta - list_num(i_in).cnt; -- меняем остаток
            upd_res_table(i_in, groupid); -- пишем
            IF (delta < 1) THEN -- Если остаток 0, выходим из цикла
              EXIT;
            END IF;
          END IF;
         
          i_in := list_num.NEXT(i_in); -- берем следующий элемент коллекции
          IF (i_in IS NULL) THEN -- если его нет, выходим
            EXIT;
          END IF;
        END LOOP; -- Законцили цикл по заполнению группы
      groupid := groupid + 1; -- Увеличиваем группу
      i_in := list_num.FIRST; -- Берем первый элемент коллекции
      IF (i_in IS NULL) THEN -- Если пусто, выходим
        EXIT;
      END IF;
    END LOOP;
END;

Время выполнения, у меня, на 100 строках, в среднем 0.008 - 0.013 с

DDL и DML таблиц

CREATE TABLE swad_table(
  tid NUMBER,
  cnt NUMBER
);
/
CREATE TABLE swad_table_res(
  tid NUMBER,
  cnt NUMBER,
  grp NUMBER
);
/
DECLARE
 mx NUMBER;
BEGIN
  SELECT NVL(MAX(tID), 0) INTO mx FROM swad_table;
  FOR x IN 1..100 LOOP
    INSERT INTO swad_table VALUES(mx + x,ROUND(dbms_random.value(1, 100)));
  END LOOP;
END;
/

--SELECT * FROM swad_table;
--SELECT * FROM swad_table_res;
--TRUNCATE TABLE swad_table;
--TRUNCATE TABLE swad_table_res

В первом варианте скрипта было 2 коллекции. Вторая результирующая наполнялась, а потом был insert в физическую таблицу.

Если расширять алгоритм и как то пытаться в пачку воткнуть близкое к 100 перебирая все возможные комбинации, то можно по аналогии создать нужные коллеции и играться с ними.

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.