KTV最優(yōu)點歌策略問題算法分析與研究

刁 航，金昕怡

（1.東北林業(yè)大學(xué)信息與計算機(jī)工程學(xué)院，黑龍江 哈爾濱 150040；2.東北林業(yè)大學(xué)機(jī)電工程學(xué)院，黑龍江 哈爾濱 150040）

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

1 KT V最優(yōu)點歌策略問題描述

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

2 貪心算法和動態(tài)規(guī)劃算法具體描述

2.1 題目算法分析

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

2.2 貪心算法

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

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

圖1 貪心算法核心偽代碼

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

2.3 動態(tài)規(guī)劃算法

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

圖2 狀態(tài)遞推方程代碼

圖3 動態(tài)規(guī)劃算法核心偽代碼

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

3 貪心算法和動態(tài)規(guī)劃算法復(fù)雜度對比分析

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

表1 兩種算法復(fù)雜度對比表

在解決實際問題的過程中，貪心算法往往無法得到最優(yōu)解，只能得到一組可行解，對結(jié)果精確度要求不高時可以使用；動態(tài)規(guī)劃算法雖然復(fù)雜度更高，但是結(jié)果更為精準(zhǔn)，是更好的選擇[7-9]。

4 結(jié)論

本文通過利用貪心算法與動態(tài)規(guī)劃算法從兩種思想角度分析并解決KTV最優(yōu)點歌策略問題。其中，貪心算法的時間空間復(fù)雜度較低，但只能得到一組可行解，無法求得最優(yōu)解；動態(tài)規(guī)劃算法采用兩重循環(huán)，雖然時間與空間復(fù)雜度較貪心算法更高，但是在實際問題解決的過程中顯然是更科學(xué)有效的算法。因此，獲得KTV最優(yōu)點歌策略問題最優(yōu)解，使用動態(tài)規(guī)劃算法是更好的選擇，但是具體問題要具體分析，從實際需求的角度出發(fā)來選擇最恰當(dāng)?shù)乃惴ǎ郧蟾咝А嵱谩⒖旖荨?/p>