Interesting practical mathematical problem

In summary, the conversation discussed a practical mathematical problem of arranging 14 files of different sizes onto DVD discs to minimize the use of discs. Different solutions were suggested, including a heuristic approach which may not always produce the optimal solution, and a solution of compressing the files to fit exactly onto the discs. It was also mentioned that this problem, known as the Bin-Packing Problem, is NP-hard and has no known algorithm for solving it in the worst case.
  • #1
kenny1999
235
4

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
  • #2
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
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
 
  • #4
Compress the files and make volumes of size that fill the disks exactly.
 
  • #5
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
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
 
  • #7
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
 
  • #8
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
 
  • #9
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.
 

Related to Interesting practical mathematical problem

1. What is an interesting practical mathematical problem?

An interesting practical mathematical problem is a real-world problem that can be solved using mathematical concepts and techniques. These problems often have practical applications and can be found in various fields, such as engineering, economics, and physics.

2. How do you approach solving an interesting practical mathematical problem?

The first step in solving an interesting practical mathematical problem is to clearly define the problem and gather all relevant information. Then, you can use mathematical tools and techniques, such as equations, formulas, and data analysis, to find a solution. It's also helpful to break down the problem into smaller, more manageable parts.

3. Why are interesting practical mathematical problems important?

Interesting practical mathematical problems help us understand and solve real-world issues and challenges. They also improve our critical thinking, problem-solving, and analytical skills. Additionally, many advancements in science and technology have been made possible through the solution of interesting practical mathematical problems.

4. Can anyone solve an interesting practical mathematical problem?

Anyone with basic mathematical knowledge and problem-solving skills can attempt to solve an interesting practical mathematical problem. However, some problems may require more advanced mathematical concepts and techniques, and it may be helpful to seek assistance from a mathematician or expert in the specific field.

5. How can I find interesting practical mathematical problems to solve?

There are many resources available for finding interesting practical mathematical problems, such as textbooks, online databases, and scientific journals. You can also create your own problems by observing and analyzing real-world situations and identifying the mathematical concepts and techniques that can be applied.

Hot Threads

Recent Insights

Back
Top