1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Interesting practical mathematical problem

  1. Apr 16, 2012 #1
    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. jcsd
  3. Apr 16, 2012 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
  4. Apr 16, 2012 #3

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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
     
  5. Apr 16, 2012 #4
    Compress the files and make volumes of size that fill the disks exactly.
     
  6. Apr 16, 2012 #5

    rcgldr

    User Avatar
    Homework Helper

    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).
     
  7. Apr 16, 2012 #6
    i don't understand any sentences of above. can you give me a solution to my problem
     
  8. Apr 16, 2012 #7
    Great solution. I'll try
     
  9. Apr 16, 2012 #8

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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
     
  10. Apr 16, 2012 #9

    Mentallic

    User Avatar
    Homework Helper

    lol quite possibly every relevant word in those sentences.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Interesting practical mathematical problem
  1. SAT practice problem (Replies: 5)

  2. Interesting Problem (Replies: 1)

Loading...