時間的揹包算法

Question

我正在使用VB.NET，我試圖想出一些算法或一些僞代碼，或者一些VB.NET代碼，這些代碼會讓我做下面的事情（希望我能解釋得很清楚） ：

我有2個集合對象，Cob1和Cob2。這些集合對象存儲實現了稱爲ICob的接口的對象。 ICob有3個屬性。一個布爾型的IsSelected屬性，一個名爲Length的屬性，它返回一個TimeSpan以及一個Rating屬性，它是一個短整數。

好吧，現在Cob1有大約100個對象存儲在集合中，而Cob2是一個空集合。我想要做的是從Cob1中選擇對象並將它們複製到Cob2。我想雖然在選擇對象時，以下規則遵守：

1. 我希望能夠指定一個時間跨度，我想選擇足夠的對象以適應我指定的時間跨度（基於長度屬性） 。例如，如果我將一個10分鐘的時間跨度傳遞給我的函數，它應該選取足夠的對象來填充整個10分鐘的窗口，或者儘可能接近地填充它。

2. 不應該選擇兩個對象。

3. 具有較高評分的對象（通過評分屬性）應該有更好的機會被挑選，然後其他對象。

4. 不管評級如何，應該再次選擇在過去30分鐘內未被選擇的對象（以便每個對象最終將被選擇至少一次）。

任何人都可以給我一些提示如何實現這一目標？這些提示可以是心理過程，VB.NET示例代碼，僞代碼或其他任何可能幫助我的內容。

感謝

編輯：

也許，如果我發現我想要在現實生活中做這將有助於給大家。

我正在爲廣播電臺編寫軟件，它會自動選擇要播放的音樂和廣告，有點像電腦程序管理器。

長度代表聲音字節（歌曲或廣告）的長度，評分就是這樣。如果這首歌很流行，它會得到更多的播出時間。如果廣告商支付更多的錢，那麼它也會獲得更多的通話時間。

所以我的程序應該選擇播放20分鐘左右的歌曲，然後選擇一些廣告播放大約5分鐘左右。

希望這會有所幫助。

感謝大家的意見！

艾倫

Answer 1

注意的是：

的限制圖1是從經典knapsack problem，通過限制性的要求，其適用於套，2.

限制3是相當含糊的。壽命的更高或更高的覆蓋率更好？如果您沒有指定一個最大化的目標函數（或者確切地說，有兩個：壽命本身和速率），那麼有一些帕累托最優解。

限制4可通過以黑名單的形式製作地圖對象 - >上次選擇時間來實現。

長話短說：首先我會通過限制4將對象加入黑名單來過濾集合，然後應用揹包算法。

Answer 2

爲了實現4，我相信你會需要保存的日期/時間時，最後選擇了玉米棒。然後，我會按照以下步驟進行操作：

1. 過濾出在過去30分鐘內沒有被選中的那些。

2. 按評分排序，並在列表中的第一個項目上設置「光標」。

3. 查看商品的時間範圍。如果足夠短以適應指定的時間，請選擇它。如果沒有，轉到3並繼續下一個項目。

4. 檢查您的時間跨度是否已滿。如果是的話，你就完成了。如果不是，轉到3並繼續下一個項目。