473,402 Members | 2,064 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,402 software developers and data experts.

best fit algorithm

I'm new to programming and need some help figuring out an algorithm.

I need to design some kind of algorithm which will help us define capacity for one of our portfolios....here's the problem explained (also see attached example):

1. The graph defines total capacity, y-axis being $, x-axis being date/time. the bars on the graph represent individual items.

2. What I need to do is place the items on the graph in an optimized manner, minimizing wastage of space. I can break the items vertically but can't break them up horizontally. The goal is to leave as much free space as possible for bigger horizonal items.

3. Items can't overlap each other.

4. See example, I'm currently doing in Access....my procedure takes too long to run and results in overlapped data.

I was wondering there has to be some standard algorithm to do this kind of thing....any ideas would be appreciated....Thanks!


take some hints:

iam creat the file by this code

Expand|Select|Wrap|Line Numbers
  1.     import java.awt.*;
  3.    import javax.swing.*;
  5.    import java.lang.SecurityException;
  7.    import java.util.*;       
  8.    import java.util.Formatter;               
  9.    import java.util.FormatterClosedException;
  10.    import java.util.NoSuchElementException;  
  11.    import java.util.Scanner;  
  13.    import java.io.*;
  14.    import java.io.FileNotFoundException;     
  15.    import java.io.InputStream;
  16.    import java.io.OutputStream;
  17.    import java.io.FileInputStream;
  18.    import java.io.FileOutputStream;
  19.    import java.io.FileReader;
  20.    import java.io.FileNotFoundException;               
  22.   public class FittingAllgorithm
  23.  {
  24.       int memory,dummycount;
  25.      int process;
  26.      int[] bestfit,worstfit,nextfit,firstfit;
  30.      private Formatter output1; // object used to output text to file
  32.      // enable user to open file
  33.      public void openFile()
  34.      {
  35.         try
  36.         {
  37.            output1 = new Formatter( "memory.txt" );
  38.         } // end try
  39.         catch ( SecurityException securityException )
  40.        {
  41.           System.err.println(
  42.               "You do not have write access to this file." );
  43.            System.exit( 1 );
  44.         } // end catch
  45.         catch ( FileNotFoundException filesNotFoundException )
  46.         {
  47.            System.err.println( "Error creating file." );
  48.            System.exit( 1 );
  49.         } // end catch
  50.      } // end method openFile
  52.      // add records to file
  53.      public void addRecords()
  54.      {
  55.         // object to be written to file
  56.         Job record = new Job();
  58.         Scanner input = new Scanner( System.in );
  60.        System.out.printf( 
  61.        "%s\n%s\n%s\n%s\n%s\n","********************\n\nFitting Algorithem\n\n********************\n\nThis Create By\n",
  62.        "Khalid Ahmed Almallahy\n20032348\n\n********************\n",
  63.        "Supervesor by",
  64.        "\nMoamar Elyazgi.\n\n********************\n\n",
  65.        "Hint :- \n When You Wont to Exit Press <CTRL>+z\n\n========================================================\n\n" );
  67.         System.out.printf( "%s\n%s\n",
  68.            "Enter First Jop 'Process' number must be greater than 0\n  Second Job 'Process'\n  Third Job 'Process'\n  last Job 'Process'",
  69.            "?" );
  71.        while ( input.hasNext() ) // loop until end-of-file indicator
  72.         {
  73.            try // output values to file
  74.            {
  75.               // retrieve data to be output
  76.               record.setAccount ( input.nextInt() ); 
  77.               record.setaccount1( input.nextInt() );    
  78.               record.setaccount2( input.nextInt() );       
  79.               record.setaccount3( input.nextInt() );     
  81.               if ( record.getAccount() > 0 )
  82.               {
  83.                  // write new record
  84.                  output1.format( "%d %d %d %d \n", 
  85.                     record.getAccount(),
  86.                     record.getaccount1(),
  87.                     record.getaccount2(),       
  88.                     record.getaccount3() );                             
  89.               } // end if
  90.               else
  91.               {
  92.                  System.out.println(
  93.                     "Job number must be greater than 0." );
  94.               } // end else
  95.            } // end try
  96.            catch ( FormatterClosedException formatterClosedException )
  97.            {
  98.               System.err.println( "Error writing to file." );
  99.               return;
  100.            } // end catch
  101.            catch ( NoSuchElementException elementException )
  102.            {
  103.               System.err.println( "Invalid input. Please try again." );
  104.               input.nextLine(); // discard input so user can try again
  105.            } // end catch
  107.           System.out.printf( "%s %s\n%s", "\nEnter First Job'Process' number greater than 0,",
  108.               "\nSecond Job 'Process', \nTherd  Job 'Process' \nand So on..", "?\n" );
  110.         } // end while
  111.      } // end method addRecords
  112.      // close file
  113.     public void closeFile()
  114.      {
  115.         if ( output1 != null )
  116.            output1.close();
  117.      } // end method closeFile
  119.      public void firstfit()
  120.      {
  122.       Job record = new Job();
  123.       Scanner input = new Scanner( System.in );
  125.      }
  128.     public static void main( String args[] ) throws FileNotFoundException
  129.      {
  130.          FittingAllgorithm application = new FittingAllgorithm();
  132.         application.openFile();
  133.         application.addRecords();
  134.         application.firstfit();
  135.         //application.worstfit();
  136.         //application.bestfit();
  137.         application.closeFile();
  138.      } // end main
  139.   } // end class CreateTextFile
  142.   /////////////////
  144.   and this one
  147.   public class Job
  148.   {
  149.       private int account;
  150.       private int account1;
  151.       private int account2;
  152.       private int account3;
  154.      public Job()
  155.      {
  156.         // constructor
  157.      } 
  160.      public Job( int acct, int account11, int  account22, int account33 )
  161.      {
  162.         setAccount( acct );
  163.         setaccount1( account11 );
  164.         setaccount2( account22 );
  165.         setaccount3( account33 );
  166.      }
  169.      public void setAccount( int acct )
  170.      {
  171.         account = acct;
  172.      } 
  175.      public int getAccount()
  176.     {
  177.         return account;
  178.      }
  181.      public void setaccount1( int account11 )
  182.      {
  183.         account1 = account11;
  184.      }
  187.      public int getaccount1()
  188.      {
  189.         return account1;
  190.      } 
  192.      public void setaccount2( int account22 )
  193.      {
  194.         account2 = account22;
  195.      } 
  198.      public int  getaccount2()
  199.      {
  200.         return account2;
  201.      }
  204.      public void setaccount3( int account33 )
  205.      {
  206.         account3 = account33;
  207.      } 
  210.      public int getaccount3()
  211.      {
  212.         return account3;
  213.     } 
  214.   } 
  217. /////////////////////
