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

Question

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

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

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

Answer 1

Выбрать данные с группировкой по группам в сумму 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 перебирая все возможные комбинации, то можно по аналогии создать нужные коллеции и играться с ними.

БЛОГ НА HUSL

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

Ответы (1 шт):