Skip records while performing SUM() window function in oracle SQL

user_15188293 0
Viewed 84

I have a scenario, there is an escalator with 1000 lbs capacity. The total no of persons weight entering the escalator should not exceed 1000 lbs .LINE table contains persons name,weight and turn in the queue.

Below is the table syntax and values in it

create table line (id int not null PRIMARY KEY,
name varchar(255) not null,
weight int not null,
turn int unique not null,
check (weight > 0)
);

INSERT INTO LINE VALUES(6,'George Washington', 250, 1);
INSERT INTO LINE VALUES(5,'Thomas Jefferson',175, 7);
INSERT INTO LINE VALUES(3,'John Adams',350, 2);
INSERT INTO LINE VALUES(7,'Thomas Jefferson',800, 3);
INSERT INTO LINE VALUES(1,'James Elephant',500, 6);
INSERT INTO LINE VALUES(2,'Andy',200, 5);
INSERT INTO LINE VALUES(4,'Will Smith',400, 4);

Now i need to write a query to print last person name who enters the lift .Means, with the last person, lift capacity will be filled. Priority should be given based on TURN value i.e 1st person should be given 1st priority and 2nd person 2nd priority and so on. Sum of first 2 persons weight in turn is 600 ,if next person(Thomas Jefferson,Weight-800) enters the escalator,it exceeds escalator capacity .So, this person should be ignored/excluded and add next person(Will Smith,Weight-400) to the escalator .Now ,the sum of all persons weight is 1000 ,there by ,Will Smith name should be displayed in the output.

Could you please guide me to write SQL query for this.

PS:This is my first post. Kindly ignore in case of errors.

SQL fiddle link

oracle sql
1 Answers

You are solving kind of optimization task similar to knapsack problem except - luckily - in your case the greedy traversal suffices. You need recursive query. In each iteration one turn is processed and it is decided if new last person on elevator is the previous one or the new one (please uncomment select * for clear understanding). The name of last person in CTE is what you look for. (For simplicity I assumed turns are contiguous sequence from 1.)

with actual_elevator (name, last_turn, total) as (
  select name, turn, weight from line where turn = 1 and weight <= 1000
  union all
  select case when r.total + l.weight <= 1000 then l.name else r.name end
       , l.turn
       , case when r.total + l.weight <= 1000 then r.total + l.weight else r.total end
  from actual_elevator r
  join line l on r.last_turn + 1 = l.turn
  where r.total < 1000 -- UPDATE 1
)
--select * from actual_elevator
select name from actual_elevator where last_turn = (select max(turn) from line)

Modified fiddle. I have to praise you for preparing fiddle, specifying db vendor and description of problem for concrete case. Not everyone asking [sql] questions on SO is so diligent.

UPDATE1: To stop iteration when sum is exactly 1000, use where condition to stop testing any new rows once the limit is reached (modified fiddle).

Note that when sum is less than 1000, the iteration must run to end because you never know the suitable value is say on last row until you see it.

Also note that algorithm greedily finds suboptimal solution. For example for input 800,100,200 it stops at 900 and does not backtrack to find 1000 or maximum. This would be quite different and more diffucult task which I assume you didn't required.

user_6535390
Related