but the problem is how can i division the memory text, the memory text i created but i cannot division it
i wont to division it in to 7 parts each part have 20kb
how can i write this code
if there any one helpe me or any one can write code to division this problem

so i wont to enter number to saved it on the memory text
the memory text have 140kb division into 7 parts each part have 20kb
this is my proble

place help me by wite a code ...

i wont to division the memory into 7 parts each part have 20kb so the memory have 140kb , then i wont to enter the nuber into the memory text we must search the hole on the memory that is
empty to enter the number and put it in this hole
there r many algorithem to insert and search the hole but i wont to use the first , best, worst fit algorithems
how can i use this fitting by using this code

hint :::

Satisfy request of size n from list of free holes – four basic methods:
First-fit: Allocate the first hole that is big enough.
Best-fit: Allocate the smallest hole that is big enough; must search entire list, unless ordered by size. Produces the smallest leftover hole.
Worst-fit: Allocate the largest hole; must also search entire list. Produces the largest leftover hole.

help me
Oct 17 '07 #1
6 17792
11,448 Expert 8TB
I was wondering there has to be some standard algorithm to do this kind of thing....any ideas would be appreciated....Thanks!
Hi, nice to see you back; your problem is a difficult problem to solve; here are
some thoughts about it:

A 'job' has a start time, a time length and a memory requirement. We can describe
it as J(s, t, m). If we do know all parameters s, t and m in advance the problem is
a two dimensional bin packing problem (loosely put: try to fit all those blocks in
the two dimensional TxM rectangle where T is time and M is memory requirement.

This problem is nasty as it is and needs sophisticated (integer) linear solvers
such as iLog's CPlex simplex and interior point plus branch and bound solvers.
Don't take this lightly; it's not stuff for a beginner (no insult intended).

If we *don't* know parameter 's' in advance we're dealing with JIT planning (JIT ==
Just In Time) and there's not much more we can do than indeed apply a simple
first- next- best- or worst fit w.r.t. the memory requirement 'm'; parameter 't' is
fixed so we can't fiddle with that.

I do hope that you're dealing with the second variant because the first variant
takes a lot of processing power and nifty heuristics when if comes to cost factors
if all the requirements are *not* met.

kind regards,

Oct 17 '07 #2
11,448 Expert 8TB
ps. when it comes to those 'fit'algorithms: Donald Knuth already showed in the
'70s that it doesn't matter much: simply takes the simplest algorithm.

kind regards,

Oct 17 '07 #3
13,262 8TB
ps. when it comes to those 'fit'algorithms: Donald Knuth already showed in the
'70s that it doesn't matter much: simply takes the simplest algorithm.

kind regards,

@OP: Revised Simplex algorithm program is not too difficult to make so there is some hope.

@Jos How far would the Nelder Mead method go here? Could it better here than the simplex

P.S Copied to challenges forum
Oct 17 '07 #4
11,448 Expert 8TB
@OP: Revised Simplex algorithm program is not too difficult to make so there is some hope.
<slashing down all hope/> The simple method or an interior point method can just
give an answer on the 'integer relaxation'. After that you have to apply an nasty
'branch and bound' method that are real show stoppers when the number of
integer variables is large; and in this problem this number can be quite large.

@Jos How far would the Nelder Mead method go here? Could it better here than the simplex

P.S Copied to challenges forum
Nope sorry; it won't be of much use as far as I can tell for now ;-)

kind regards,


ps. I bet this thing will stay unanswered for a long time in the 'Challenges' forum ;-)
Oct 17 '07 #5
for non solve my problem
Oct 17 '07 #6
11,448 Expert 8TB
for non solve my problem

