KTV最優點歌策略問題算法分析與研究

刁 航，金昕怡

（1.東北林業大學信息與計算機工程學院，黑龍江 哈爾濱 150040；2.東北林業大學機電工程學院，黑龍江 哈爾濱 150040）

日常生活中，在時間有限、選擇有限的情況下，經常需要選擇最優策略使利益最大化。所謂最優策略，指在相同約束條件下能盡最大可能滿足要求的策略。KTV唱歌是一種常見的娛樂項目，點歌時在價格固定的前提下會有唱歌時長有限、點歌選擇有限、歌曲時長不同等問題，就會出現最優點歌策略，即在相同時間下點唱曲目盡可能多、離開KTV時間盡可能晚。關于這類問題的解法多種多樣，其中貪心算法、動態規劃算法最為常用。貪心算法是一種經過改進后的分級處理方法，其特點是一步一步進行，根據某個優化測度，每一步都要保證能獲得局部最優解[1]。貪心算法需要根據題意先行確定一個量度標準，而大多數量度標準下所得的解不一定為問題最優解[2]。動態規劃算法的基本思想是將待求解問題分解成若干子問題，并利用問題的最優子結構性質，以自底向上的方式遞歸地從子問題的最優解逐步構造出整個問題的最優解[3]。本文分別采用這兩種算法處理問題并進行對比。

1 KT V最優點歌策略問題描述

一般來說，KTV不會在“時間到”的時候魯莽地把你正在唱的歌曲“切掉”，而是會等它放完。例如，在還有15 s的時候再唱一首2 min的歌曲，則實際上多唱了105 s。但是融合了多首歌曲的《勁歌金曲》《情歌王》等歌曲時長超過10 min，如果唱這種歌曲，相當于多唱了超過600 s。假設唱歌時間還剩t秒，接下來只能唱n首，不考慮切歌，并在時間結束之前再唱一個《勁歌金曲》或者《情歌王》，使得唱的總曲目數量盡量多，在此前提下盡量晚離開KTV。通常情況下，設定n（n≤50），t（t≤109）和每首曲目的時長（不超過3 min），得到唱的總曲目數量及總時長，保證n+1首曲目的總時長嚴格大于t。

2 貪心算法和動態規劃算法具體描述

2.1 題目算法分析

在題目中，曲目數量與時長是給定的，因此在處理時要將n首曲目抽象成歌曲數組song[i]（0＜i≤n），下標i代表第i首曲目，數組song[i]存儲的是第i首歌的時長，把n首歌的取舍用向量[x1x2x3…xi]來表示，其中每一個xi只能有0，1兩種取值，當xi=1時，表示第i首歌被點唱；xi=0時則表示該首歌不被點唱。因此本問題就可以抽象化為求取約束條件為0≤i≤n，在song[i]數組的基礎上對選歌策略進行分析[4]。本文選用貪心算法與動態規劃算法分別進行分析與解決。

2.2 貪心算法

貪心算法是在對問題求解時總是做出在當前看來是最好的選擇。也就是說，這種思想并不從整體最優上加以考慮，算法得到的是在某種意義上的局部最優解。在利用貪心算法求解KTV最優點歌策略時，可選擇的貪心策略量度如下：時長優先。以時長為量度標準，先唱時長最長的歌曲，盡量保證不會出現時長上的浪費。曲目優先。以演唱曲目數量為量度標準，先唱時長較短的歌曲，保證最終演唱曲目數量最多。

由于曲目數量、演唱時長都是約束條件，在實際生活需求與題目要求中，一般根據盡可能多唱曲目為前提，因此面臨兩種量度策略，選取曲目優先策略，目標函數為約束條件為song[i]xi≤t，xi∈{0,1}，0≤i≤n，即先對歌曲數組song[i]按照歌曲時長升序排列，在剩余t時間內，當未達到時間上限時，繼續按順序演唱下一首，直到加上第k首歌的時長后超出了t的時間范圍，取前k-1首歌曲作為點歌曲目。這種方法雖然可以得到一組可行的解，但并不是最優解，容易造成時間上的浪費。為了滿足離開時間盡量晚的約束條件，本文在上述算法思想的基礎上進行優化。考慮在出現time[k-1]+time[k]＞t，即加入第k首歌曲導致時長超出上限時，執行以下兩種優化算法策略。第一種，因為歌曲是按照時間升序排序的，所以第2首到第k首的總時長一定大于第1首到第k-1首，所以向后選取更新選擇的歌曲，以此來達到唱歌時間盡量長的要求。當第一種策略不成立時，執行第二種策略，保證前k-2首歌曲的選擇不變，考慮用后面歌曲替代第k-1首，觀察是否比原第k-1首更能在時間限制內滿足離開時間盡量晚的要求。貪心算法核心偽代碼見圖1。

