计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2012年
7期
237-241
,共5页
贺毅朝%田海燕%张新禄%王志威%高锁刚
賀毅朝%田海燕%張新祿%王誌威%高鎖剛
하의조%전해연%장신록%왕지위%고쇄강
NP-难问题%0-1背包问题%动态优化%时变背包问题%动态规划法
NP-難問題%0-1揹包問題%動態優化%時變揹包問題%動態規劃法
NP-난문제%0-1배포문제%동태우화%시변배포문제%동태규화법
随机时变背包问题(RTVKP)是一种动态组合优化问题,也是一种典型的NP-hard问题.由于RTVKP问题中物品的价值、重量和背包载重均是动态变化的,导致问题的求解非常困难.在动态规划法基础上,提出了一种求解背包载重随机变化的RTVKP问题的确定性算法,分析了其复杂度和成功求解需要满足的条件.对两个大规模实例的计算表明,该算法是求解RTVKP问题的一种高效算法.
隨機時變揹包問題(RTVKP)是一種動態組閤優化問題,也是一種典型的NP-hard問題.由于RTVKP問題中物品的價值、重量和揹包載重均是動態變化的,導緻問題的求解非常睏難.在動態規劃法基礎上,提齣瞭一種求解揹包載重隨機變化的RTVKP問題的確定性算法,分析瞭其複雜度和成功求解需要滿足的條件.對兩箇大規模實例的計算錶明,該算法是求解RTVKP問題的一種高效算法.
수궤시변배포문제(RTVKP)시일충동태조합우화문제,야시일충전형적NP-hard문제.유우RTVKP문제중물품적개치、중량화배포재중균시동태변화적,도치문제적구해비상곤난.재동태규화법기출상,제출료일충구해배포재중수궤변화적RTVKP문제적학정성산법,분석료기복잡도화성공구해수요만족적조건.대량개대규모실례적계산표명,해산법시구해RTVKP문제적일충고효산법.
