I'm dividing up an animation project among 20 students. The whole film is 4955 frames long, so each student should have as close to 248 frames as possible. However, the scenes have an unequal number of frames that cannot be changed, and each student must have a whole scene (nobody can have .45 of a scene.) What is the easiest way to divide these scenes up to make sure each student gets as close to 248 frames as possible?
The original number of frames you have is 4955 frames and every student should receive as close to equal amount of frames as possible, the following is a solution I would suggest:
4955 frames / 20 students = 247.75
we take 247 (floor) and 248 (ceiling) as the possible number of frames that each student can get, now to figure out how many of those students should get 248 (the rest will get 247):
4955 mod 20 = 15
15 students will receive 248 frames and 5 will receive 247 frames
This works because .75 is 15/20 which therefore means 15 out of 20 got the ceiling value of the original division and the rest got the floor to equalise to .75
First define the function you want to minimise: Let A = number of frames divided by number of students, this is how many frames each student should get (but most likely not an integer).
Then if a student has $S_i$ frames, count that as a deviation of $|S_i - A|^k$ for k = 2 or 3 for example and optimise the sum of all deviations; if you choose k large then the optimum will avoid students being outliers.
A workable algorithm: Sort the scenes by number of frames in descending order. Take the scenes in turns and assign each of them to the student who currently has the lowest number of frames.
Then find two scenes that could be swapped to improve the total deviation, repeat until there is no swap improving the outcome.