壹号娱乐 - NG大舞台,有梦你就来

一种求解分组01背包问题的动态规划法

作者:小编    发布时间:2026-09-14 07:02:42    浏览:次

[返回]

  (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大舞台,有梦你就来提供

搜索

 谷歌地图 百度地图