Interesting practical mathematical problem

AI Thread Summary
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, each with a capacity of 4.7GB. The total size of the files is 25.62GB, indicating that at least six DVDs will be required, leaving some unused space. The problem is identified as a classical Bin-Packing Problem, which is NP-hard, meaning there is no guaranteed efficient algorithm for the worst-case scenario. A heuristic approach is suggested, which can often yield good results but may not always provide an optimal solution due to its anomalous behavior. The conversation highlights the complexity of the problem and the limitations of heuristic solutions in different scenarios.
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.
 

Hot Threads

Recent Insights

Back
Top