Best fit algo
-
Hi, All of you must have herd of Best fit also, but i would give a brief , just in case. Say i have slots of 50 KB, and there are some codes of different sizes say [10KB,11KB,23KB,34KB,2KB,28KB,31KB,9KB] Now i have to fit all the elements in the different 50KB Slots such that i make the optimum use of the space. Like: 31+9+10 = 50KB --- 1st slot. 11+34 = 45KB --- 2nd slot... I need an algo for the same in C#.. Thanks in advance...
-
Hi, All of you must have herd of Best fit also, but i would give a brief , just in case. Say i have slots of 50 KB, and there are some codes of different sizes say [10KB,11KB,23KB,34KB,2KB,28KB,31KB,9KB] Now i have to fit all the elements in the different 50KB Slots such that i make the optimum use of the space. Like: 31+9+10 = 50KB --- 1st slot. 11+34 = 45KB --- 2nd slot... I need an algo for the same in C#.. Thanks in advance...
-
Hi, All of you must have herd of Best fit also, but i would give a brief , just in case. Say i have slots of 50 KB, and there are some codes of different sizes say [10KB,11KB,23KB,34KB,2KB,28KB,31KB,9KB] Now i have to fit all the elements in the different 50KB Slots such that i make the optimum use of the space. Like: 31+9+10 = 50KB --- 1st slot. 11+34 = 45KB --- 2nd slot... I need an algo for the same in C#.. Thanks in advance...
You don't define "best fit" based on your needs (i.e. largest first, most-used first, etc) but, based on your example, I'll assume you need a solution to what is called a "bin packing problem" (see google.com). A bin-packing problem solves the problem of fitting different-sized objects (data) into a number of specifically-sized containers without being able to split objects between containers. The solution you choose will depend on your requirements. The optimum solution (the absolute best possible fit) is computationally complex with longer execution times. A "good enough" solution will be simpler and will likely run in the amount of time you need to complete the task. Here are some of the simpler solutions: 1. First Fit Decreasing - Sort the items (largest first), then place each item in the first container it will fit in. 2. Best Fit Decreasing - Sort the items (largest first), then place each item in the container that leaves the least room left over (tightest fit). With these two algorithms, you should need no more than ~120% + 1 more containers than the optimal solution. If you don't sort the items first, I think you need 170% + 1 (or 2?) more containers than the optimum solution. Best solutions depend on how big the items are in relation to your container (lots of little items in large container or larger items in "close fit" containers) and how much the item sizes and container sizes vary. Then you have to worry about whether you will be adding and removing items on an on-going basis (fragmentation occurs) or if you can move data once it is placed in a container (optimization). For a start, see if "Best Fit Decreasing" works in your case. It's pretty easy to implement, assuming I even have your problem defined correctly. Robert C. Cartaino