刁 航，金昕怡

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

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

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

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

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

2.1 題目算法分析

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

2.2 貪心算法

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

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

圖1 貪心算法核心偽代碼

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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