一種求解RTVKP問(wèn)題的精確算法

　　 隨機(jī)時(shí)變背包問(wèn)題（randomized time-varying knapsack problem，簡(jiǎn)稱RTVKP）是一種動(dòng)態(tài)背包問(wèn)題，也是一種動(dòng)態(tài)組合優(yōu)化問(wèn)題，目前其求解算法主要是動(dòng)態(tài)規(guī)劃的精確算法、近似算法和遺傳算法．首先，利用動(dòng)態(tài)規(guī)劃提出了一種求解RTVKP問(wèn)題的精確算法，對(duì)算法時(shí)間復(fù)雜度的比較結(jié)果表明，它比已有的精確算法更適于求解背包載重較大的一類RTVKP實(shí)例．然后，分別基于差分演化和粒子群優(yōu)化與貪心修正策略相結(jié)合，提出了求解RTVKP問(wèn)題的兩種進(jìn)化算法．對(duì)5個(gè)RTVKP實(shí)例的數(shù)值計(jì)算結(jié)果比較表明，精確算法一般不宜求解大規(guī)模的RTVKP實(shí)例，而基于差分演化、粒子群優(yōu)化和遺傳算法與貪心修正策略相結(jié)合的進(jìn)化算法卻不受實(shí)例規(guī)模與數(shù)據(jù)大小的影響，對(duì)于振蕩頻率大且具有較大數(shù)據(jù)的大規(guī)模RTVKP實(shí)例均能求得一個(gè)極好的近似解．