kind regards,

Oct 17 '07 #7

Sign in to post your reply or Sign up for a free account.

Similar topics

by: QQ | last post by:
Hello I have a integer range Now I have another integer range ai,bi =0,1,....,M I wanna compare the relationship between the two ranges for example = = so there are 9 situations
by: Daniel Reber | last post by:
I am looking to populate classes (I will have two types of classes, dimensions & facts) in c# with flat data from a summarized dataset. Based on what the user wants I will create a hierarchy of...
by: Bob | last post by:
It's not especially important, but I always like to know the best way of doing things for when I encounter a case where performance becomes a factor... say I have a string array and I want to get a...
by: Thirsty Traveler | last post by:
I hear that MD5 is not recommended for encrypting database passwords in that it can be compromised. Does anyone have a recomendation (SHA-1, etc.) on an algorithm that would be more appropriate.
by: Hunk | last post by:
Hi I have a binary file which contains records sorted by Identifiers which are strings. The Identifiers are stored in ascending order. I would have to write a routine to give the record given...
by: Ryan Liu | last post by:
Hi, If I have tens of thousands DataRow in a DataTable and allow the end user to pick any DataColumn(s) to check for duplicated lines, the data is so large, is there a better API, algorithm can...
by: pj | last post by:
Hi, I 'm currently writing a program that performs transliteration (i.e., converts greek text written using the english alphabet to "pure" greek text using the greek alphabet) as part of my...
by: ahmadcorp.m | last post by:
Hi, Need some ideas for this problem: If you had a file containing boundaries (up to 25 million) and a file containing a list of points P (up to 10 billion). What would be the fastest way to...
by: mike3 | last post by:
Hi. (Xposted to both comp.lang.c++ and comp.programming since I've got questions related to both C++ language and general programming) I've got the following C++ code. The first routine runs in...
by: istillshine | last post by:
Questions for the major contributors to comp.lang.c. What C books do you have? What C books have you read? Which algorithm book is your favorite? What resources that you find...
by: Charles Arthur | last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
by: emmanuelkatto | last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud. Please let me know. Thanks! Emmanuel
by: BarryA | last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
by: Sonnysonu | last post by:
This is the data of csv file 1 2 3 1 2 3 1 2 3 1 2 3 2 3 2 3 3 the lengths should be different i have to store the data by column-wise with in the specific length. suppose the i have to...
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers,...
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing,...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.