Win a copy of TensorFlow 2.0 in Action this week in the Artificial Intelligence and Machine Learning forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Paul Clapham
  • Bear Bibeault
  • Jeanne Boyarsky
Sheriffs:
  • Ron McLeod
  • Tim Cooke
  • Devaka Cooray
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Jj Roberts
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • salvin francis
  • Scott Selikoff
  • fred rosenberger

Best Fit Algorithm

 
Ranch Hand
Posts: 74
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,
My problem is as follows:
I have a bunch of files that I would like to copy to a CD. The total size of these files let's say needs four to five CD's, depending on the way that you arrange the files. I need an algorithm that takes the sized of these files, and distribute them on the Maximum capacity of each CD, in a way to utilize the space of each CD.

Example:
Let's say a CD can contain 20 MB.
items:
(A) 10
(B) 5
(C) 4
(D) 3
(E) 2

if you sort the files based on their size - like above - most likely you'll choose the files as follows:
(A) 10, (B) 5, (C) 4, the total will be 19 MB and there will be 1 MB unused.

However, if you replace (C) with (D) and (E), you'll fill the remaining unused space efficiently.

Of course, this example is very easy to solve manually with a glance. But in case of more complicated scenarios with many files with different sizes, that task will be much harder.

So, any help?
 
author
Posts: 23887
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How about just a brute force recursive algorithm? You can try out every possible combination (done recursively), and then save the ones that uses the least amount of CDs.

Henry
 
Nadeem Awad
Ranch Hand
Posts: 74
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Originally posted by Henry Wong:
How about just a brute force recursive algorithm? You can try out every possible combination (done recursively), and then save the ones that uses the least amount of CDs.

Henry



Don't you think that this might take a huge amount of time? Especially in a scenario that we have - let's say - a 13 GB of data that I want to distribute over three (4.6 GB) DVD's.
 
Rancher
Posts: 43016
76
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, you hadn't told us how many items there were. If it's really 5MB-sized items then there may indeed be too many for an exhaustive approach.

The bin packing problem -of which this is an instance- is NP-hard, so no fast, accurate algorithms to solve it are available. Wikipedia: Bin packing problem mentions a couple of heuristical approaches that should be feasible, although likely sub-optimal.
[ February 05, 2008: Message edited by: Ulf Dittmer ]
 
Henry Wong
author
Posts: 23887
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Don't you think that this might take a huge amount of time? Especially in a scenario that we have - let's say - a 13 GB of data that I want to distribute over three (4.6 GB) DVD's.



What are these one byte files? And even if they were one megabyte files, why would you need this? What does it matter if you have a one megabyte of unused disk space in a 4.6 gigabyte disk?


Anyway, here is another recommendation.... separate the files based on size. Try different cut-offs like 10 meg, 50 meg, 100 meg, etc.

Use the brute force recursive algorithm on the bigger files. Pick one of the many solutions with the least disks -- odds are there will be many solutions with the smallest amount of disks.

Optionally sort the smaller files based on size. And then place the small files into the unused areas -- going to a new disk only if a file doesn't fit into any of the current disks. If you insert the largest of the small files first, then the maximum unused space should be the smallest of the small files.


Will this give you a perfect solution? Probably not, but I don't see how it may fail. And remember, you have two requirements here -- the other one is a time constraint. You need to solve both problems.

Henry
 
Nadeem Awad
Ranch Hand
Posts: 74
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Originally posted by Henry Wong:


What are these one byte files? And even if they were one megabyte files, why would you need this? What does it matter if you have a one megabyte of unused disk space in a 4.6 gigabyte disk?

Henry



I didn't understand what one byte files are you talking about.

Anyway, I found what I've been looking for. It's a well-known problem called Bin Packing Problem. I've found many solution for it in the Source Forge as well.

Thanks a lot.
 
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hello ,
i want to find best fit algorithm's steps. it's very very important for my case study at Univ. i searched a lot but i could't find at internet . can anyone help me?
 
Ulf Dittmer
Rancher
Posts: 43016
76
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What terms did you google? "best fit algorithm" seems a promising one.
 
dilsad yalcin
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Ulf Dittmer wrote:What terms did you google? "best fit algorithm" seems a promising one.



ofcourse i used "best fit algorithm" but it must be acedemic explanation and step to step like articles in Science Direct website , but i can't use that website
 
Ulf Dittmer
Rancher
Posts: 43016
76
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The first result I get for that search phrase leads to an article on developerfusion.com, which includes source code. You can't get more step-by-step than that. Of course, it relates to "bin packing", which is what this topic is all about. If you're talking about "best fit" in some other context, you should mention that.
 
I didn't say it. I'm just telling you what this tiny ad said.
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
reply
    Bookmark Topic Watch Topic
  • New Topic