Intelligent Selection Algorithm

Question

Hi all,

I am using VB.NET and I am trying to come up with some algorithm or some pseudo-code, or some VB.NET code that will let me do the following (hopefully I can explain this well):

I have 2 collection objects, Cob1 and Cob2. These collection objects store objects that implement an interface called ICob. ICob has 3 properties. A boolean IsSelected property, a property called Length, which returns a TimeSpan, and a Rating property, which is a short integer.

OK, now Cob1 has about 100 objects stored in the collection and Cob2 is an empty collection. What I want to do is select objects from Cob1 and copy them over to Cob2. I want the following rules obeyed when selecting the objects though:

1. I want to be able to specify a timespan and I want enough objects to be selected to fit into the timespan I specify (based on the Length property). So for example, if I pass a 10 minute timespan to my function, it should pick enough objects that fill the entire 10 minute window, or come as close to filling it as possible.

2. No objects should be selected twice.

3. Objects that have a higher rating (via the Rating property) should have a better chance at being picked then other objects.

4. No object that has been selected in the last 30 minutes should be selected again (so that each object will eventually get selected at least once), regardless of rating.

Can anyone give me some tips on how to achieve this? The tips can be in the form of mental processes, VB.NET example code, Pseudo-code or just about anything else that might help me.

Thanks

EDIT:

Maybe It would help to everyone if I revealed what I'm trying to do in real life.

I am writing software for a radio station that will automatically select the music and advertisments to play, kinda of like a computerized program manager.

The length represents the length of the sound byte (either a song or an advertisement) and the rating is just that. If the song is popular, it gets more airtime. If an advertiser pays more money, then it also gets more airtime.

So my program should pick songs that play for 20 minutes or so, then pick some advertisements to play for about 5 minutes or so.

Hopefully this helps a little.

Thanks for the input from everyone!

Alan

Answer 1

In order to implement 4., I believe you'll need to save the date/time when the Cob was last selected. Then, I'd do it in the following steps:

1. Filter out the ones that have not been selected within the last 30 minutes.

2. Sort by rating and set your "cursor" on the first item in the list.

3. Check the item's timespan. If short enough to fit in the specified time, select it. If not, goto 3 and proceed with the next item.

4. Check if your timespan has been filled. If yes, you are done. If no, goto 3 and proceed with the next item.

Answer 2

Note that:

The restriction 1 is from the classical knapsack problem, which works on sets, as requested by restriction 2.

Restriction 3 is rather vague. It is better to have higher value or higher coverage of the lifespan? If you don't specify a objective function to maximaze (or, to be precise, there are two: lifespan itself and rate), there are some pareto optimal solutions.

Restriction 4 is implementable by making a map object -> last time selected., in the form of black list.

Long story short: first I'd filter the set by blacklisting the object by restriction 4, and then apply a knapsack algorithm.