时间背包算法

Question

我正在使用VB.NET，我正在尝试提出一些算法或一些伪代码，或者一些VB.NET代码，这些代码可以让我做到以下几点（希望我能解释清楚）：

我有2个集合对象，Cob1和Cob2。这些集合对象存储实现名为ICob的接口的对象。 ICob有3处房产。一个布尔的IsSelected属性，一个名为Length的属性，它返回一个TimeSpan，以及一个Rating属性，它是一个短整数。

好的，现在Cob1有大约100个对象存储在集合中，而Cob2是一个空集合。我想要做的是从Cob1中选择对象并将它们复制到Cob2。我希望在选择对象时遵循以下规则：

1. 我希望能够指定一个时间跨度，并且我希望选择足够的对象以适应我指定的时间跨度（基于Length属性）。因此，例如，如果我将10分钟的时间跨度传递给我的函数，它应该选择足够的对象来填充整个10分钟的窗口，或者尽可能接近填充它。

2. 不应选择任何对象两次。

3. 评分较高的对象（通过评级属性）应该比其他对象更有机会被选中。

4. 不应再次选择在过去30分钟内选择的对象（以便每个对象最终至少被选中一次），无论评级如何。

任何人都可以给我一些如何实现这一目标的提示吗？提示可以是心理过程，VB.NET示例代码，伪代码或其他任何可能对我有帮助的形式。

由于

编辑：

如果我揭示了我在现实生活中想要做的事情，也许对每个人都有帮助。

我正在为一个广播电台编写软件，它将自动选择要播放的音乐和广告，有点像电脑化的节目管理员。

长度表示声音字节（歌曲或广告）的长度，而评级就是这个长度。如果这首歌很受欢迎，那就会有更多的播放时间。如果广告客户支付更多的钱，那么它也会获得更多的播放时间。

所以我的节目应该选择播放20分钟左右的歌曲，然后挑选一些广告播放约5分钟左右。

希望这有点帮助。

感谢大家的投入！

艾伦

Answer 1

请注意：

限制1来自经典的背包问题，它根据要求在集合上工作通过限制2。

限制3相当含糊。拥有更高价值或更高的寿命覆盖范围会更好吗？如果你没有指定一个目标函数来最大化（或者，确切地说，有两个：寿命本身和速率），那么有一些帕累托最优解。

限制4可通过制作地图对象来实现 - ＆gt;上一次选择。，以黑名单的形式。

长话短说：首先我通过限制4将对象列入黑名单来过滤该集合，然后应用背包算法。

Answer 2

为了实现4.，我相信您需要保存最后一次选择Cob的日期/时间。然后，我将按以下步骤执行此操作：

1. 过滤掉过去30分钟内未选择的内容。

2. 按评分排序并设置“光标”列表中的第一项。

3. 检查项目的时间跨度。如果足够短以适合指定时间，请选择它。如果没有，请转到3并继续下一个项目。

4. 检查您的时间跨度是否已经填满。如果是的话，你就完成了。如果不是，请转到3并继续下一个项目。