Algorithms

harold aptroot wrote:

veryone seems to use heuristic algorithms because solving an ILP problem is too slow for them

static int[] Schedule(int[] jobs, int machines)
{
    int[] targets = new int[jobs.Length];
    int[] lengths = new int[machines];
    _bestFoundScore = int.MaxValue;
    _bestSolution = null;
    _schedule(jobs, targets, 0, lengths);
    return _bestSolution;
}
static int _bestFoundScore = int.MaxValue;
static int[] _bestSolution = null;
static void _schedule(int[] jobs, int[] targets, int index, int[] lengths)
{
    if (index == jobs.Length)
    {   // reached bottom
        int max = 0;
        for (int j = 0; j < lengths.Length; j++)
            if (lengths[j] > max)
                max = lengths[j];
        if (max >= _bestFoundScore)
            return; // not good

        // found better
        _bestFoundScore = max;
        int[] res = new int[targets.Length];
        Array.Copy(targets, res, res.Length);
        _bestSolution = res;
    }
    else
    {
        for (int i = 0; i < lengths.Length; i++)
        {   // for each machine

            // add unused job to that machine
            targets[index] = i + 1;
            lengths[i] += jobs[index];
            // check bounds
            int max = 0;
            for (int j = 0; j < lengths.Length; j++)
                if (lengths[j] > max)
                    max = lengths[j];
            if (max < _bestFoundScore)
            {
                // recurse for next job
                _schedule(jobs, targets, index + 1, lengths);
            }
            // undo changes
            targets[index] = 0;
            lengths[i] -= jobs[index];
        }
    }
}

harold aptroot wrote:

For anything above 16 jobs it becomes really really slow

Luc Pattyn wrote:

IMO the more jobs the more "biggest job first" gets nearer to the optimal solution

static void Main(string[] args)
{
    StringBuilder sb = new StringBuilder();
    int j = 100;
    for (int i = 100; i < 101000; i++)
    {
        if (j > 999) j = 100;
        sb.Append((j*10).ToString() + " ");
        j++;
    }
    string s = sb.ToString();


    int idx = 0;
    int startidx = 0;
    int length = s.Length;
    List<int> nrs = new List<int>((int)(length*0.25));

    var watch = Stopwatch.StartNew();
    do
    {
        if (s[idx] == ' ')
        {
            if(idx>startidx)
                nrs.Add(atoi(s, startidx, idx));
            startidx = idx + 1;
        }
        idx ++;
    }
    while (idx < length);
    Console.WriteLine(watch.ElapsedMilliseconds);
    Console.ReadLine();
}


static int atoi(string c, int start, int len) {
  int res = 0;
  int i = start;
  len += start;
  while (i<len && c[i] >= '0' && c[i] <= '9')
    res = res * 10 + c[i++] - '0';
  return res;
}

PaulowniaK wrote:

How can I improve my code in C++?

PaulowniaK wrote:

CString::Find()

// Args:
//  txt: the string
//  txt_size: the string size (including the NULL terminator)
//  a: the int array
//  max_count: the int array size.
// Returns: the number of found integers.
// Remark: if the string contains more integers than array capacity, only max_count integers will be returned.
int get_all_numbers( const char * txt, int txt_size, int * a, int max_count)
{
  const char * p0 = txt;
  const char * p1 = NULL;
  const char * guard = p0+txt_size-1;
  int count = 0;
  while (p1 < guard && count < max_count)
  {
    a[count++] = (int) strtol(p0, (char**)&p1, 10);
    p0 = p1;  
  }
  return count;
}