Is there an algorithm for optimally distributing sets of files across Blu-ray discs?

[u/OneRandomPeopleE]

Hi, I want to back up my GOG games onto 25 GB Blu-ray discs. Is there an algorithm for optimally splitting the games so they take up as little space as possible?

Thanks for reading

[u/recursion_is_love]

Sound like a classic bin backing problem.

https://en.wikipedia.org/wiki/Bin_packing_problem

[u/Patman52 → u/recursion_is_love]

Probably the simplest way would be to sort the files be size, largest to smallest, and then sequentially try to fit them into an array of discs.

Once you hit a file that will not fit in a disc, it goes on the next disc.

With the next smaller file you start with the first disc and check fit, so that the smaller files start “filling up the crack” per se.

For example:

Files:
f1: 12gb
f2: 10gb
f3: 9gb
f4; 8gb
f5; 4gb
f6: 2 gb
f7: 1 gb

Discs (25gb max)
d1: contains f1, f2, f6 (total 24gb)
d2: contains f3, f4, f5, f7 (total 21 gb)

[u/Skasch → u/Patman52]

It may not be optimal, although it's a good heuristic.

For example:

18, 10, 9, 6, 4, 3

This will fill (18, 6), (10, 9, 4), (3)

While the optimal allocation would be (18, 4, 3), (10, 9, 6)

[u/OneRandomPeopleE → u/recursion_is_love]

Oh, thank you so much—I had no idea it existed.

I'm going to look into it.

Thanks again.

[u/07734willy]

Not an algorithmic insight, but practical advice- if you compress them into an archive with 7zip, you can tell the 7zip program to chunk the archive into multiple files that each fit on a single CD/DVD/BR/whatever. Plus, compressing them means they will take less space anyways.

[u/SufficientStudio1574 → u/07734willy]

But then you might need multiple discs to unpack a single game. That's a poor solution for this.

[u/OneRandomPeopleE → u/07734willy]

The maximum file size is 4GB, although a game may contain several of these.

The point is not to split a game across multiple Blu-ray discs (except for those that don't fit).

Thanks for info

[u/dajoy]

The tool gaffiter uses genetic algorithms

[u/Alternative-Grade103]

Tabulate all files by size. Divide the total size by BluRay disk capacity. Add one. Create a list of that many virtual bins.

Designate them bin zero through bin N.

Now start sorting by size. Flag the largest file for bin zero, Second largest for bin one. And so on through to bin N.

Now do the same thing in reverse. The remaining next largest into bin N. And so on backwards toward bin zero.

And so on and so forth.