Roger Burton West <roger-UvLOT2mcgw/NLxjTenLetw@xxxxxxxxxxxxxxxx>:
> On Mon, May 24, 2004 at 04:12:25PM -0400, Mark Jason Dominus wrote:
>
> >I'd be interested to hear if anyone other than me initially considered
> >a greedy algorithm, and then realized later that that wouldn't always
> >work, and whether the test suite I posted had anything to do with
> >that.
>
> I tried a slight variant. During the first pass, converting the
> schedule map for each course into a bitmask, I calculated a "weight"
> for the course (number of bits set); then I sorted the courses into
> descending weight order, and in effect followed the procedure you
> described.
A very similar problem is "bin packing". You have a bunch of objects,
each of which has a given 'size', and you have a bunch of bins, each
of which can hold objects whose total size is no more than some given
number N. The problem is to determine the minimum number of bins that
are required to hold all the objects.
The bin packing problem is also NP-complete. But the 'FFD' (first fit
decreasing) algorithm, which is analogous to yours, is known to use no
more than 11/9 of the minimum possible number of bins, and in most
cases it does substantially better than this. FFD is simply the greedy
algorithm in which the items are placed into the bins starting with
the largest.
It might turn out that your algorithm obeys a similar sort of bound.
I feel a little silly that I didn't think of trying that myself.
> I wasn't able to come up with any cases that would break this on my own,
A possibly interesting exercsise would be to show that the greedy
algorithm always works when there are fewer than four courses. Or
maybe that's too easy.
|
