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...
The best fit is a rather lengthy algorithm to implement. I would try sorting in descending order before trying to assign bins. Then you'll have to loop through all the bins and assign as appropriate. You also have the possibility of increasing the numbers of bins. Assign elements to the bin that is most full that can accomodate your element. At this point you can increase the number of bins if you like. Continue in this manner....
-
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...
This is a standard Multiple Knapsack[^] problem, there are lots of references on the web and a variety of solution trchniques with different ranges of applicability. One general code (fortran though, not c#) is TOMS ALgortihm 632[^]
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
-
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 are probably going to have to live with an imperfect solution. This looks a lot like subset-sum, which iirc is an NP hard problem ;)
Mark Churchill Director Dunn & Churchill Free Download:
Diamond Binding: The simple, powerful, reliable, and effective data layer toolkit for Visual Studio. -
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...
Hello, Best Fit problem as applies to computer science involves variable size storage blocks as well as variable size data to be put into the storage blocks notably without combining data chunks before storage (see Knuth, Vol. I). What you have described is the timeworn knapsack problem, aka circus train problem. Simply stated: What is the packaging arrangement of a fixed set of variably sized objects into uniform size containers that fills the fewest containers? Problem size will be a considerable obstacle here. Consider unfavorable size distributions in your set of variables that yield many size combinations to be generated, tested, and compared with the previous-best combination. And how many possible combinations of these combinations are possible? Anyway, I think you should postulate some modest inputs and do some pencil scratch before hunting down code or algorithm.
Tadeusz Westawic An ounce of Clever is worth a pound of Experience.