Your mission is to build an algorithm (program or function) that can optimize packing fruit from a conveyor belt into bags to be sent off to retailers, optimizing for a largest number of bags.
Each bag has to weight at least a certain amount, but any excess is lost profit since that weight could be used to fill another bag. Your bagging machine has always a lookahead of
n fruits from the queue and may only choose to add any of these
n fruits to the (single) bag that is being processed. It cannot look beyond the
n first elements in the queue. The program always knows exactly how much weight there already is in the bag.
Another way to visualize this is having a conveyor belt with a loading area of size
n at the end, from where a fruit has to be taken before a new fruit arrives. Any leftover fruit and a non-full bag at the end are discarded.
- List/array of weights of fruits in queue (positive integers)
- Minimum total weight for bags (positive integer)
Your algorithm should return for all bags the weights of the fruits in them, by whatever means is convenient for you and your language, be that stdin or a return value or something else. You should be able to run the program and calculate your score in one minute on your computer.
Total weight 1000, lookahead of 3 and fruit queue:
One possible output (indented to show how the lookahead affects the bagging):
[171,163,172, 156,175, 176]
[162, 155,182,189, 161,160]
Your algorithm will be tested on six runs on a batch of 10000 oranges I have prepared for you, on lookaheads ranging from 2 to 7, inclusive on both ends. You shall pack them into bags weighing at least 1000 units. The oranges are normally distributed with a mean weight of 170 and a standard deviation of 13, if that is of any help.
Your score will be the sum of number of bags from the six runs. The highest score wins. Standard loopholes are disallowed.