# Interesting practical mathematical problem

1. Apr 16, 2012

### kenny1999

1. The problem statement, all variables and given/known data

Hello, I now have a real practical mathematical problem to ask

I have 14 files with different sizes to be burnt on DVD discs. Each DVD disc is 4.7GB. How to arrange the files so as to minimize the use of discs?

The file sizes of the 14 files are

1) 2.25GB
2) 2.25GB
3) 1.15GB
4) 3.05GB
5) 1.16GB
6) 2.40GB
7) 0.6GB
8) 2.05GB
9) 1.36GB
10) 1.97GB
11) 1.11GB
12) 1.14GB
13) 2.48GB
14) 2.65GB

2. Relevant equations

3. The attempt at a solution

2. Apr 16, 2012

### HallsofIvy

Staff Emeritus
Pretty straight forward. Choose files to come as close to 4.7 GB as you can, without going over. Those will go on one disc. The choose files from the rest to come as close 4.7 GV without going over. Continue until you have dealt with all the discs.

3. Apr 16, 2012

### Ray Vickson

This is the classical Bin-Packing Problem, and is known to be NP-hard, which means that there is no known good algorithm for solving it in the worst case. The solution suggested by HallsofIvy is a heuristic that often works pretty well in practical problems, but is not guaranteed in general to produce the optimal solution. It, and many similar heuristics, have a property of "anomalous" behaviour, which means that they can produce solutions in which (1) adding files needs fewer disks; (2) removing some files needs more disks; (3) increasing some of the file sizes requires fewer disks; (4) decreasing some of the file sizes requires more disks. Of course, that cannot happen for the optimal policy.

There is a vast literature devoted to bin packing, and a large literature dealing with the type of bin-packing anomalies I outlined above---including worst case bounds and the like.

RGV

4. Apr 16, 2012

### Dickfore

Compress the files and make volumes of size that fill the disks exactly.

5. Apr 16, 2012

### rcgldr

Total size of the files is 25.62GB, so that requires a minimum of 6 dvd's, with 2.58gb of unused space. In this case your algorithm doesn't have to be that complex, any solution that takes 6 dvd's will be good enough. Any combination of files that totals 4.27GB to 4.7GB per dvd will work. (Note, 4.27 = 4.7 - 2.58/6).

6. Apr 16, 2012

### kenny1999

i don't understand any sentences of above. can you give me a solution to my problem

7. Apr 16, 2012

### kenny1999

Great solution. I'll try

8. Apr 16, 2012

### Ray Vickson

What part of the sentence "This is the classical Bin-Packing Problem, and is known to be NP-hard, which means that there is no known good algorithm for solving it in the worst case" did you not understand? What part of the sentence "The solution suggested by HallsofIvy is a heuristic that often works pretty well in practical problems, but is not guaranteed in general to produce the optimal solution" do you not understand? The rest of the posting just gives some weird properties of heuristic solutions that are quite hard to believe at first, but are well-known in the field.

The point of the post is: you may be able to sometimes solve specific cases (such as yours), but if I gave you another problem with different numbers you might not be---there are no guarantees.

RGV

9. Apr 16, 2012

### Mentallic

lol quite possibly every relevant word in those sentences.