Algorithme Knapsack pour le temps

Question

J'utilise VB.NET et j'essaie de trouver un algorithme ou un pseudo-code, ou un code VB.NET qui me permettra de faire ce qui suit (j'espère que je peux bien l'expliquer) :

J'ai 2 objets de collection, Cob1 et Cob2. Ces objets de collection stockent des objets qui implémentent une interface appelée ICob. ICob a 3 propriétés. Une propriété IsSelected booléenne, une propriété appelée Length, qui renvoie un TimeSpan et une propriété Rating, qui est un entier court. OK, maintenant Cob1 a environ 100 objets stockés dans la collection et Cob2 est une collection vide. Ce que je veux faire, c'est sélectionner des objets de Cob1 et les copier sur Cob2. Je veux que les règles suivantes obéirent lors de la sélection des objets si:

1. Je veux être en mesure de préciser un laps de temps et je veux assez d'objets pour être sélectionnés pour entrer dans la timespan je précise (basée sur la propriété de longueur) . Donc, par exemple, si je passe une période de 10 minutes à ma fonction, il faut choisir suffisamment d'objets qui remplissent toute la fenêtre de 10 minutes, ou se rapprocher autant que possible du remplissage.

2. Aucun objet ne doit être sélectionné deux fois.

3. Les objets ayant une note plus élevée (via la propriété Rating) devraient avoir une meilleure chance d'être sélectionnés que les autres objets.

4. Aucun objet sélectionné dans les 30 dernières minutes ne doit être sélectionné à nouveau (de sorte que chaque objet soit finalement sélectionné au moins une fois), quelle que soit l'évaluation.

Quelqu'un peut-il me donner quelques conseils sur la façon d'y parvenir? Les conseils peuvent être sous la forme de processus mentaux, code exemple VB.NET, Pseudo-code ou à peu près tout ce qui pourrait m'aider.

Merci

EDIT:

Peut-être que cela aiderait à tout le monde si je révélais ce que je suis en train de faire dans la vie réelle.

J'écris un logiciel pour une station de radio qui va sélectionner automatiquement la musique et les publicités à jouer, un peu comme un gestionnaire de programme informatisé.

La longueur représente la longueur de l'octet son (soit une chanson ou une publicité) et la note est juste cela. Si la chanson est populaire, elle obtient plus de temps d'antenne. Si un annonceur paie plus d'argent, il obtient également plus de temps d'antenne. Donc, mon programme devrait choisir des chansons qui jouent pendant environ 20 minutes, puis choisir des publicités à jouer pendant environ 5 minutes environ.

J'espère que cela aide un peu.

Merci pour la contribution de tout le monde!

Alan

Answer 1

Notez que:

La restriction 1 est de la knapsack problem classique, qui fonctionne sur des ensembles, comme demandé par la restriction 2.

Restriction 3 est assez vague. Il est préférable d'avoir une valeur plus élevée ou une couverture plus élevée de la durée de vie? Si vous ne spécifiez pas de fonction objectif pour maximiser (ou, pour être précis, il y en a deux: durée de vie elle-même et taux), il existe des solutions pareto optimales.

La restriction 4 peut être implémentée en créant un objet carte -> la dernière fois sélectionnée, sous la forme d'une liste noire.

Longue histoire courte: d'abord je filtrer l'ensemble en mettant sur la liste noire l'objet par la restriction 4, puis appliquer un algorithme de sac à dos.

Answer 2

Afin de mettre en œuvre 4., je crois que vous devez enregistrer la date/heure lorsque le Cob a été sélectionné en dernier.Ensuite, je le ferais dans les étapes suivantes:

1. Filtrer ceux qui n'ont pas été sélectionnés dans les 30 dernières minutes.

2. Trier par note et définir votre «curseur» sur le premier élément de la liste.

3. Vérifiez le délai de l'article. Si elle est suffisamment courte pour tenir dans l'heure spécifiée, sélectionnez-la. Sinon, passez à 3 et passez à l'élément suivant.

4. Vérifiez si votre période de temps a été remplie. Si oui, vous avez terminé. Si non, passez à 3 et passez à l'élément suivant.