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?

  • 1
    $\begingroup$ Sounds like the partition problem. Could you please clarify the differences? $\endgroup$ – xskxzr Oct 29 '19 at 3:00
  • $\begingroup$ Can you quantify "as close to 248 frames as possible"? What objective function are you trying to minimize? $\endgroup$ – Yuval Filmus Oct 29 '19 at 10:24

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

  • $\begingroup$ You missed the requirement that each student must receive one or more complete scenes. $\endgroup$ – gnasher729 Nov 28 '19 at 23:21
  • $\begingroup$ By complete scenes if you mean 248 frames, that's not possible, don't get confused by my fractions, they're just a means to figure out how many people should get 248 frames and how many should get 247 since 4955/20 is 247.75 which is not possible, you either do or do not get that frame. Your solution will also end up with people getting less than 248 frames since it relies on them creating less frames which is not an assumption I was willing to make. I took this question in the more programmatic way of splitting the load as equally as possible with no prior assumptions $\endgroup$ – Dan Nov 29 '19 at 8:54

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.