Interesting practical mathematical problem

Click For Summary

Homework Help Overview

The discussion revolves around a practical mathematical problem involving the arrangement of 14 files of varying sizes to minimize the number of DVD discs used for burning, with each disc having a capacity of 4.7GB.

Discussion Character

  • Exploratory, Assumption checking, Problem interpretation

Approaches and Questions Raised

  • Participants discuss strategies for selecting files to maximize disc usage without exceeding capacity. Some mention the classical Bin-Packing Problem and its complexity, while others suggest heuristic methods for practical solutions.

Discussion Status

There is an ongoing exploration of different strategies, with some participants providing heuristic suggestions and others expressing confusion about the complexity of the problem. No consensus has been reached on a definitive solution.

Contextual Notes

Participants note the total size of the files and the minimum number of discs required, while also discussing the implications of the NP-hard classification of the problem. Some express difficulty in understanding the technical terminology used in the discussion.

kenny1999
Messages
235
Reaction score
5

Homework Statement



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



Homework Equations





The Attempt at a Solution

 
Physics news on Phys.org
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.
 
kenny1999 said:

Homework Statement



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



Homework Equations





The Attempt at a Solution


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
 
Compress the files and make volumes of size that fill the disks exactly.
 
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).
 
Ray Vickson said:
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

i don't understand any sentences of above. can you give me a solution to my problem
 
rcgldr said:
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).

Great solution. I'll try
 
kenny1999 said:
i don't understand any sentences of above. can you give me a solution to my problem

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
 
Ray Vickson said:
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?

lol quite possibly every relevant word in those sentences.