15,919,778 members
Home / Discussions / Algorithms

# Algorithms

 "Best Fit" Algorithm Request && Teach A Man To Fish Michael Fritzius17-Apr-10 13:10 Michael Fritzius 17-Apr-10 13:10
 Re: "Best Fit" Algorithm Request && Teach A Man To Fish Luc Pattyn17-Apr-10 13:45 Luc Pattyn 17-Apr-10 13:45
 Re: "Best Fit" Algorithm Request && Teach A Man To Fish Radhakrishnan G.18-May-10 3:44 Radhakrishnan G. 18-May-10 3:44
 Re: "Best Fit" Algorithm Request && Teach A Man To Fish harold aptroot17-Apr-10 14:31 harold aptroot 17-Apr-10 14:31
 Re: "Best Fit" Algorithm Request && Teach A Man To Fish Som Shekhar17-Apr-10 20:46 Som Shekhar 17-Apr-10 20:46
 Re: "Best Fit" Algorithm Request && Teach A Man To Fish harold aptroot18-Apr-10 2:01 harold aptroot 18-Apr-10 2:01
 Re: "Best Fit" Algorithm Request && Teach A Man To Fish Som Shekhar18-Apr-10 2:18 Som Shekhar 18-Apr-10 2:18
 Re: "Best Fit" Algorithm Request && Teach A Man To Fish [modified] harold aptroot18-Apr-10 2:38 harold aptroot 18-Apr-10 2:38
 Time for some code! This code is clearly crap, I just wrote it quickly in a console app to see whether it would work. It calculates the optimal solution with a simple branch and bound algorithm (without any tricks that can make it faster) - all cases that I tested worked. For anything above 16 jobs it becomes really really slow. As a quick guestimate, the time complexity is about `O(m^j)` where `m` is the number of machines and `j` is the number of jobs. ```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]; } } } ``` Edit: but I don't think using rectangles will help at all - if anything, it will just make it harder without having any benefits. The problem would still be the same, but you'd have "the width of a rectangle" instead of just "some integer or float" which is really just the same thing. modified on Sunday, April 18, 2010 8:44 AM
 Re: "Best Fit" Algorithm Request && Teach A Man To Fish Som Shekhar18-Apr-10 2:56 Som Shekhar 18-Apr-10 2:56
 Re: "Best Fit" Algorithm Request && Teach A Man To Fish harold aptroot18-Apr-10 3:16 harold aptroot 18-Apr-10 3:16
 Re: "Best Fit" Algorithm Request && Teach A Man To Fish Som Shekhar18-Apr-10 3:40 Som Shekhar 18-Apr-10 3:40
 Re: "Best Fit" Algorithm Request && Teach A Man To Fish harold aptroot18-Apr-10 3:44 harold aptroot 18-Apr-10 3:44
 Re: "Best Fit" Algorithm Request && Teach A Man To Fish Som Shekhar18-Apr-10 3:53 Som Shekhar 18-Apr-10 3:53
 Re: "Best Fit" Algorithm Request && Teach A Man To Fish Michael Fritzius18-Apr-10 9:40 Michael Fritzius 18-Apr-10 9:40
 Re: "Best Fit" Algorithm Request && Teach A Man To Fish Luc Pattyn18-Apr-10 10:02 Luc Pattyn 18-Apr-10 10:02
 Re: "Best Fit" Algorithm Request && Teach A Man To Fish Luc Pattyn18-Apr-10 10:07 Luc Pattyn 18-Apr-10 10:07
 Re: "Best Fit" Algorithm Request && Teach A Man To Fish harold aptroot18-Apr-10 11:39 harold aptroot 18-Apr-10 11:39
 Re: "Best Fit" Algorithm Request && Teach A Man To Fish Michael Fritzius19-Apr-10 11:59 Michael Fritzius 19-Apr-10 11:59
 Re: "Best Fit" Algorithm Request && Teach A Man To Fish Luc Pattyn19-Apr-10 12:45 Luc Pattyn 19-Apr-10 12:45
 Re: "Best Fit" Algorithm Request && Teach A Man To Fish Tim Craig19-Apr-10 12:48 Tim Craig 19-Apr-10 12:48
 Re: "Best Fit" Algorithm Request && Teach A Man To Fish [modified] harold aptroot19-Apr-10 12:56 harold aptroot 19-Apr-10 12:56
 Re: "Best Fit" Algorithm Request && Teach A Man To Fish Tadeusz Westawic23-Apr-10 2:24 Tadeusz Westawic 23-Apr-10 2:24
 Re: "Best Fit" Algorithm Request && Teach A Man To Fish Tadeusz Westawic23-Apr-10 3:57 Tadeusz Westawic 23-Apr-10 3:57
 CSMA / CA hairy_hats14-Apr-10 4:59 hairy_hats 14-Apr-10 4:59
 Re: CSMA / CA Anshul R9-Jun-10 4:14 Anshul R 9-Jun-10 4:14
 Last Visit: 31-Dec-99 18:00     Last Update: 19-Jun-24 4:50 Refresh ᐊ Prev1...122123124125126127128129130131 Next ᐅ