(1.湖南科技学院计算机与通信工程系,湖南永州425100;2.湖南大学数学与计量经济学院,湖南长沙410082)
摘要研究了分组0-1背包问题,提出了一种动态规划解决方法,在物品总数为n个和背包承重
量为W时,递推过程的复杂度为O(nW),回溯过程的复杂度为O(n).计算实例表明利用该方法易于找到最优解.
(1.DepartmentofComputerandCommunicationEngineering,HunanUniversityofScienceandEngineering,Yongzhou,
Hunan425100China;2.CollegeofMathematicsandEconometrics,HunanUniversity,Changsha,Hunan410082China)
AbstractThispaperstudiedtheclassified0-1knapsackproblem,andproposedadynamicprogrammingmethod.The
complexityoftherecursiveprocessisO(nW),andthecomplexityofthetracebackprocessisO(n),wherenisthetotalnumberofgoodsandWisthebearingweightoftheknapsack.Theexampleshowsthatitiseasytofindtheoptimalsolutionbythemethod.
KeywordsKnapsackProblem;NP-complete;DynamicProgramming
本文将传统的0-1背包问题扩展为分组0-1背包问题,阐述了分组0-1背包问题的动态规划解决方案,为背包问题的应用拓展了新的思路.
为:已知n个物品和一个承重量为W的背包,每个物品i的重量为wi,价值为vi(i=1,2,…,n),现要从这n个物品中选出若干件放入背包,使得装入背包物品的总重量不超过W,且总价值达到最大.0-
1背包问题在信息安全、工程决策等领域中有着极为重要的应用[1-5],对0-1背包问题扩展研究,如0
背包.不能将物品装入背包多次,也不能只装入部分的物品.在这里假设所有物品的重量和背包的承重量都是正整数.分组0-1背包问题的数学模型描述为:
当l=2时(对应(i,j)=(2,1)),易知对于任意k,由公式(1)或公式(2)给出的M(1)[2,k]满足最大价值.
2)假设1≤l≤m时(对应唯一(i,j)),对于任意k,由公式(1)或公式(2)给出的M(j)[i,k]满足最大价值.
以用一个动态规划表M跟踪递推,行对应于每一个物品,列对应于背包的承重量,M(j)[i,k]代表第
时,设 M(1)[0,k]=0,M(j)[i,0]=0;当2 ≤j ≤r
时,设 M(j)[0,k]= M(j-1)[s ,k],则分组0-1背包
纳假设 M(j′)[i′ -1,k]= M(j)[i,k]满足最大价值,
设 M(j′)[i′ -1,k]= M(j)[i,k]满足最大价值,所以
M(j′)[i′ ,k]= M(j′)[i′ -1,k];而当第 m +1个物品
= max {M(j′)[i′ -1,k],M(j)[i′ -1,k-wj′
=s1 + … +sj -1 +i -1时(这里1≤i <sj′ ),有
为了通过动态规划表 M 求取最优子集,定义一 个回溯表 F 来跟踪上述递推过程,行对应于每一个 物品,列对应于背包的承重量.令
由归纳假设 M(j′)[i′ -1,k]= M(j)[i,k]满足最大价
数为n 个和背包承重量为 W 时,生成动态规划表 M 的复 杂 度 为 O(nW ),生 成 回 溯 表 F 的 复 杂 度 为 O(n).该方法思路简单,容易理解,计算实例验证了 利用该方法易于找到最优解.
[1] B Chor,R Rivest.A knapsack-typepublickeycryptosystem
basedonarithmeticinfinitefields[J].IEEE Transactionson
InformationTheory,1988,34(5):901-909.
[2] CLaih,JLee,L Harn,etal.Linearlyshiftknapsackpublic- keycryptosystem[J].IEEEJournalofSelectedAreasCommu- nication,1989,7(4):534-539.
[3] D Yao,K Frikken,M Atallah,etal.Privateinformation:to revealornottoreveal[J].ACM TransactionsonInformation andSystemsSecurity,2008,12(1):1-27.
[4] 张生,魏忠华,何 尚 录 等.0-1 背 包 问 题 在限额投资决策中
1,x2,x3,x1,x2)= (1,0,1,0,1,1,0,1).故最优子
[6] 谢涛,陈火 旺,康 立 山.二次背包问题的一 种 快 速 解 法 [J].
[7] 熊小华,宁爱兵,马良.多目 标 0-1 背包问题的元胞竞争决 策算法[J].计算机应用研究,2010,27(10):3680-3683.
本文由:壹号娱乐 - NG大舞台,有梦你就来提供