圖1 貪心算法核心偽代碼

本解法關鍵點在于選擇了曲目數優先的策略，將歌曲按照時長進行排序，并且在排序后根據離開時間盡量晚的要求考慮替換歌曲問題，最終達到演唱時長與t相差盡量少的結果。然而在實際問題中，由于貪心算法的性質，上述兩種優化后的貪心策略依然無法保證取到最優解，只能得到一個可行解，并且在本題目的限制下第一種優化策略與最優解差距最小。尤其在不考慮切歌的情況下，貪心算法往往無法取得最貼合時間長度的策略，最終得到的結果可能是選擇的k-1首歌曲總時長與時間上限t還有一定距離，造成時間上的浪費，導致無法達到盡可能晚離開KTV的要求，同時在歌曲數目較多且時長相差不明顯的情況下，優化算法容易導致開銷增大，占據過多運算資源，所以本文提出了基于動態規劃算法思想的解決方案。

2.3 動態規劃算法

動態規劃算法是一種自下而上的算法，往往能夠給非NP問題求得一組最優解。在利用動態規劃算法求解KTV問題時，可以將問題抽象成一種類似復雜化0-1背包問題的情況[5]，時長t相當于背包容量，備選歌曲相當于可選擇的物品。由于有兩個限制條件，即要求在所選曲目有限制的情況下唱的曲目最多，并且在限制時長為t的情況下離開時間最晚，所以設置兩個數組，即dp[i][j]記錄歌曲數目，time[i][j]記錄演唱時長，用兩層循環來進行數量與時間的動態規劃。狀態遞推方程代碼見圖2。動態規劃算法核心偽代碼見第36頁圖3。

圖2 狀態遞推方程代碼

圖3 動態規劃算法核心偽代碼

本題動態規劃算法的策略是在先通過第一重循環dp[i][j]求出唱的曲目最多的情況后，在所唱曲目盡量多的前提下再使用第二重循環time[i][j]，選出離開時間盡量晚（唱歌時間盡量長）的情況，從而得到唱的曲目最多、離開時間最晚的最優解。動態規劃算法可以得到題目的精確最優解，但是在時間與空間上較貪心算法更復雜，開銷更大。

3 貪心算法和動態規劃算法復雜度對比分析

因為題目中總時長t的取值與備選歌曲總數n的值較大，所以從時間與空間復雜度層面上來看，貪心算法更為優越。貪心算法通過將歌曲按照時長為量度進行升序排序，按順序選取直到超出時長上限，在此基礎上運用優化算法不斷重新選取歌曲使總時長不斷趨近限制t，因此貪心算法的時間復雜度為排序所需付出的代價，空間復雜度為歌曲數組所占空間；而動態規劃問題的時間復雜度代價為兩重循環，先查找演唱曲目最多的情況，然后在得出的盡量多的曲目基礎上查找總時長最長的情況，最后能得到演唱曲目盡量多、離開KTV時間盡量晚的最優解，空間復雜度為dp數組與time數組的空間乘積大小[6]。兩種算法復雜度對比見表1。

表1 兩種算法復雜度對比表

在解決實際問題的過程中，貪心算法往往無法得到最優解，只能得到一組可行解，對結果精確度要求不高時可以使用；動態規劃算法雖然復雜度更高，但是結果更為精準，是更好的選擇[7-9]。

4 結論

本文通過利用貪心算法與動態規劃算法從兩種思想角度分析并解決KTV最優點歌策略問題。其中，貪心算法的時間空間復雜度較低，但只能得到一組可行解，無法求得最優解；動態規劃算法采用兩重循環，雖然時間與空間復雜度較貪心算法更高，但是在實際問題解決的過程中顯然是更科學有效的算法。因此，獲得KTV最優點歌策略問題最優解，使用動態規劃算法是更好的選擇，但是具體問題要具體分析，從實際需求的角度出發來選擇最恰當的算法，以求高效、實用、快捷。